Logic and Set Theory

Question 1

Define the set of propositions. Define a valuation. Show that valuations are uniquely specified by the primitive props, and any such specification works.

State the three axioms of propositional logic. State and prove the deduction theorem. State and prove the Soundness theorem.

Question 2

State and prove the Adequacy theorem and show it is equivalent to another important result.
Name and prove this other result. Hence state and prove completeness, compactness, and decidability.

Answer 2

Adequecy: If S |= p, the S |- p. (If every model of S is a model of p, you can prove p from S).
Model existence: If S is consistent, then S has a model.

Adequecy ==> Model existence, since if S doesn’t have a model, then every model of S is a model of false, so S |= false, so S |- false, so S is inconsistent.

Model existence ==> Adequecy. Suppose S|=p. Suppose S union {not p} is consistent. Then it has a model, which is a model of S and not p, contradiction. Thus S union {not p} proves false. So S proves {not p} ==> false. So S proves p by axiom 3.

Proof of the model existence lemma:

1. Note that is S consistent, p a prop, one of S u {p} or S u {not p} is consistent. Indeed if both aren’t, then S proves (p==> false) and (p==>false)==>false and hence by MP S |- false.
2. The set of all props is ctble (if we start with ctbly many prims) so list as t_n, n>=1. Set S_0=S, S_n = S u {t_n} or S u {not t_n} such that S_n is consistent. Set S^bar the union of S_n.
3. Note S^bar consistent since proof are finite and S_n are consistent. Note S^bar is deductively closed, since if S^bar proves p but S^bar doesn’t contain p, then S^bar contains not p, hence is not consistent.
4. Define v that sets v(t)=1 iff t in S^bar. Note that v(false)=0 since false isn’t in S^bar.

For p==>q,
(i) if v(p)=1,v(q)=0, then p==>q can’t be in S^bar (otherwise q would be by MP).
(ii) if v(q)=1, then by axiom 1, q==>(p==>q), we get p==>q in S^bar.
(iii) if v(p)=0, not p is in S^bar. Its enough to show that (p==>false) |- (p==>q), so its enough to show {false} |- q.
By axiom 3, |- (not not q)==>q.
By axiom 1, |- false ==> ((q==>false)==>false) i.e., |- false ==> (not not q)
Thus |- false ==> q. Thus {false} |- q.

Completeness: S|-p iff S|=p. Proof: Adequeacy+soundness.

Compactness V1: If S entails p, then some finite subset T of S entails p.
Compactness V2: If every finite subset of S has a model, then S has a model.

V2 ==> V1. Indeed, if S entails p, S u {not p} has no models, and so some finite subset Tu{not p} has no models. Thus T entails p.

Decidability: If S a finite set of props, there is a finite time algorithm to decide if S proves t.

Question 3

State and prove “proof by induction.” Show isomorphisms between well orderings are unique.

Answer 3

Proof by induction: Let X a well-ordering, and S a subset of X such that if y in S for all y < x, then x in S. Then S=X.
Proof: pick the least element of X\S, contradiction.

Uniqueness of isomorphism. let f,g:X–>Y isomorphisms. We show f(x)=g(x) for all x by induction. Indeed, let S = Y \ {f(y):y a, then x > f^{-1}(a), a contradiction. Thus, f(x)=a. So f(x)=g(x).

Question 4

Define an initial segment. State and prove Definition by Recursion.

Answer 4

Definition by recursion. Let X a well-ordering, Y a set. For any G: P(XxY)–>Y, there is f : X–>Y such that for all x in X, f(x)=G(f restricted to I_x). Moreover, f is unique.

This weird definition just says, given (y,f(y)) for all yY for some initial segment I of X, and for all x in I, h(x)=G(h restricted to I_x). If h, h’ are two attempts defined at x, then h(x)=h’(x).
2. Indeed, if h(y)=h’(y) for all y

Question 5

1. State and prove subset collapse.
2. For well-orders X,Y define what X <= Y means. Show that X<=Y or Y<=X for any two well orders.
3. If X<=Y and Y<=X, then X and Y are isomorphic.

Answer 5

1. If S a subset of a well-order X, then S is isomorphic to a unique initial segment of X, and this isomorphism is unique.

Proof: Note that S is a well-order. A function f : S–>X is an isomorphism to an initial segment iff for all x, f(x)=min(X{f(y):y}). This is a definition by recursion. Note this set is non-empty, since by induction f(x) <= x. So we get existence and uniqueness.

Officially, we let
f(x)={min(X{f(y):yY by recursion, f(x)=min(Y{f(y):yY, g:Y–>X. so gf:X–>X is an isomorphism from X to an initial segment. By uniqueness in subset collapse, this initial segment is X. so gf=id. Similarly fg=id.

Question 6

1. Define an ordinal.
2. Show that for any ordinal alpha, the ordinals less than alpha (I_{alpha}) form a well-ordered set of order type alpha.
3. Show that any non-empty set of ordinals has a least element.
4. Show that the ordinals do not form a set.
5. State and prove Hartog’s Lemma. Define omega_1 and define gamma(X).

Answer 6

2. We’ve seen every well ordering < X are isomorphic to an initial segment of X. Thus the ordinals less than alpha are the proper initial segments of X, which are all of the form I_x={y:y

Question 7

Define ordinal addition inductively. Show that the inductive addition is assoc. Define ordinal addition synthetically and prove it equals the inductive definition. Do the same for multiplication.

Question 8

1. beta <= gamma ==> alpha+beta <= alpha+gamma
2. beta < gamma ==> alpha+beta < alpha+gamma
3. beta < gamma =!=> beta+alpha < gamma+alpha
4. If alpha >= beta, there is unique gamma, beta+gamma=alpha.
5. alpha(beta+gamma) = alphabeta+alpha*gamma.
6. (beta+gamma)alpha = betaalpha+gamma*alpha is not always true.
7. alpha^{beta+gamma}=alpha^beta * alpha^gamma

Moral: Things are as nice as you like on the right. Things always go wrong on the left.

Question 9

State Zorn. Prove Zorn assuming AC. Sketch a proof that every vector space has a basis. Sketch a proof of the model existence lemma for arbitrary primitives.

Question 10

State AC formally. Prove Zorn ==> AC. State the Well-Ordering Principle. Show AC <==> Well-ordering.

Question 11

Give languages and theories that axiomatize

• groups
• fields
• graphs
• posets

Question 12

Show that the theory of finite groups cannot be axiomatized.
Show that a theory with arbitrary large finite models has an infinite model.
Show that the theory of char(p) fields cannot be axiomatized.

Question 13

State and prove the Upward Lowenheim theorem.

State and “prove” the Downard Lowenheim theorem.

Answer 13

Upper: Let S a theory with an infinite model. Then S has an uncountable model.

Proof: Pick some uncountable set I and add constants c_i, i in I to the language, then add axioms c_i != c_j for each i!=j to give a new theory T. Note that any finite subset B of T can only mention finitely many of the c_i. In particular, the infinite model of S is a model of B. Thus T has a model, which must be uncountable.

Lower: Let L a countable language (i.e., the number of functions and relations are countable) and S a theory with an infinite model. Then S has a countable model.
Proof: The model constructed in the model existence lemma is countable.

Question 14

Define a transitive set and show that every x is contained in one. Define the transitive closure of x.

Observe that transitive sets are not automatically totally ordered (as you once thought despite the THM that trivially says the opposite)

Answer 14

A transitive set is a set x such that if y in x, then y is a subset of x.

Let x a set. We define an attempt f by
f is a function, dom(f) in omega, dom(f) not empty, f(0)=x, and for all n, n in omega and n in dom(f) ==> f(n)=Uf(n-1)

1. Two attempts agree where defined. The proof is by omega induction.
2. For all n in omega, there is an attempt defined at n.
3. Our function class is then p(y,z) = there exists f, f is an attempt and y in dom(f) and z=f(y).
4. This function class sends 0 |–> x, 1 |–> Ux, 2 |–> UUx, etc. Then by replacement the image of this function class is {x, Ux, UUx, ..}. Taking the union gives a transitive set that contains x.

The transitive closure is the least transitive set containing x, noting that the intersection of transitive sets remains transitives.

{0, {0}, {{0}}}, where 0 is the empty set. This set is transitive, and models the relation: {(a,b), (b,c)}.

Question 15

State and prove the principle of epsilon-induction.

Show that epsilon-induction implies foundation.

State and prove epsilon-recursion.

Explain how epsilon can be replaced by a relation satisfying two properties which you should define and name.

Answer 15

Epsilon-induction: For all t1,…,tn, [ (for all x) ((for all y) y in x and p(y))==>p(x)] ==> (for all x) p(x).

Fix t_1,…,t_n and suppose some x has not p(x). Then let u=TC({x}). Then the set {y in u: not p(y)} is non-empty, hence has an eps minimal element by foundation. Let this by y. By epsilon minimality, for all z in y, p(z). Thus p(y), contradiction.

epsilon-foundation ==> FDN

Call x regular if every y containing x has an epsilon minimal element. Let for all y in x, y regular. Let x in z. If x is epsilon-minimal in z, done. Otherwise, some y in z is also in x. So y is regular. So z has an epsilon-minimal element.

Epsilon-recursion: Let G a function class defined on all sets. Then there exists a function class F such that F(x)=G(F|x). Moreover, F is unique.

Proof:
We say f is an attempt if
f is a function, dom(f) is transitive, for all x in dom(f), f(x)=G(f|x), noting f|x is indeed a set, since f|x={(y,f(y)) : y in x} which is a set by replacement.

We have that all attempts defined at a point x agree, by epsilon-induction on x. Moreover, for all x, there is an attempt defined at x. Indeed, assume so for all y in x. Then we know for all y in x, there is a unique attempt f_y with domain TC({y}). Set f’ =U f_y. Then set f=f’ U {(x,G(f|x))}. f is a function defined on TC({x}) and is an attempt. Then finally our function class is just p(x,y)={there is an attempt f defined at x and f(x)=y}.

For uniqueness, we use epsilon-induction. i.e., if F and F’ are two function classes satisfying the requirements, do epsilon-induction on x that F(x)=F’(x).

eps can be replaced by an arbitrary relation class R defined by formula p. i.e., (x,y) in R iff p(x,y) if

R is well-founded. i.e., for all x, there is y such that yRx and for all z with zRx, not zRy. (replacing foundation)
R is local. for all x, the class {y:yRx} is a set.

Question 16

Define an ordinal in ZF.
Define what it means for a relation to be extensional. State and prove the Mostowski collapse theorem.
Show that alpha = {beta : beta < alpha}.

Answer 16

An ordinal in ZF is a transitive set that is totally ordered by epsilon.

A relation R is extensional if, for a, b, and for all x, (x,a) in R iff (x,b) in R, then a=b.

Mostowski: Let R a relation on a set a that is well-founded and extensional. Then there is a transitive set b and a bijection f: a–>b s.t. for all x,y in a (xry) iff (f(x) in f(y)). Moreover, this f, b are unique.

Proof:

1. Suppose such an f, b exist. Note that if yrx, then f(y) in f(x). Thus f(x) contains {f(y) : yrx}. Conversely, if f(x) contains any other set, say w, then since f(x) in b and b transitive, w in b. Since f is an isomorphism, w=f(z) some z in a, a contradiction. Thus we see that f(x)={f(y) : yrx}. Then we must define b={f(x):x in a}. This proves uniqueness.
2. We define f by this formula using r-recursion (noting that r is local since any relation on a set is local), then define b={f(x):x in a}.
   (i) Automatically we have xry iff (f(x) in f(y))
   (ii) Note that b is transitive, since if q in f(x), then q=f(y), for y in a. So q in b.
   (iii) It suffices to prove injective. i.e., for all x in a, f(x)=f(y)==>x=y. We prove this by r-induction on x. Assuming for all s in a, srx, then f(s)=f(t) iff s=t. Then if f(x)=f(y) iff {f(s) : srx}={f(t): try} iff {s: srx}={t: try} iff x=y since r is extensional.
3. (Maybe this proof is overly long?)
   (i) If alpha is an ordinal, then every element of alpha is an ordinal.
   Proof: We let beta in alpha. beta is a subset of alpha, and so is totally ordered by eps. In addition, if y in beta and x in y, then by transitivity of the total order on alpha, we have x in beta. Thus beta is transitive.

(ii) The proper initial segments of alpha are precisely ordinals beta, for beta in alpha. Then certainly these beta satisfy beta < alpha.
(iii) Conversely, if beta < alpha, then a unique proper initial segment of alpha has order type beta, and hence equals beta. Thus alpha={beta: beta < alpha}.
(iii) We know a priori that {beta : beta < alpha} has order type alpha. But if beta is in this set, and gamma in beta, then gamma is an ordinal that is an initial segment of beta, and so gamma <= beta < alpha. So gamma is in the set, thus {beta : beta < alpha} is an initial segment of alpha of the same order type. So by uniqueness of initial segments alpha = {beta : beta < alpha}.

Question 17

Define the Von Neumann Hierarchy.

1. Show that V_{alpha} is transitive.
2. Show that if alpha <= beta, V_alpha is a subset of V_beta.
3. State and prove the theorem, and then define the rank of a set.

Answer 17

V_0=empty set, V_{alpha+}=P(V_alpha), V_{lambda}=U V_{gamma}, gamma < lambda for nonzero limits lambda.

1. Note that power sets of transitive sets are transitive, and that unions of transitive sets are transitive.

Question 18

Define card(x). Define an initial ordinal. Define the omega ordinals and show that they are precisely the initial ordinals. Define the aleph numbers.

Question 19

Define the cofinality of an ordinal. Show that the cofinality of omega_1 is countable. Show that the cofinality of omega_2 does not inject into omega_1.

Question 20

Show that alpha+beta=beta+alpha iff alpha2+beta2=beta2+alpha2.
State a similar result for multiplication. Is 2 special?

Question 21

Define C_{alpha} inductively.
C_0 = null set
C_(alpha+)={all countable subsets of C_{alpha})
C_{lambda} = U C_{gamma}, gamma < lambda.

Does there exist C_{alpha+}=C_{alpha}?

Compare with Von-Neumman’s Hierarchy.

Answer 21

Yes (!)

Crucial first step is to show each V_{alpha} is transitive.
We show V_{alpha+} is transitive if V_{alpha} is. Indeed, pick x in V_{alpha+}. Then x is a ctble subset of V_{alpha}. So if y in x, then y in V_{alpha}. Hence y is ctble. Since V_{alpha} transitive, y a subset of V_{alpha}. So y in V_{alpha+}.

It follows that V_{alpha} subset of V_{beta} whenever alpha <= beta.

Then every countable set is a subset of C_{alpha} for some countable alpha.
Proof:
1. (null set) subset of C_0
2. If for all x in y, x in C_{alpha_x}, where alpha_x countable, consider alpha = sup {alpha_x}. Since x in C_{alpha_x}, x in C_{alpha}. So y a subset of C_{alpha}.

Therefore C_{omega1} is the set of all countable sets. So then C_{omega1+1} is a subset of C_{omega1}. So done.

Question 22

Can the theory of groups with an element of infinite order be axiomatised in the language of groups, while preserving the meaning of identity?

Answer 22

No.
1. There exists a group G which has no elements of infinite order, but elements of order n for each n

2. Let Th(G) be the set of all propositions which hold in G. Note that Th(G) is complete, meaning that for all propositions p, either Th(G) |= p or Th(G) |= not p.
3. Now add a constant g to the language, and axioms g^n != e. By compactness, this new theory has a model, which then is a group G’ with an element of infinite order.
4. Note that G’ is elementary equivalent to G, meaning the set of propositions (in the lanugage of groups) which hold in G is precisely the set of propositions that hold in G.
5. If the theory of groups with an element of infinite order could be axiomatised by say A, then G is not a model of A. But G’ is a model of A. Hence G is a model of A, contradiction.