MLCS-Homework 4 Solved

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 A2 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”).

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 ) 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 ` ∃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¬ProofT(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 MA0 E.

(5)   If N 6|= E then MA0 ¬E.

(6)   If N |= A → B then, if MA ` A, then MA ` B.