[ Pobierz całość w formacie PDF ]
only if £ |=(È ’! Á).
Definition 6.7. A formula È of L is a tautology if it is true in
every structure, i.e. if |= È. È is a contradiction if ¬È is a tautology,
i.e. if |= ¬È.
For some trivial examples, let Õ be a formula of L and M a structure
for L. Then M |= {Õ} if and only if M |= Õ, so it must be the case
that {Õ} |= Õ. It is also easy to check that Õ ’! Õ is a tautology and
¬(Õ ’! Õ) is a contradiction.
Problem 6.12. Show that "yy = y is a tautology and that "y ¬y =
y is a contradiction.
Problem 6.13. Suppose Õ is a contradiction. Show that M |= Õ[s]
is false for every structure M and assignment s : V ’!|M| for M.
Problem 6.14. Show that a set of formulas £ is satisfiable if and
only if there is no contradiction Ç such that £ |= Ç.
The following fact is a counterpart of Proposition 2.4.
Proposition 6.15. Suppose M is a structure for L and ± and ²
are sentences of L. Then:
1. M |= ¬± if and only if M ±.
2. M |= ± ’! ² if and only if M |= ² whenever M |= ±.
3. M |= ± (" ² if and only if M |= ± or M |= ².
4. M |= ± '" ² if and only if M |= ± and M |= ².
5. M |= ± ”! ² if and only if M |= ± exactly when M |= ².
6. M |= "x± if and only if M |= ±.
7. M |= "x± if and only if there is some m " |M| so that M |=
± [s(x|m)] for every assignment s for M.
Problem 6.16. How much of Proposition 6.15 must remain true
if ± and ² are not sentences?
6. STRUCTURES AND MODELS 39
Recall that by Proposition 5.14 a formula of a first-order language
is also a formula of any extension of the language. The following rela-
tionship between extension languages and satisfiability will be needed
later on.
Proposition 6.17. Suppose L is a first-order language, L is an
extension of L, and “ is a set of formulas of L. Then “ is satisfiable
in a structure for L if and only if “ is satisfiable in a structure for L .
One last bit of terminology . . .
Definition 6.8. If M is a structure for L, then the theory of M
is just the set of all sentences of L true in M, i.e.
Th(M) ={ Ä | Ä is a sentence and M |= Ä }.
If " is a set of sentences and S is a collection of structures, then " is
a set of (non-logical) axioms for S if for every structure M, M "S if
and only if M |=".
Example 6.4. Consider the sentence "x "y ((¬x = y) '""z (z =
x (" z = y)) of L=. Every structure of L= satisfying this sentence must
have exactly two elements in its universe, so {"x "y ((¬x = y)'""z (z =
x (" z = y)) } is a set of non-logical axioms for the collection of sets of
cardinality 2:
{ M | M is a structure for L= with exactly 2 elements}.
Problem 6.18. In each case, find a suitable language and a set of
axioms in it for the given collection of structures.
1. Sets of size 3.
2. Bipartite graphs.
3. Commutative groups.
4. Fields of characteristic 5.
40 6. STRUCTURES AND MODELS
CHAPTER 7
Deductions
Deductions in first-order logic are not unlike deductions in propo-
sitional logic. Of course, some changes are necessary to handle the
various additional features of propositional logic, especially quantifiers.
In particular, one of the new axioms requires a tricky preliminary def-
inition. Roughly, the problem is that we need to know when we can
replace occurrences of a variable in a formula by a term without letting
any variable in the term get captured by a quantifier.
Throughout this chapter, let L be a fixed arbitrary first-order lan-
guage. Unless stated otherwise, all formulas will be assumed to be
formulas of L.
Definition 7.1. Suppose x is a variable, t is a term, and Õ is a
formula. Then t is substitutable for x in Õ is defined as follows:
1. If Õ is atomic, then t is substitutable for x in Õ.
2. If Õ is (¬È), then t is substitutable for x in Õ if and only if t is
substitutable for x in È.
3. If Õ is (± ’! ²), then t is substitutable for x in Õ if and only if t
is substitutable for x in ± and t is substitutable for x in ².
4. If Õ is "y´, then t is substitutable for x in Õ if and only if either
(a) x does not occur free in Õ, or
(b) if y does not occur in t and t is substitutable for x in ´.
For example, x is always substitutable for itself in any formula
Õ and Õx is just Õ (see Problem 7.1). On the other hand, y is not
x
substitutable for x in "yx = y because if x were to be replaced by y,
the new instance of y would be captured by the quantifier "y. This
makes a difference to the truth of the formula. The truth of "yx = y
depends on the structure in which it is interpreted it s true if the
universe has only one element and false otherwise but "yy = y is
a tautology by Problem 6.12 so it is true in any structure whatsoever.
This sort of difficulty makes it necessary to be careful when substituting
for variables.
41
42 7. DEDUCTIONS
Definition 7.2. Suppose x is a variable, t is a term, and Õ is
a formula. If t is substitutable for x in Õ, then Õx (i.e. Õ with t
t
substituted for x) is defined as follows:
1. If Õ is atomic, then Õx is the formula obtained by replacing each
t
occurrence of x in Õ by t.
x [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl freetocraft.keep.pl
only if £ |=(È ’! Á).
Definition 6.7. A formula È of L is a tautology if it is true in
every structure, i.e. if |= È. È is a contradiction if ¬È is a tautology,
i.e. if |= ¬È.
For some trivial examples, let Õ be a formula of L and M a structure
for L. Then M |= {Õ} if and only if M |= Õ, so it must be the case
that {Õ} |= Õ. It is also easy to check that Õ ’! Õ is a tautology and
¬(Õ ’! Õ) is a contradiction.
Problem 6.12. Show that "yy = y is a tautology and that "y ¬y =
y is a contradiction.
Problem 6.13. Suppose Õ is a contradiction. Show that M |= Õ[s]
is false for every structure M and assignment s : V ’!|M| for M.
Problem 6.14. Show that a set of formulas £ is satisfiable if and
only if there is no contradiction Ç such that £ |= Ç.
The following fact is a counterpart of Proposition 2.4.
Proposition 6.15. Suppose M is a structure for L and ± and ²
are sentences of L. Then:
1. M |= ¬± if and only if M ±.
2. M |= ± ’! ² if and only if M |= ² whenever M |= ±.
3. M |= ± (" ² if and only if M |= ± or M |= ².
4. M |= ± '" ² if and only if M |= ± and M |= ².
5. M |= ± ”! ² if and only if M |= ± exactly when M |= ².
6. M |= "x± if and only if M |= ±.
7. M |= "x± if and only if there is some m " |M| so that M |=
± [s(x|m)] for every assignment s for M.
Problem 6.16. How much of Proposition 6.15 must remain true
if ± and ² are not sentences?
6. STRUCTURES AND MODELS 39
Recall that by Proposition 5.14 a formula of a first-order language
is also a formula of any extension of the language. The following rela-
tionship between extension languages and satisfiability will be needed
later on.
Proposition 6.17. Suppose L is a first-order language, L is an
extension of L, and “ is a set of formulas of L. Then “ is satisfiable
in a structure for L if and only if “ is satisfiable in a structure for L .
One last bit of terminology . . .
Definition 6.8. If M is a structure for L, then the theory of M
is just the set of all sentences of L true in M, i.e.
Th(M) ={ Ä | Ä is a sentence and M |= Ä }.
If " is a set of sentences and S is a collection of structures, then " is
a set of (non-logical) axioms for S if for every structure M, M "S if
and only if M |=".
Example 6.4. Consider the sentence "x "y ((¬x = y) '""z (z =
x (" z = y)) of L=. Every structure of L= satisfying this sentence must
have exactly two elements in its universe, so {"x "y ((¬x = y)'""z (z =
x (" z = y)) } is a set of non-logical axioms for the collection of sets of
cardinality 2:
{ M | M is a structure for L= with exactly 2 elements}.
Problem 6.18. In each case, find a suitable language and a set of
axioms in it for the given collection of structures.
1. Sets of size 3.
2. Bipartite graphs.
3. Commutative groups.
4. Fields of characteristic 5.
40 6. STRUCTURES AND MODELS
CHAPTER 7
Deductions
Deductions in first-order logic are not unlike deductions in propo-
sitional logic. Of course, some changes are necessary to handle the
various additional features of propositional logic, especially quantifiers.
In particular, one of the new axioms requires a tricky preliminary def-
inition. Roughly, the problem is that we need to know when we can
replace occurrences of a variable in a formula by a term without letting
any variable in the term get captured by a quantifier.
Throughout this chapter, let L be a fixed arbitrary first-order lan-
guage. Unless stated otherwise, all formulas will be assumed to be
formulas of L.
Definition 7.1. Suppose x is a variable, t is a term, and Õ is a
formula. Then t is substitutable for x in Õ is defined as follows:
1. If Õ is atomic, then t is substitutable for x in Õ.
2. If Õ is (¬È), then t is substitutable for x in Õ if and only if t is
substitutable for x in È.
3. If Õ is (± ’! ²), then t is substitutable for x in Õ if and only if t
is substitutable for x in ± and t is substitutable for x in ².
4. If Õ is "y´, then t is substitutable for x in Õ if and only if either
(a) x does not occur free in Õ, or
(b) if y does not occur in t and t is substitutable for x in ´.
For example, x is always substitutable for itself in any formula
Õ and Õx is just Õ (see Problem 7.1). On the other hand, y is not
x
substitutable for x in "yx = y because if x were to be replaced by y,
the new instance of y would be captured by the quantifier "y. This
makes a difference to the truth of the formula. The truth of "yx = y
depends on the structure in which it is interpreted it s true if the
universe has only one element and false otherwise but "yy = y is
a tautology by Problem 6.12 so it is true in any structure whatsoever.
This sort of difficulty makes it necessary to be careful when substituting
for variables.
41
42 7. DEDUCTIONS
Definition 7.2. Suppose x is a variable, t is a term, and Õ is
a formula. If t is substitutable for x in Õ, then Õx (i.e. Õ with t
t
substituted for x) is defined as follows:
1. If Õ is atomic, then Õx is the formula obtained by replacing each
t
occurrence of x in Õ by t.
x [ Pobierz całość w formacie PDF ]