7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The SEP article on “model theory” explains this, as will the first chapter of any model theory textbook. $\endgroup$
    – MJD
    Commented May 20, 2014 at 14:59
  • $\begingroup$ Ah! I was looking in the wrong places: I thought this would be explained in the context of first-order logic... I did not realize that this is a model-theoretic topic. $\endgroup$
    – Newb
    Commented May 20, 2014 at 15:01
  • 1
    $\begingroup$ Probably this is a very abbreviated version of let $L$ be the first-order language with constant symbol $0$, binary function symbol $+$, and binary predicate symbol$\le$. It is understood that the usual symbols for variables, conectives, quantifiers, equality are around, and that the formation rules for terms, formulas are the usual ones. $\endgroup$ Commented May 20, 2014 at 15:02
  • $\begingroup$ Some reference on first answering "What is language" $\endgroup$
    – MmmHmm
    Commented Jan 8, 2017 at 10:17

2 Answers 2

6
$\begingroup$

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".

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .