In Mathematical Logic, What is a Language?

I've been reading about mathematical logic and computability theory, but I'm somewhat confused on one note: what exactly is a language? What does it mean when I am told "let $\langle 0, +, \leq \rangle$ be a language"? I looked this up everywhere I could, but haven't found a satisfactory/clear answer.

Solution 1:

From Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001), Section 2.1. : First-Order Languages, page 69-on.

We assume an alphabet with the following symbols :

$A$. Logical symbols :

$A_0$. Parentheses: $(, )$.

$A_1$. Sentential connective symbols: $\rightarrow, \lnot$.

$A_2$. Variables (one for each positive integer $n$): $v_1, v_2, ...$.

$A_3$. Equality symbol (optional): $=$.

$B$. Parameters :

$B_0$: Quantifier symbol: $\forall$.

$B_1$. Predicate symbols: For each positive integer $n$, some set (possibly empty) of symbols, called $n$-place predicate symbols.

$B_2$. Constant symbols: Some set (possibly empty) of symbols.

$B_3$. Function symbols: For each positive integer $n$, some set (possibly empty) of symbols, called $n$-place function symbols.

Then we need :

• the definition of expression [page 73] : any finite sequence of symbols;

• the definition of term [page 74] : terms are the nouns and pronouns of our language;

• the definition of atomic formula [page 74] : an atomic formula is an expression of the form $Pt_1...t_n$, where $P$ is an $n$-place predicate symbol and $t_1,..., t_n$ are terms. For example, $=v_1v_2$ is an atomic formula, since $=$ is a predicate symbol and each variable is a term.

• the definition well-formed formulas [page 75] : those expressions that can be built up from the atomic formulas by use (zero or more times) of the connective symbols and the quantifier symbol.

  ---

Examples

(1) We can avoid all predicate, constant and function symbols, and use only equality. This theory is "made of" formulas like : $x = y$ , $\forall x(x = x)$, and so on.

(2) First-order arithmetic : we have a constant symbol : $0$, a (unary) function symbol $S$ (for the successor function) and two (binary) predicate symbols : $+$ for sum and $\times$ for product.

Then we usually expand the language introducing the defined (binary) predicate symbols : $<$ and $\le$.

(3) First-order set theory : we have only one (binary) predicate : $\in$ ("membership"). Then, as usual, we expand the language introducing the constant symbol $\emptyset$ for the "emptyset".

Solution 2:

The Wikipedia on Signature says "The language [emphasis added] of a signature is the set of all well formed sentences built from the symbols in that signature together with the symbols in the logical system."

So, when you're told that "let ⟨0,+,≤⟩ be a language", we're getting told that we have "0", "+", and "≤" have "0" in the signature, with connective symbols and quantifier symbols presupposed (as Andre Nicolas points out). Almost surely, "0" indicates a nullary function (or constant), "+" indicates a binary function, and "≤" indicates a binary relation.

For more details see Mauro's nice answer.