Mathematical Logic and Computability III. (Chapter 2: Logic of First Order)

This wiki is the continuation of this

The first-order logic can be considered as an extension of the propsicional logic. In this, a simple proposition of ordinary language is represented globally, by a symbol or row of symbols. On the other hand, in the logic of the first order, this simple proposition may be represented by a symbolism in which the predicate and the subject of the proposition are also represented.

Let's see some examples.

"Carlos is tall" can be represented by $Ac$, if $A$ represents "is tall" and c represents "Carlos". In this case, the interpretation of $A$ is said to be class $A^{*}$ of the tall people, and that of $c$ is $c^{*}$ = Carlos. That is, $Ac$ represents $c^{*} \in A^{*}$

"Jorge is Marta's brother" can be represented by $Hjm$, if $H$ stands for "is brother of",$j$ stands for "Jorge" and $m$ stands for "Marta". The interpretation of $H$ is then said to be the set $H^{*}$ of pairs of persons who are siblings, that of $j$ is $j^{*}$ = Jorge and that of $m$ is $m^{*}$ = Marta. Thus, $Hjm$ represents $\langle j^{*}, m^{*} \rangle \in H^{*}$

In Grammar, the expressions "is tall", "is brother of" are predicates. Hence, the symbols $A$, $H$ representing them are said predicate symbols, $A$ unary, $H$ binary. The interpretation of $A$ has been one relation $A^{*}$ unary and that of H has been a relation $H^{*}$ binary.

If the subject is of general or arbitrary index, quantifiers $\forall$ or $\exists$ are used. Let's see one example:

"All lions have mane" can be represented by $\forall x \space Mx$, if $\forall x$ represents "each lion" and $M$ represents "has mane". In this case, the interpretation of $\forall$ is said to be the set $L$ of the lions, and that of $M$ is the class $M^{*}$ of the beings that have mane.

There are also symbols for representing ordinary functions.

" Rocinante's head" can be represented by $fb$, if $f$ means "the head of " and $b$ represents "Rocinante". En this case, the interpretation of $f$ is $f^{*}$ given by $f^{*} (z)$ = head of z = z's head. And that of $b$ is $b^{*}$ =Rocinante.

The alphabet of a first-order language consists of the symbols of a list such as the following:

• 1.- Parentheses: ( , )

• 2.- Connectives: $\neg, \Rightarrow$

• 3.- Variables: $x_1, x_2, \ldots$

• 4.- Universal quantizer: $\forall$

• 5.- Symbol of equality (optional): =

• 6.- Predicate Symbols: P, Q, ..., $\in$, < , ..., $A^n$, $B^n, ... (\forall n \ge 1)$

• 7.- Function symbols: f, g, ... , $f^n, g^n, ... (\forall n \ge 1)$

• 8.- Constant symbols: c , 0, ..., $c_1, c_2, ...$

$\boxed{\text{ Note 1.-}}$ Any language must have symbols 1 - 4, and a predicate at least (which can be =)

$\boxed{\text{ Note 2.-}}$ Each predicate or function symbol must be assigned a natural number (its order or arity). If the order is 1, it's unary, if the order is 2, it's binary...

$\boxed{\text{ Note 3.-}}$ The equals symbol =, has binary predicate meaning, but special as will be seen. According to the previous notes, a specific language is defined when it is established:

• (i) if it has the symbol = or not.

• (ii) what symbols 6 - 8 contains.

Symbols (i) and (ii) are called language parameters.

Example 1: Pure language of equality

• Equality: yes.

• Other parameters. None

Example 2: language of theory of sets

• Equality : yes

• Predicates: 2 binary predicates: $\in, \subseteq$

• Functions: None

• Constants: one alone $\emptyset$ ( or none)

Example 3: language of Arithmetic

• Equality : yes

• Predicates : <

• Functions: one 1- ary: $S$ (successor) and 2 binary: + (sum) and $\times$ product.

• Constants : 0

Definition 2.1.1. We call expression of language to a finite sequence of n symbols of the alphabet,$(n \neq 0)$ written in row:$s_1 s_2 \ldots s_n$

Definition 2.1.2. For each function symbol n-aria $f$, we indicate with T$_f$ an internal n-aria operation in the expressions set $E$, defined as: $T_f (\alpha _1, \cdots, \alpha_n) = f\alpha_1 \cdots \alpha_n$.

And we call term of language, any member generated by variables and constants, by the operations $T_f$. If in language there are no function symbols, terms are variables and constants.

In language of Arithmetic, the following expressions are terms:

$0,\space S0,\space SS0, \space +x_1 0, \space S+x_1 0, \space +x_1 Sx_2$

Defintion 2.1.3. It's said that an atomic formula will be given to an expression of the form $Pt_1 \ldots t_n$, where $P$ is an n-ary predicate symbol and $t_1, \ldots , t_n$ are terms.

Defintion 2.1.4. Let $E_{\neg}$, $E_{\Rightarrow}$, $Q_i, \{i = 1, 2, \ldots\}$ be internal operations of the expressions set $E$, defined as:

$E_{\neg} (\alpha) = \neg \alpha$, $E_{\Rightarrow} (\alpha, \delta) = (\alpha \Rightarrow \delta)$, $Q_i (\alpha) = \forall x_i \alpha$.

A well formed formula (wff) will be given to any member of the set E generated by the atomic formulas, by the operations $E_{\neg}$, $E_{\Rightarrow}$, $Q_i, \{i = 1, 2, \ldots\}$

$=x_1 0$ (atomic formula), $<x_1 Sx_2$ (atomic formula), $\neg =x_1 0$, $\neg <x_1 Sx_2$, ($\neg =x_1 0 \Rightarrow \neg <x_1 Sx_2$), $\forall x_1 (\neg =x_1 0 \Rightarrow \neg <x_1 Sx_2$)

The previous example presents a constructive succession in the set E, with generators atomic formulas and operations $E_{\neg}$, $E_{\Rightarrow}$, $Q_i, \{i = 1, 2, \ldots\}$ .

Induction principle for terms 2.1.5.

Let R be a set of terms that satisfies: 1) contains all variables and constants; 2) is closed for operations $T_f$. Then, R is the set of all terms.

Induction principle for wffs 2.1.6.

Let C be a set of wffs that satisfies: 1) contains all atomic formulas; 2) is closed for operations $E_{\neg}$, $E_{\Rightarrow}$, $Q_i, \{i = 1, 2, \ldots\}$ . . Then, C is the set of all wffs.

Theorem 2.1.7. The set of all terms is freely generated

---

Proof.-

$\small \textrm{Lógica matemática y computabilidad. Author:J. Sancho San Román}$