# 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.