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}\)