Lecture #14, Nov, 4
0.0.1 Remark. We saw that a Boolean wff, is also a 1st-order wff.
We view Boolean formulas as abstractions of 1st-order ones.
How is this Abstraction manifesting itself?
Well, in any given 1st-order wff we just “hide” all 1st-order features. That is, look at any wff like the following three forms as Boolean variables.
1. t = s
2. φt1t2t3…tn 3. (∀x)A
Why so? You see, if you “live” inside Boolean logic, you know these configura- tions are “statements” but you cannot say what they say:
You do not understand the symbols.
So an inhabitant of Boolean logic can USE the above if connected with Boolean glue.
Examples.
• Youseethis“x=y→x=y∨x=z”as“ → ∨ ”where the first a and second box is the same —say variable p— while the last one is different. You recognize a tautology!
• You see this “x = x” as “ ”. Just a Boolean variable. Not a tautology.
• The same goes for this “(∀x)x = y → x = y” which the Boolean citizen views
as“ → ”,thatis,aBooleanwffp→q. Notatautology. Basic Logic© by George Tourlakis
1
(∀x)x = y
x=x
x=y
x=y
x=z
x=y
2
Process of abstraction: We only abstract the expressions 1.–3. above in order to turn a 1st-order wff into a Boolean wff.
The three forms above are know in logic as Prime Formulas.
Basic Logic© by George Tourlakis
More Boolean abstraction examples: • If A is
p → x = y ∨ (∀x)φx ∧ q note that q is not in the scope of (∀x) then we abstract as
p→ ∨ ∧q (1) so the Boolean citizen sees
p→p′ ∨p′′ ∧q
If we ask “show all the prime formulas in A by boxing them” then we —who understand 1st-order language and can see inside scopes— would have also boxed φx above. The Boolean citizen cannot see φx in the scope of (∀x) so the boxing for such a person would be as we gave in (1)
• First box all prime formulas in (2) below.
(∀x)(x = y → (∀z)z = a ∨ q)
Here it is.
Now abstract the above for Boolean inhabitants:
3
(∀x)(
x=y
→
(∀z)
z=a
∨q)
They see no glue at all! The abstraction is
• x=y→x=yabstractsas →
p
(∀x)(x = y → (∀z)z = a ∨ q)
. Thatis,p→p—atautology.
x=y
Why bother with abstractions? Well, the last example is a tautology so a Boolean citizen can prove it.
However x = x and (∀x)x = y → x = y are not tautologies and we need predicate logic techniques to settle their theoremhood.
Basic Logic© by George Tourlakis
(∀x)φx
x=y
x=y
4
We can now define:
0.0.2 Definition. (Tautologies and Tautological Implications) We say that a
(1st-order) wff, A, is a tautology and write |=taut A, iff its Boolean abstraction is.
In 1st-order Logic Γ |=taut A is applied to the Boolean abstraction of A and the
wff in Γ.
Goes without saying that ALL the identical occurrences of stand for the same Boolean variale.
Forexample,x=y|=taut x=y∨z=viscorrectasweseefrom ppq
in Γ ∪ {A} will
…
x=y|=taut x=y∨z=v
Basic Logic© by George Tourlakis
Substitutions
A substitution is a textual substitution.
In A[x := t] we will replace all occurrences of a free x in A by the term t: Find
and replace.
In A[p := B] we will replace all occurrences of a p in A by B: Find and replace.
0.0.3 Example. (What to avoid) Consider the substitution below (∃x)¬x = y[y := x]
If we go ahead with it as a brute force “find and replace” asking no questions, then we are met by a serious problem:
The result
says something other than what the original formula says!
The latter says “for any choice of y-value there is a fresh (i.e., other than y) new x-value”.
The above is true in any application of logic where we have infinitely many ob- jects. For example, it is true of real numbers and natural numbers.
(1) though is NEVER true! It says that there is an object that is different from
itself!
0.0.4 Definition. (Substitution) Each of
(∃x)¬x = x (1)
1. In A[x := t] replace all occurrences of a free x in A by the term t: Find and replace.
2. In A[p := B] replace all occurrences of a p in A by B: Find and replace.
Basic Logic© by George Tourlakis
5
6
dictates that we do a find and replace.
However we abort the substitution 1 or 2 if it so happens that going ahead with it makes a free variable y of t or B bound because t or B ended up in the scope of a (∀y) or (∃y).
We say that the substitution is undefined and that the reason is that we had a “free variable capture”.
There is a variant of substution 2, above:
3. In A[p \ B] replace all occurrences of a p in A by B: Find and replace.
For technically justified reasons to be learnt later, we never abort this one, capture or not. We call the substitutions 1. and 2. conditional, while the substitution 3.
unconditional.
There is NO unconditional version of 1.
[x := t], [p := B], [p \ B] have higher priority that all connectives ∀, ∃, ¬, ∧, ∨, → , ≡. They associate from LEFT to RIGHT that is A[x := t][p := B] means
Basic Logic© by George Tourlakis
A[x:=t] [p:=B]
0.0.5 Example. Several substitutions based on Definition 0.0.4.
(1) (y = x)[y := x].
The red brackets are META brackets. I need them to show the substitution applies to the whole formula.
The result is x = x.
(2) (∀x)x = y[y := x]. By 0.0.4, this is undefined because if I go ahead then x
is captured by (∀x).
(3) (∀x)(x = y)[y := x]. According to priorities, this means (∀x)(x = y)[y :=
x].
That is, “apply the quantifier (∀x) to x = x”, which is all right.
Result is (∀x)x = x.
(4) (∀x)(∀y)φ(x, y)[y := x]. This says
•Do (∀x)(∀y)φ(x,y) [y:=x]
• This is all right since y is not free in (∀y)φ(x, y) —so not found; no replace!
Result is the original formula UNCHANGED.
(5) z = a ∨ (∀x)x = y[y := x]. Abort: x is captured when we attempt substi- tution in the subformula (∀x)x = y.
(6) (∀x)p[p \ x = y] Unconditional substitution. Just find and replace, no questions asked!
Result: (∀x)x = y.
Basic Logic© by George Tourlakis
7
8
(7) (∀x)p[p := x = y] Undefined. x in x = y will get captured if you go
ahead!
Basic Logic© by George Tourlakis
0.0.6 Definition. (Partial Generalisation) We say that B is a partial generali- sation of A if B is formed by adding as a PREFIX to A zero or more strings of the
form (∀x) for any choices whatsoever of the variable x —repetitions allowed.
0.0.7 Example. Here is a small list of partial generalisations of the formula x = z:
x = z,
(∀w)x = z,
(∀x)(∀x)x = z,
(∀x)(∀z)x = z,
(∀z)(∀x)x = z, (∀z)(∀z)(∀z)(∀x)(∀z)x = z.
Basic Logic© by George Tourlakis
9
10
0.1. Axioms and Rules for Predicate Logic
0.1.1 Definition. (1st-Order Axioms) These are all the partial generalisations of all the instances of the following schemata.
1. All tautologies
2. (∀x)A → A[x := t]
Note that we get an instance of this schema ONLY IF the substitution is not
aborted.
3. A → (∀x)A —PROVIDED x is not free in A.
4. (∀x)(A → B) → (∀x)A → (∀x)B
5. x = x
6. t=s→(A[x:=t]≡A[x:=s])
The set of all first-order axioms is named “Λ1” —“1” for 1st-order. Our only INITIAL (or Primary) rule is Modus Ponens:
A, A → B B
You may think that including all tautologies as axioms is overkill. However
(MP)
1. It is customary to do so in the literature ([Tou08, Sho67, End72, Tou03])
2. After Post’s Theorem we do know that every tautology is a theorem of Boolean logic. Adopting axiom one makes every tautology also a theorem of Predicate Logic outright!
This is the easiest way to incorporate Boolean logic as a sublogic of 1st-order logic.
Basic Logic© by George Tourlakis
Bibliography
[End72] Herbert B. Enderton, A mathematical introduction to logic, Academic Press, New York, 1972.
[Sho67] Joseph R. Shoenfield, Mathematical Logic, Addison-Wesley, Reading, Mas- sachusetts, 1967.
[Tou03] G. Tourlakis, Lectures in Logic and Set Theory; Volume 1: Mathematical Logic, Cambridge University Press, Cambridge, 2003.
[Tou08] , Mathematical Logic, John Wiley & Sons, Hoboken, NJ, 2008.
Basic Logic© by George Tourlakis