Mathematical Logic and Computability III. (Chapter 2: Logic of First Order)
This wiki is the continuation of this
Contents
Chapter 2.- Logic of first order. Introduction
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 , if represents "is tall" and c represents "Carlos". In this case, the interpretation of is said to be class of the tall people, and that of is = Carlos. That is, represents
"Jorge is Marta's brother" can be represented by , if stands for "is brother of", stands for "Jorge" and stands for "Marta". The interpretation of is then said to be the set of pairs of persons who are siblings, that of is = Jorge and that of is = Marta. Thus, represents
In Grammar, the expressions "is tall", "is brother of" are predicates. Hence, the symbols , representing them are said predicate symbols, unary, binary. The interpretation of has been one relation unary and that of H has been a relation binary.
If the subject is of general or arbitrary index, quantifiers or are used. Let's see one example:
"All lions have mane" can be represented by , if represents "each lion" and represents "has mane". In this case, the interpretation of is said to be the set of the lions, and that of is the class of the beings that have mane.
There are also symbols for representing ordinary functions.
" Rocinante's head" can be represented by , if means "the head of " and represents "Rocinante". En this case, the interpretation of is given by = head of z = z's head. And that of is =Rocinante.
1.- Language of the Logic of first order
The alphabet of a first-order language consists of the symbols of a list such as the following:
1.- Parentheses: ( , )
2.- Connectives:
3.- Variables:
4.- Universal quantizer:
5.- Symbol of equality (optional): =
6.- Predicate Symbols: P, Q, ..., , < , ..., ,
7.- Function symbols: f, g, ... ,
8.- Constant symbols: c , 0, ...,
Any language must have symbols 1 - 4, and a predicate at least (which can be =)
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...
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:
Functions: None
Constants: one alone ( or none)
Example 3: language of Arithmetic
Equality : yes
Predicates : <
Functions: one 1- ary: (successor) and 2 binary: + (sum) and product.
Constants : 0
Definition 2.1.1. We call expression of language to a finite sequence of n symbols of the alphabet, written in row:
Definition 2.1.2. For each function symbol n-aria , we indicate with T an internal n-aria operation in the expressions set , defined as: .
And we call term of language, any member generated by variables and constants, by the operations . If in language there are no function symbols, terms are variables and constants.
In language of Arithmetic, the following expressions are terms:
Defintion 2.1.3. It's said that an atomic formula will be given to an expression of the form , where is an n-ary predicate symbol and are terms.
Defintion 2.1.4. Let , , be internal operations of the expressions set , defined as:
, , .
A well formed formula (wff) will be given to any member of the set E generated by the atomic formulas, by the operations , ,
(atomic formula), (atomic formula), , , (), )
The previous example presents a constructive succession in the set E, with generators atomic formulas and operations , , .
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 . 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 , , . . Then, C is the set of all wffs.
Theorem 2.1.7. The set of all terms is freely generated
Proof.-
References