Exercises and examples from Chapter 2

This web page provides answers, or hints and clues, to exercises from Chapter 2 of The Mathematics of Logic and also some additional information on some of the examples. As elsewhere in the book means "and" and means "or".

Exercise 2.21.

The axioms for a poset are universal or 1 , that is to say that each axiom is of the form x y z θ ( x , y , , z ) where θ is quantifier-free. (See Chapter 9 on first order logic.)

Exercise 2.22.

Given < on X let x y be defined by x < y x = y . Then the axioms in Definition 2.4 hold. For example if x y y x then x = y since the other case, x < y and y < x is forbidden by irreflexivity, since by transitivity it implies x < x . Now let x < y be defined by x y x y . So x < y ( x < y x = y ) x y x < y so < is recovered this way. For the other case, given on X satisfying Definition 2.4 let x < y x x x y and observe that the axioms in Definition 2.1 hold. For example if x < y and y < z then x z by transitivity of and if x = z then x < y and y < x so by the definition of < , x y and y x so by Definition 2.4 x = y , so x < y is false, a contradiction. Therefore x z and so x < z . Now let x y x < y x = y . So x y x = y ( x y x y ) x y since x y holds when x = y by Definition 2.4. So is recovered.

Exercise 2.24.

is an equivalence relation as x x holds by axiom (ii) of a preorder so is reflexive; if x y and y x and also y z and z y then x z and z x by transitivity of twice; and clearly the definition x y is symmetric in x , y . Definte [ x ] [ y ] to mean x y . This is well-defined for if x y and x x , y y then x x , x x , y y , y y , so by transitivity (twice) x y . Thus the definition of [ x ] [ y ] does not depend on the choice of representatives of the equivalence classes [ x ] , [ y ] .

is a partial order on X / . Transitivity and reflexivity are easy and follow from properties on on X . For the remaining axiom (iii), suppose [ x ] [ y ] and [ y ] [ x ] . Then by the previous paragraph x y and y x so x y and hence [ y ] = [ x ] .

Exercise 2.25.

(Proof of Theorem 2.12)

If ( X , ) is directed and u , v X are maximal then there is w X with u w and v w . But u w and v w since they are both maximal. So u = w and v = w hence u = v .

Exercise 2.26.

We can show there is a surjection f : . It follows that is countable as = { f ( n ) : n } . Observe that there is a bijection × (see Figure 11.1, p163 for a hint) and both and 0 are countable. Then composing functions we have a surjection

× × ( 0 )

where the last arrow is ( n , k ) n / k .

Exercise 2.27.

If f : × { X i : i } is given as shown then there is a surjection

{ X i : i }

obtained by composing with the bijection × of Figure 11.1.

The result in Exercise 2.27 requires care: it shows that under certain conditions a countable union of countable sets is easily seen to be countable. (The conditions required are that each X i is countable by a single function uniformly defineduniformly in i .) The general result that a countable union of countable sets is countable is still true but requires a form of the axiom of choice or Zorn's lemma to prove it.

Exercise 2.28.

Follow the hint given.

Exercise 2.29.

If P = P ( X ) and f : X P , let Y = { x X : x f ( x ) } . If f is onto then Y = f ( y ) for some y X . If y f ( y ) then y Y by the definition of Y hence y f ( y ) , and if y f ( y ) then y Y so y f ( y ) . This gives the contradiction.

Exercise 2.31.

X = { T : } G t 1 , t 2 T h 1 , h 2 H ( h 1 t 1 = h 2 t 2 h 1 = h 2 & t 1 = t 2 )

Then if the condition to the right of the : here is false for some T G there are t 1 t 2 T and h 1 , h 2 H with h 1 t 1 = h 2 t 2 . In other words every T G containing t 1 , t 2 failes to be in X , which shows the condition in Proposition 2.20 holds.

Exercise 2.32.

A set U V is linearly independent if whenever n and u 1 , , u n U all distinct and λ 1 , , λ n F with λ 1 u 1 + + λ n u n = 0 then λ 1 = = λ n = 0 . (Note that there is in general no way of adding infinitely many vectors from V .) A basis is a maximal linear independent set. The collection X of linearly independent sets has the Zorn property bu Proposition 2.20 since if U is dependent there is a finite subset u 1 u n U which is dependent and any U containing this is also dependent. So a maximal independent set exists by Zorn's lemma. If B V is such a set and v V then there are n and u 1 , , u n B , λ 1 , , λ n F such that λ 1 u 1 + + λ n u n = x . For if not one cna show that B x is independent, contradicting maximality of B . For if u 1 , , u n B are distinct with λ 1 u 1 + + λ n u n + μ x = 0 then μ 0 and x = μ -1 λ 1 u 1 + + μ -1 λ n u n .

Exercise 2.33.

Given a bijection f : B C define

F ( λ 1 u 1 + + λ n u n ) = λ 1 f ( u 1 ) + + λ n f ( u n )

for each λ 1 , , λ n F and u 1 , , u n B . This is well-defined and linearly maps V W since each v V is λ 1 u 1 + + λ n u n for some unique choice of non-zero λ 1 , , λ n F and u 1 , , u n B , and F has an inverse map

G ( λ 1 w 1 + + λ n w n ) = λ 1 f -1 ( u 1 ) + + λ n f -1 ( u n )

As you can check. (There are a number of detailed checks omitted that the reader must do here.)

Exercise 2.34.

The set of ideals containing I is a poset with the Zorn property by Proposition 2.20. So a maximal ideal M I exists. R / M is a field since if x R and there is no y with x y M then M x generates an ideal properly extending M . The details are left to the reader.