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
$\wedge $ means "and" and $\vee $ means "or".

Exercise 2.21.

The axioms for a poset are *universal* or ${\forall}_{1}$, that is
to say that each axiom is of the form
$\forall x\u200a\forall y\u200a\dots \forall z\u200a\theta (x,y,\dots ,z)$
where $\theta $ is quantifier-free. (See Chapter 9 on first order logic.)

Exercise 2.22.

Given $<$ on $X$ let $x\u2a7dy$ be defined by $x<y\vee x=y$. Then the axioms in Definition 2.4 hold. For example if $x\u2a7dy\wedge y\u2a7dx$ 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<\prime y$ be defined by $x\u2a7dy\wedge x\ne y$. So $x<\prime y\iff (x<y\vee x=y)\wedge x\ne y\iff x<y$ so $<$ is recovered this way. For the other case, given $\u2a7d$ on $X$ satisfying Definition 2.4 let $x<y\iff x\u2a7dx\wedge x\ne y$ and observe that the axioms in Definition 2.1 hold. For example if $x<y$ and $y<z$ then $x\u2a7dz$ by transitivity of $\u2a7d$ and if $x=z$ then $x<y$ and $y<x$ so by the definition of $<$, $x\u2a7dy$ and $y\u2a7dx$ so by Definition 2.4 $x=y$, so $x<y$ is false, a contradiction. Therefore $x\ne z$ and so $x<z$. Now let $x\u2a7d\prime y\iff x<y\vee x=y$. So $x\u2a7d\prime y\iff x=y\vee (x\u2a7dy\wedge x\ne y)\iff x\u2a7dy$ since $x\u2a7dy$ holds when $x=y$ by Definition 2.4. So $\u2a7d$ is recovered.

Exercise 2.24.

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

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

Exercise 2.25.

(Proof of Theorem 2.12)

If $(X,\u2a7d)$ is directed and $u,v\in X$ are maximal then there is $w\in X$ with $u\u2a7dw$ and $v\u2a7dw$. But $uw$ and $vw$ 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:\mathbb{N}\to \mathbb{Q}$. It follows that $\mathbb{Q}$ is countable as $\mathbb{Q}=\left\{f\left(n\right):n\in \mathbb{N}\right\}$. Observe that there is a bijection $\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ (see Figure 11.1, p163 for a hint) and both $\mathbb{Z}$ and $\mathbb{N}\setminus \left\{0\right\}$ are countable. Then composing functions we have a surjection

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

Exercise 2.27.

If $f:\mathbb{N}\times \mathbb{N}\to \bigcup \left\{{X}_{i}:i\in \mathbb{N}\right\}$ is given as shown then there is a surjection

obtained by composing with the bijection $\mathbb{N}\to \mathbb{N}\times \mathbb{N}$ 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 defined

Exercise 2.28.

Follow the hint given.

Exercise 2.29.

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

Exercise 2.31.

$$X=\left\{T:\subseteq \right\}G\forall {t}_{1},{t}_{2}\in T\u200a\forall {h}_{1},{h}_{2}\in H\u200a({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\subseteq G$ there are ${t}_{1}\ne {t}_{2}\in T$ and ${h}_{1},{h}_{2}\in H$ with ${h}_{1}{t}_{1}={h}_{2}{t}_{2}$. In other words every $T\subseteq 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\subseteq V$ is linearly independent if whenever $n\in \mathbb{N}$
and ${u}_{1},\dots ,{u}_{n}\in U$ all distinct and ${\lambda}_{1},\dots ,{\lambda}_{n}\in F$
with ${\lambda}_{1}{u}_{1}+\dots +{\lambda}_{n}{u}_{n}=0$
then ${\lambda}_{1}=\dots ={\lambda}_{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 $\left\{{u}_{1},\dots ,{u}_{n}\right\}\subseteq U$
which is dependent and any $U\prime $ containing this is also dependent. So a maximal
independent set exists by Zorn's lemma. If $B\subseteq V$
is such a set and $v\in V$ then there are $n\in \mathbb{N}$ and
${u}_{1},\dots ,{u}_{n}\in B$,
${\lambda}_{1},\dots ,{\lambda}_{n}\in F$ such that
${\lambda}_{1}{u}_{1}+\dots +{\lambda}_{n}{u}_{n}=x$. For if not
one cna show that $B\cup \left\{x\right\}$ is independent, contradicting maximality
of $B$. For if ${u}_{1},\dots ,{u}_{n}\in B$ are distinct with
${\lambda}_{1}{u}_{1}+\dots +{\lambda}_{n}{u}_{n}+\mu x=0$ then
$\mu \ne 0$ and
$x={\mu}^{-1}{\lambda}_{1}{u}_{1}+\dots +{\mu}^{-1}{\lambda}_{n}{u}_{n}$.

Exercise 2.33.

Given a bijection $f:B\to C$ define

for each ${\lambda}_{1},\dots ,{\lambda}_{n}\in F$ and ${u}_{1},\dots ,{u}_{n}\in B$. This is well-defined and linearly maps $V\to W$ since each $v\in V$ is ${\lambda}_{1}{u}_{1}+\dots +{\lambda}_{n}{u}_{n}$ for some unique choice of non-zero ${\lambda}_{1},\dots ,{\lambda}_{n}\in F$ and ${u}_{1},\dots ,{u}_{n}\in B$, and $F$ has an inverse map

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\supseteq I$ exists. $R/M$ is a field since if $x\in R$ and there is no $y$ with $xy\in M$ then $M\cup \left\{x\right\}$ generates an ideal properly extending $M$. The details are left to the reader.