Exercises on discretely ordered rings

Exercise 1.

By induction on $m$ . $H (m)$ is the statement that if $k = n m$ then $DOR ⊢ (cterm (n) \times cterm (m)) = cterm (k)$ .

$H (0)$ holds as $0 = n 0$ and by an axiom of $DOR$ , $DOR ⊢ (cterm (n) \times 0) = 0$ for all $n$ .

Assuming $H (m)$ , let $k = n (m + 1)$ so $k = l + n$ where $l = n m$ . So by $H (m)$ we have $DOR ⊢ (cterm (n) \times cterm (m)) = cterm (l)$ . Also $cterm (l) + cterm (n) = cterm (l + n)$ and this is provable in $DOR$ by a theorem on a previous web page. And by the distributivity axiom, the commutativity axiom and the axiom on multiplication by $1$ we have $DOR ⊢ (cterm (n) \times (cterm (m) + 1)) = (cterm (n) \times cterm (m)) + cterm (n)$ . So puuting these together using first-order logic rules for $=$ we have $DOR ⊢ (cterm (n) \times (cterm (m) + 1)) = cterm (k)$ , as required.

Exercise 2.

Induction on the complexity of $Δ_{0}$ sentences. It's important to get the induction hypothesis right. Let $H (n)$ be the statement that If $θ$ is a $Δ_{0}$ sentence with a total of at most $n$ occurences of $¬$ , $∨$ , $∧$ , $∃$ or $∀$ , then: if $θ$ is true $DOR ⊢ θ$ ; and if $θ$ is false $DOR ⊢ \neg θ$ . The rest is left to the reader.

Exercise 3.

To prove $DOR ⊢ \forall x, y, u, v ((u + x = v \land u + y = v) \to x = y)$ and $DOR ⊢ \forall u, v \neg (2 u = 2 v + 1)$ , work, as usual, in a model of the appropriate theory and appeal to completeness.

If $x < y$ then $u + x < u + y$ so they are not equal, using axioms of $DOR$ .

If $2 u = 2 v + 1$ then $u > v$ since $u < v$ implies $2 u < 2 v$ so $2 u < 2 v + 1$ and $u = v$ implies $2 u = 2 v < 2 v + 1$ . So $2 u = u + u ⩾ u + v + 1 ⩾ v + 1 + v + 1 = 2 v + 2$ , a contradiction.

Exercise 4.

Work in an arbitrary model $M$ of $DOR$ . At the end we appeal to the completeness theorem to show the required statement is provable. Let $u, v, u', v', w \in M$ with $⟨ u, v ⟩ = ⟨ u', v' ⟩ = w$ .

We first show $u + v = u' + v'$ . Suppose not, and suppose $u + v < u' + v'$ . Then $u + v + 1 ⩽ u' + v'$ . It follows by multiplying by $u + v + 1$ and from the axioms that $(u + v) (u + v + 1) + (u + v + 1) ⩽ (u' + v') (u + v + 1)$ . Similarly $(u' + v') (u + v + 1) + (u + v + 1) ⩽ (u' + v') (u' + v' + 1)$ and putting these together, $(u + v) (u + v + 1) + 2 (u + v + 1) ⩽ (u' + v') (u' + v' + 1)$ . But this is impossible as $2 (u + v + 1) > 2 u$ and hence $w = (u + v) (u + v + 1) + 2 u ⩾ (u' + v') (u' + v' + 1)$ . Therefore $u + v ⩾ u' + v'$ and by symmetry $u + v ⩽ u' + v'$ so $u + v = u' + v'$ .

Now as $u + v = u' + v'$ it follows that $(u + v) (u + v + 1) = (u' + v') (u' + v' + 1)$ and hence $2 u = 2 u'$ . But then $u = u'$ for $u < u'$ would mean $u + u < u + u' < u' + u'$ and similiarly the other way round. Finally, as $u + v = u' + v'$ and $u = u'$ it follows from the axioms that $v = v'$ and we are done.

Exercise 5.

Again, work in an arbitrary model $M$ of $DOR + DIV2 + SQRT$ and let $w \in M$ be arbitrary.

We first claim that there is $r \in M$ such that $r (r +1) ≤ 2 w < (r +1) (r +2)$ . Indeed, by $SQRT$ , there is $r_{0}$ such that ${r_{0}}^{2} ⩽ 2 w < (r_{0})^{2}$ . If $r_{0} (r_{0} +1) ⩽ 2 w$ just let $r = r_{0}$ and note that $2 w < (r_{0} + 1)^{2} ⩽ (r_{0} + 1)^{2} + (r_{0} + 1) = (r_{0} + 1) (r_{0} + 2)$ . Otherwise $r_{0} (r_{0} +1) > 2 w$ so $r_{0} \neq 0$ and there is $r$ such that $r + 1 = r_{0}$ . Then $(r + 1) (r + 2) = r_{0} (r_{0} + 1) > 2 w ⩾ {r_{0}}^{2} = (r + 1)^{2} > r (r +1)$ and the claim is done.

