Lecture #13, Continued; Oct. 30
Extending Boolean Logic
Boolean Logic can deal only with the Boolean glue: properties and behaviour.
Can certify tautologies, but it misses many other truths as we will see, like x = x where x stands for a mathematical object like a matrix, string, array, number, etc.
One of the obvious reasons is that Boolean logic cannot even “see” or “speak” about mathematical objects.
If it cannot see or speak about them, then naturally cannot reason about them either!
1
Basic Logic© by George Tourlakis
2
E.g, we cannot say inside Boolean logic the sentence “every natural number
greater than 1 has a prime factor”.
Boolean Logic does not know what “every” means or what a “number” is, what “natural” means, what is “1”, what “greater” means, what “prime” is, or what “fac- tor” is.
In fact it is worse than not “knowing”: It cannot even say any one of the concepts listed above.
Its alphabet and language is extremely limited.
We need a richer language!
Basic Logic© by George Tourlakis
0.0.1 Example. Look at these two math statements. The first says that two sets are equal iff they have the same elements. The second says that any object is equal to itself.
We read “(∀x)” below as “for all values of x”, usually said MORE SIMPLY as, “for all x”.
and
(∀y)(∀z)(∀x)(x ∈ y ≡ x ∈ z) → y = z (1) x=x (2)
Boolean Logic is a very high level ( = very non-detailed) abstraction of Mathe- matics.
Since Boolean Logic cannot see object variables x,y,z, cannot see ∀ or =, nor can penetrate inside the so-called “scope” of (∀z) —that is, the big brackets above— it myopically understands each (1) and (2) as atomic statements p and q (not seeing inside the scope it sees no “glue”).
Thus Boolean logic, if forced to opine about the above it will say none of the above is a theorem (by soundness).
Yet, (1) is a theorem of Set Theory and (2) is an axiom in ALL mathematics.
3
Says: “Every object is equal to itself.”
Basic Logic© by George Tourlakis
4
Enter First-Order Logic or Predicate Logic.
Predicate logic is the language AND logic of mathematics and mathematical sci- ences.
In it we CAN “speak” (1) and (2) above and reason about them. 0.1. The language of First-Order Logic
What symbols are absolutely necessary to include in the Alphabet, V1 —the sub- script “1” for “1st-order”— of Predicate Logic?
Well, let us enumerate:
0.1.1 Definition. (The 1st-order alphabet; first part)
1. First of all, we are EXTENDING, NOT discarding, Boolean Logic. So we include in V1 all of Boolean Logic’s symbols p, ⊥, ⊤, (, ), ¬, ∧, ∨, →, ≡, where p stands for any of the infinitely many Boolean variables.
2. Then we need object variables —that is variables that stand for mathematical objects— x, y, z, u, v, w with or without primes or subscripts. So, these are infinitely many.
Metanotation that stands for any of them will be bold face, but using the same letters with or without primes or subscripts: x, x′′ , y, w′′′ , etc.
3. Equality between mathematical objects: =
4. New glue: ∀
We call this glue universal quantifier. It is pronounced “for all”.
Is that all? No. But let’s motivate with two examples.
Basic Logic© by George Tourlakis
5 123
0.1. The language of First-Order Logic 5 0.1.2 Example. (Set theory) The language of set theory needs also a binary re-
lation or predicate up in front: Denoted by “∈”. BUT nothing else.
All else is “manufactured” in the theory, that is, introduced by definitions.
The manufactured symbols include constants like our familiar N (the set of natural numbers, albeit set theorists often prefer the symbol “ω”), our familiar constant “∅” (the empty set).
Also include functions like ∪, ∩ and relations or predicates like ⊂, ⊆.
So set theory needs no constants or functions up in front to
start “operating” (proving theorems, that is).
Basic Logic© by George Tourlakis
6
0.1.3 Example. (Number theory) The language of Number theory —also called Peano arithmetic— needs —in order to get started:
• A constant, the number zero: 0
• A predicate (“less than”): <
• A unary function: “S”. (This, informally/intuitively is the “successor function” which with input x produces output x + 1.)
• Two binary functions, “+, ×” with the obvious meaning.
All else is “manufactured” in the theory, that is, introduced by definitions.
The manufactured symbols include constants like our familiar 1, 2, 1000234000785.
Also include functions like xy,⌊x/y⌋ and more relations or predicates like ≤.
Basic Logic© by George Tourlakis
0.1. The language of First-Order Logic 7
We will do logic for the user, that is, we are aiming to teach the USE of logic. But will do so without having to do set theory or number theory or any specific
mathematical theory (geometry, algenra, etc.).
So equipped with our observations from the examples above, we note that various
theories start up with DIFFERENT sets of constants, functions and predicates.
So we will complete the Definition 0.1.1 in a way that APPLIES TO ANY AREA
OF MATHEMATICAL APPLICATION.
Basic Logic© by George Tourlakis
8
0.1.4 Definition. (The 1st-order alphabet; part 2) Our 1st-order alphabet also includes the following symbols
(1) Symbols for zero or more constants. Generically, we use a, b, c, d with or without primes or subscripts for constants.
(2) Symbols for zero or more functions. Generically we use f,g,h with or without primes or subscripts for functions.
Each such symbol will have the need for a certain number of arguments, this number called the function’s “arity” (must be ≥ 1). For example, S has arity 1; it is unary. Each of +, × have arity two; they are binary.
(3) Symbols for zero or more predicates, generically denoted as φ, ψ, with or without primes or subscripts.
Each predicate symbol will have the need for a certain number of arguments
called it “arity” (must be ≥ 1). For example, < has arity 2.
Basic Logic© by George Tourlakis
0.1. The language of First-Order Logic 9 The first-order LANGUAGE is a set of strings of two types —terms and formu-
las— over the alphabet 0.1.1 – 0.1.4.
By now we should feel comfortable with first-order inductive definitions.
In fact we gave inductive definitions of first-order Boolean formulas and used it
quite a bit, but also more recently gave an inductive definition of Boolean proofs. Thus we introduce first-order Terms, that denote objects, and first-order formu-
las, that denote statements, inductively in two separate definitions.
Basic Logic© by George Tourlakis
10
First terms:
0.1.5 Definition. (Terms)
A term is a string over the alphabet V1 that satisfies one of:
(1) It is just an object variable x (recall that x is metanotation and stands for any
object variable).
BTW, we drop the qualifier “object” from “object variable” from now on, but RETAIN the qualifier “Boolean” in “Boolean variable”.
(2) An object constant a (this stands for any constant —generically).
BTW, we ALSO drop the qualifier “object” from “object constant” from now
on, but RETAIN the qualifier “Boolean” in “Boolean constant”. (3) General case. It is a string of the form ft1t2 . . . tn where the function symbol f
has arity n.
We will denote arbitrary terms generically by the metasymbols t, s with or without
primes or subscripts.
Basic Logic© by George Tourlakis
0.1. The language of First-Order Logic 11 We will often abuse notation and write “f(t1, t2, . . . , tn)” for “ft1t2 . . . tn”.
This is one (rare) case where the human eye prefers extra brackets! Be sure to note that the comma “,” is not in our alphabet!
Examples from number theory.
x, 0 are terms. x + 0 is a term (abuse of the actual “+x0” notation).
(x+y)×z is a term (abuse of the actual ×+xyz).
Basic Logic© by George Tourlakis
12
With the concept of terms out of the way we now define 1st-order formulas: First the Atomic Case:
0.1.6 Definition. (1st-order Atomic formulas) The following are the atomic for- mulas of 1st-order logic:
(i) Any Boolean atomic formula.
(ii) The expression (string) “t = s”, for any choice of t and s (probably, the t and
s name the same term).
(iii) Foranypredicateφofarityn,andanyntermst1,t2,...,tn,thestring“φt1t2...tn”.
We denote the set of all atomic formulas here defined AF.
0.1.7 Remark.
(1) As in the case of “complex” terms ft1t2 ...tn, we often abuse notation using
“φ(t1, t2, . . . , tn)” in place of the correctly written “φt1t2 . . . tn”.
(2) The symbol “=” is a binary predicate and is always written as it is here (never
“φ, ψ”).
(3) We absolutely NEVER confuse “=” with the “glue” “≡”.
They are more different than apples and oranges!
Basic Logic© by George Tourlakis
0.1. The language of First-Order Logic 13 0.1.8 Definition. (1st-order formulas) A first-order formula A —or wff A— is
one of
We let context fend for us as to what formulas we have in mind when we say “wff”.
From here on it is 1st-order ones!
If we want to talk about Boolean wff we WILL USE the qualifier “Boolean”! (1) A member of 1st-order AF set —in particular it could be a Boolean atomic wff!
(2) (¬B)ifBisawff.
(3) (B◦C)ifBandCarewff,and◦isoneof∧,∨,→,≡. (4) ((∀x)B), where B is a wff and x any variable.
TWO things: (1) we already agreed that “variable” means object variable oth- erwise I’d say “Boolean variable”. (2) Nowhere in the definition is required that
x occurs in B as a substring.
We call “∀” the universal quantifier.
The configuration (∀x) is pronounced “for all x” —intuitively meaning “for all
values of x” rather than “for all variables x, y′′, z′′′ , . . . that x may stand for”. 1234009
We say that the part of A between the two red brackets is the scope of (∀x). Thus the x in (∀x) and the entire B are in this scope.
The “in particular” observation in (1) and the cases (2) and (3) make it clear that every Boolean wff is also a (1st-order) wff.
Basic Logic© by George Tourlakis
14
0.1.9 Example. x = y and p are wff. The second one is also a Boolean wff.
((∀x)((∀y)(¬x=y)))isawff. Notethat¬in(¬x=y)appliestox=yNOTtox!
Glue cannot apply to an object like x. Must apply to a statement (a wff)!
((∀y)((¬x = y) ∧ p)) and (((∀y)(¬x = y)) ∧ p) are also formulas.
BTW, in the two last examples: p is in the scope of (∀y) in the first, but not so
in the second.
Basic Logic© by George Tourlakis
0.1. The language of First-Order Logic 15
0.1.10 Definition. (Existential quantifier)
It is convenient —but NOT NECESSARY— to introduce the “existential quan- tifier”, ∃.
This is only a metatheoretical abbreviation symbol that we introduce by this Def- inition, that is, by a “naming”
For any wff A, we define ((∃x)A) to be short for
¬ (∀x)(¬A) (1) We pronounce ((∃x)A) “for some (value of) x, A holds”.
The intuition behind this ((∃x)A) naming is captured by the diagram below make A false
it is not the case that
(¬A)
¬
(∀x)
all values of x
The scope of (∃x) in
is the area between the two red brackets.
(∃x)A
In particular, the leftmost x in (2) is in the scope.
(2)
Basic Logic© by George Tourlakis
16
Priorities Revisited
We augment our priorities table, from highest to lowest: equal priorities
∀,∃,¬ ,∧,∨,→,≡
Associativities remain right! Thus, ¬(∀x)¬A is a short form of (1) in 0.1.10. Another example: (u = v → (((∀x)x = a) ∧ p)) simplifies into
u = v → (∀x)x = a ∧ p
More examples:
(2) Instead of ((∀z)(¬x = y)) we write (∀z)¬x = y
(3) Instead of ((∀x)((∀x)x = y)) we write (∀x)(∀x)x = y
Basic Logic© by George Tourlakis
0.1. The language of First-Order Logic 17 BOUND vs FREE.
0.1.11 Definition. A variable x occurs free in a wff A iff it is NOT in the scope of a (∀x) or (∃x).
A bound variable x in (∀x)A other than the one in the displayed (∀x), belongs to the displayed leftmost “(∀x)” iff x occurs free in A.
We apply this criterion to subformulas of A of the form (∀x)(. . .) to determine
where various bound x found inside A belong. 0.1.12 Example. Consider
A
(∀x) (x = y → (∀x)x = z))
Here the red x in A belongs to the red ∀x. The black x belongs to the black ∀x.
Basic Logic© by George Tourlakis