Description
1. Compactness
Exercise 1.1. Let T be a theory that axiomatizes a property P of structures. Prove that if P is also finitely
axiomatizable then P is finitely axiomatizable by a subset of T.
Exercise 1.2. Let T1 and T2 be two theories in a language L. Suppose that for each structure A adequate
for L, A |= T1 if and only if A 2 T2. Then T1 and T2 are finitely axiomatizable.
(Hint: Reason by way of contradiction and use the Compactness Theorem to obtain a model of an
unsatisfiable theory).
Exercise 1.3. Show that the property of being a non-bipartite graph is not finitely axiomatizable.
(Hint: use a particular property of bipartite graphs concerning cycles and a standard Compactness
argument).
Exercise 1.4. Let < be a strict total order on a set X (that is, < is anti-symmetric, irreflexive and total).
We call such a relation nice if it admits no infinite decreasing sequences. Prove by a Compactness argument
that the notion of being a nice relation is not axiomatizable.
Exercise 1.5. Prove the following: If a property P and its complement are axiomatizable then P is finitely
axiomatizable.
Exercise 1.6. Let p0, p1, p2, . . . be the list of all prime numbers in increasing order. Show that for any
subset S ⊆ N there is a model of arithmetic (i.e. a model of all sentences true in the standard model) that
contains an element c such that c is divisible by pi for all and only the pis such that i ∈ S.
(Hint: use an extra constant and Compactness)
Exercise 1.7. Let T be a theory that has some finite models and some infinite models. Let E be a sentence
such that is A |= T and A is infinite then A |= E. Show that there is a bound b ∈ N such that if A |= T and
A is of cardinality ≥ b then A |= E.
(Hint: Compactness and some of its corollaries).
Exercise 1.8. Assuming the Infinite Ramsey’s Theorem give a proof by Compactness of the following
principle:
For all m, there exists an n such that for all colorings f : [1, . . . , n]
2 → {0, 1} there exists a set H ⊆
[1, . . . , n] such that |H| ≥ m and |H| > min(H) and f is constant on [H]
2
.
Exercise 1.9. Consider the class of undirected graphs with no self-loop.
A graph is acyclic if, for each n ≥ 3 it does not contain distinct vertices x1, . . . , xn such that xi
is adjacent
to xi+1 for each 1 ≤ i < n and xn is adjacent to x1. Prove that the property of being an acyclic graph is
not finitely axiomatizable in the first-order language of graphs.
(Hint: Use Compactness).
Exercise 1.10. A subset S of vertices of an undirected graph is called a star if there exists an element
v ∈ S such that for each other w ∈ S, w is adjacent to v and to no other vertex.
The property P of “not containing a star of even cardinality” is axiomatizable in the language of graphs
by the following theory: {An : n ∈ N} where An expresses “There is no star of cardinality 2n” (i.e., “There
are no 2n distinct elements forming a star”).
1
Is ¬P axiomatizalbe?
Is P finitely axiomatizable?
Exercise 1.11. A strict total order on a set X (i.e., an anti-symmetric, reflexive and total) binary relation
is called a well-ordering if it admits no infinite strictly decreasing sequences. Prove that the property of
being a well-ordering is not axiomatizable (in the language of orders).
(Hint: Expand by constant(s) and use Compactness).
Exercise 1.12. A subset S of vertices of an undirected graph is called a clique if each vertex in S is adjacent
to any other vertex in S. The property P of “not containing cliques of even cardinality” is axiomatizable in
the language of graphs by the theory {An : n ∈ N} where An expresses “There is no clique of cardinality
2n”.
Is ¬P axiomatizable?
Is P finitely axiomatizable?
Exercise 1.13. In the language L containing the symbol R(x, y) (and identity = as a logical symbol) write
a sentence E such that the following set
S = {n ∈ N+ : esiste A t.c. A |= E e |A| = n}
is the set of even positive integers (N+ denotes the set of positive integers).
Does E finitely axiomatize the property of having even cardinality domain?
(Hint: axiomatize R as a special equivalence relation.)
Exercise 1.14. Is there a theory T with infinite models, at least one finite model but such that T does not
have finite models of arbitrarily high cardinality?
Exercise 1.15. Let A be a non-standard model of arithmetic and let F(x) be a formula with one free
variable. If it is the case that for infinitely many n ∈ N we have A |= F[
x
n¯A
) then there is a non-standard
element a ∈ A such that A |= F[
x
a
]. In other words: if a formula is satisfied by infinitely many standard
numbers then it is satisfied also by a non-standard number.
(Hint: reason on the properties of sets that are definable in a non-standard model of arithmetic).
2. Group 2
Recall that a theory T is ω-consistent if there is not formula A(x) such that for all n ∈ N, T ` A(n) and
T ` ∃x¬A(x).
Exercise 2.1. Prove that ω-consistency implies consistency.
Exercise 2.2. Consider G¨odel’s unprovable sentence G for some theory T ⊇ MA, satisfying:
T ` G ↔ ∀x¬P roofT (x, code(G)).
Prove that if T is consistent then T + {¬G} is consistent but not ω-consistent.
Exercise 2.3. Apply the fix-point theorem to obtain sentences in the language of arithmetic that express
the following:
(1) I am decidable in MA (i.e. either provable or disprovable).
(2) I am undecidable in MA.
(3) I am not refutable in MA (i.e. I am consistent with MA).
(4) I am provable in MA.
For each of the above say as much as possible of the following questions: Is the sentence provable, refutable
or undecidable? Is the sentence true in the standard model?
Exercise 2.4. A theory T is called 1-consistent if the following holds: For every formula R(x) of type ∆0
(i.e., with bounded quantifiers only), if for all n ∈ N we have T ` R(n), then T 0 ∃x¬R(x). Let T be a
theory in the language of arithmetic such that for every sentence E of type Σ1, if N |= E then T ` E. Prove
that, for every sentence A, T ∪ {A} is 1-consistent if and only if for every sentence E of type Π1 true in N,
T ∪ {A, E} is consistent. (A sentence of type Π1 is of the form ∀x1 . . . ∀xkH where H contains only bounded
quantifiers. Note that the negation of a Σ1 formula is Π1, and viceversa).
Exercise 2.5. Recall the Rosser sentence (see handout notes).
E := (∀y)(F(m, y) → (∃z)(z ≤ y ∧ H(m, z))),
where m is the code of the formula (∀y)(F(x, y) → (∃z)(z ≤ y ∧ H(x, z))) F represents the relations R and
H represents the relation S introduced in the handouts. Show that if T ⊇ MA is consistent then T 0 E and
T 0 ¬E. One can prove that if T is consistent then ¬E is not provable.
Exercise 2.6. Deduce from Tarski’s Theorem (on the non-representability of the theorems of a theory within
a theory – proved in class) the following version of Godel’s Theorem: If T is an ω-consistent decidable set of
sentence extending MA then T is incomplete. 7
(Hint: use the fact that the relation (a, b) ∈ R iff “a is the code of a proof in T of sentence coded by b”
is computable).
Exercise 2.7. Argue that if F is a Σ1-sentence then if N |= F then MA ` F. (You can consider F with just
one existential quantifier). Argue that this implies that for some class of sentences of arithmetic, if T 0 ¬E
then E is true.
Exercise 2.8. Indicate whether the following points are true or false assuming that MA is consistent, and
explain why (E is a sentence in the language of MA).
(1) If MA ` E then MA 6|= ¬E.
(2) If there exists a structure A such that A |= MA and A |= E then N 6|= ¬E.
(3) If N |= E then MA ∪ {¬E} has not models.
(4) If N 6|= E then MA 0 E.
(5) If N 6|= E then MA 0 ¬E.
(6) If N |= A → B then, if MA ` A, then MA ` B.
3