Next we find $u$ such that $r (r +1) + 2 u = 2 w$ . Indeed $2 w ⩾ r (r +1)$ so by an axiom of $DOR$ there is $s$ such that $r (r + 1) + s = 2 w$ . By $DIV2$ there is $u$ such that $2 u ⩽ s < 2 (u + 1) = 2 u + 2$ . So $s = 2 u$ or $s = 2 u + 1$ . We show the latter is impossible. If $2 w = r (r + 1) + 2 u + 1$ let $2 t ⩽ r < 2 (t +1)$ using $DIV2$ again. So $r = 2 t$ or $r = 2 t + 1$ . If $r = 2 t$ then $2 w = 2 t (2 t + 1) + 2 u + 1 = 2 (t (2 t + 1) + u) + 1$ contradicting the lemma. Similarly if $r = 2 t + 1$ then $2 w = (2 t + 1) (2 t + 2) + 2 u + 1 = 2 ((t + 1) (2 t + 1) + u) + 1$ contradicting the lemma.

Finally given $2 w = r (r +1) + 2 u$ we need to check $u ⩽ r$ for if so there is $v$ such that $r = u + v$ as required. But if $u > r$ then $u ⩾ r + 1$ and $2 u ⩾ 2 r + 2$ so $2 w ⩾ r (r +1) + 2 r + 2 = (r +1) (r +2)$ contradicting our choice of $r$ .

Exercise 6.

It is actually helpful for this to assume the result in the exercise above that shows $⟨ u, v ⟩ = w$ is injective in $DOR$ .

The proof is by induction on the complexity of existential sentences. Again it is important to get the induction hypothesis right. Let $H (n)$ be the statement that If $θ (\overline{x})$ is an existential formula with a total of at most $n$ occurences of $¬$ , $∨$ , $∧$ , then there is a formula $ϕ$ in the form shown, and in the same free variables, provably equivalent to $θ (\overline{x})$ .

BASE CASE: In the case $n = 0$ the statement $θ (\overline{x})$ is either in the form given already, in which case there is nothing to prove, or else is of the form

\exists v_{1} \dots \exists v_{k} t (v_{1}, \dots, v_{k}, x_{1}, \dots, x_{m}) < s (v_{1}, \dots, v_{k}, x_{1}, \dots, x_{m})

in which case it is equivalent in $DOR$ to

\exists v_{1} \dots \exists v_{k} \exists v_{k + 1} t (v_{1}, \dots, v_{k}, x_{1}, \dots, x_{m}) + v_{k + 1} + 1 = s (v_{1}, \dots, v_{k}, x_{1}, \dots, x_{m})

as you can check.

STEP FOR $\lor$ : To transform the statement

\exists v_{1} \dots \exists v_{k} t (v_{1}, \dots, v_{k}, x_{1}, \dots, x_{m}) = s (v_{1}, \dots, v_{k}, x_{1}, \dots, x_{m}) \lor \exists w_{1} \dots \exists w_{l} g (w_{1}, \dots, w_{l}, x_{1}, \dots, x_{m}) = h (w_{1}, \dots, w_{l}, x_{1}, \dots, x_{m})

First rename the variables $w_{1}, \dots, w_{l}$ so that they are diofferent from the $v_{1}, \dots, v_{k}$ as necessary, and then write it as

\exists v_{1} \dots \exists v_{k} \exists w_{1} \dots \exists w_{l} t (\overline{v}, \overline{x}) g (\overline{w}, \overline{x}) + s (\overline{v}, \overline{x}) h (\overline{w}, \overline{x}) = t (\overline{v}, \overline{x}) h (\overline{w}, \overline{x}) + s (\overline{v}, \overline{x}) g (\overline{w}, \overline{x})

STEP FOR $\land$ : To transform the statement

\exists v_{1} \dots \exists v_{k} t (v_{1}, \dots, v_{k}, x_{1}, \dots, x_{m}) = s (v_{1}, \dots, v_{k}, x_{1}, \dots, x_{m}) \land \exists w_{1} \dots \exists w_{l} g (w_{1}, \dots, w_{l}, x_{1}, \dots, x_{m}) = h (w_{1}, \dots, w_{l}, x_{1}, \dots, x_{m})

Write it as

\exists v_{1} \dots \exists v_{k} \exists w_{1} \dots \exists w_{l} ⟨ t (\overline{v}, \overline{x}), g (\overline{w}, \overline{x}) ⟩ = ⟨ s (\overline{v}, \overline{x}), h (\overline{w}, \overline{x}) ⟩

using the pairing function of the exercise above, but note that this statement will have to be transformed to the required form using elementary algebraic means, all of which are available in $DOR$ .

STEP FOR $\neg$ : To transform the statement

\exists v_{1} \dots \exists v_{k} \neg t (v_{1}, \dots v_{k}, x_{1}, \dots, x_{m}) = s (v_{1}, \dots v_{k}, x_{1}, \dots, x_{m})

write it as

\exists v_{1} \dots \exists v_{k} (t (v_{1}, \dots v_{k}, x_{1}, \dots, x_{m}) < s (v_{1}, \dots v_{k}, x_{1}, \dots, x_{m}) \lor s (v_{1}, \dots v_{k}, x_{1}, \dots, x_{m}) < t (v_{1}, \dots v_{k}, x_{1}, \dots, x_{m}))

and use previous transformations for $<$ and $\lor$ .

Exercises on discretely ordered rings - answers