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 T₁ and T₂ be two theories in a language L. Suppose that for each structure A adequate for L, A |= T₁ if and only if A2 T₂. Then T₁ and T₂ 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 p₀,p₁,p₂, 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 p_i for all and only the p_is 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 Ramseys 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]² {0,1} there exists a set H [1,,n] such that |H| m and |H| > min(H) and f is constant on [H]².

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 x₁,,x_n such that x_i is adjacent to x_i+1 for each 1 i < n and x_n is adjacent to x₁. 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: {A_n : n N} where A_n expresses There is no star of cardinality 2n (i.e., There are no 2n distinct elements forming a star).

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 {A_n : n N} where A_n 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) then there is a non-standard element a A such that 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 ` xA(x).

Exercise 2.1. Prove that -consistency implies consistency.

Exercise 2.2. Consider Godels unprovable sentence G for some theory T MA, satisfying:

T ` G ↔ xProof_T(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:

• I am decidable in MA (i.e. either provable or disprovable).
• I am undecidable in MA.
• I am not refutable in MA (i.e. I am consistent with MA).
• 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 ₀ (i.e., with bounded quantifiers only), if for all n N we have T ` R(n), then T 0 xR(x). Let T be a theory in the language of arithmetic such that for every sentence E of type <sub>1</sub>, 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 ₁ true in N, T {A,E} is consistent. (A sentence of type ₁ is of the form x₁ x_kH where H contains only bounded quantifiers. Note that the negation of a ₁ formula is ₁, 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 Tarskis Theorem (on the non-representability of the theorems of a theory within a theory proved in class) the following version of Godels 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 ₁-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).

• If MA ` E then MA 6|= E.
• If there exists a structure A such that A |= MA and A |= E then N 6|= E.
• If N |= E then MA {E} has not models.
• If N 6|= E then MA0 E.
• If N 6|= E then MA0 E.
• If N |= A B then, if MA ` A, then MA ` B.