J. Munkres. Topology (2013) Chapter 1: Set Theory and Logic. 4: The Integers and the Real Numbers

Definition 1: Binary Operation

A binary operation on a set \(A\) is a function \(A^2 \rightarrow A\).

Definition 2: Field

A field is a triple \((K, +, \cdot)\) where \(K\) is a set and \(+\) and \(\cdot\) are binary operations on \(K\), called addition and multiplication, such that:

(1)

\((x + y) + z = x + (y + z)\) and \((xy)z = x(yz)\) for all \(x,y,z \in \mathbb{R}\)

(2)

\(x+y=y+x\) and \(xy=yx\) for all \(x,y \in \mathbb{R}\)

(3)

There exists an element \(0 \in \mathbb{R}\), called zero, such that \(x + 0 = x\) for all \(x \in \mathbb{R}\). There exists an element \(1 \in \mathbb{R}\), called one, such that \(0 \neq 1\) and \(x1=x\) for all \(x \in \mathbb{R}\).

(4)

For all \(x \in \mathbb{R}\), there exists a unique \(y \in \mathbb{R}\) such that \(x + y = 0\), called the negative of \(x\) and denoted \(-x\). For each \(x \in \mathbb{R}\) different from 0, there exists a unique \(y \in \mathbb{R}\) such that \(xy = 1\), called the reciprocal of \(x\) and denoted \(1/x\).

(5)

\( x(y+z) = xy+xz \) for all \(x,y,z \in \mathbb{R}\).

Definition 3: Subtraction

We write \(x - y\) for \(x + (-y)\).

Definition 4: Quotient

Given elements \(x\) and \(y\) of a field with \(y \neq 0\), we write \(x/y\) for \(x(1/y)\).

Proposition 5

In any field, if \(x + z = y + z\) then \(x = y\).

Proof

\[ \begin{align} x & = x + 0 & (\text{3}) \\ & = x + z + (-z) & (\text{4}) \\ & = y + z + (-z) \\ & = y + 0 & (\text{4}) \\ & = y & (\text{3}) \Box \end{align} \]

Proposition 6

\[ 0x = 0 \]

Proof

\[ \begin{align} 0x & = (0+0)x & (\text{3}) \\ & = 0x + 0x & (\text{5}) \end{align} \]

We also have \(0x = 0x + 0\) by (3) so \(0x + 0 = 0x + 0x\). Hence \(0x = 0\) by Proposition 5. \(\Box\)

Proposition 7

\[ (-x)y = -(xy) \]

Proof

\[ \begin{align} xy + (-x)y & = (x+(-x))y & (\text{5}) \\ & = 0y & (\text{4}) \\ & = 0 & (Proposition 6) \Box \end{align} \]

Proposition

\[ -0 = 0 \]

Proof

Since \(0 + 0 = 0\). \(\Box\)

Proposition

\[ -(-x) = x \]

Proof

Since \((-x) + x = 0\).

Definition 8: Ordered Field

An ordered field is a quadruple \((K, +, \cdot, <)\) such that \((K, +, \cdot)\) is a field and \(<\) is a linear order on \(K\), and:

(6)

If \(x > y\), then \(x + z > y + z\). If \(x > y\) and \(z > 0\), then \(xz > yz\).

Proposition 9

In any ordered field, if \(-x < -y\) then \(x > y\).

Proof

If \(-x < -y\) then \(x-x < x-y\) by (6), hence \(0 < x-y\) by (4). Hence \(y < x-y+y\) by (6), so \(y < x + 0\) by (4), and so \(y < x\) by (3).

Proposition 10

If \(x > y\) and \(z < 0\), then \(xz < yz\).

Proof

Let \(x,y,z \in \mathbb{R}\). Assume \(x > y\) and \(z < 0\).
\(0 < -z\)

We have \(z + (-z) < 0 + (-z)\) by (6), \(z + (-z) = 0\) by (4) and \(0 + (-z) = -z\) by (3).

\(x(-z) > y(-z)\)

By (6)

\(-(xz) > -(yz)\)

Proposition 7

\(xz < yz\)

Proposition 9

\(\Box\)

Proposition 11

\[ 0 < 1 \]

Proof

\(0 \neq 1\)

By (3)

\(1 \nless 0\)

Assume for a contradiction \(1 < 0\)
\(1 \cdot 1 > 1 \cdot 0\)

Proposition 10

\(1 > 0\)

By (3)

This is a contradiction.

\(0 < 1\)

Since \(<\) is a linear order.

\(\Box\)

Proposition 12

\[ -1 < 0 \]

Proof

Add \(-1\) to both sides of Proposition 11. \(\Box\)

Definition 13: Positive

An element of an ordered field \(x\) is positive iff \(x > 0\).

Definition 15: Negative

An element of an ordered field \(x\) is negative iff \(x < 0\). We write \(\overline{\mathbb{R}_+}\) for the set of nonnegative reals.

Definition 16: Linear Continuum

A linear continuum is a linearly ordered set \((A, <)\) such that \(<\) has the least upper bound property, and, for all \(x,y \in A\), if \(x < y\), then there exists an element \(z\) such that \(x < z < y\).

Assumption 17

There exists an ordered field \((\mathbb{R}, +, \cdot, <)\) that satisfies the least upper bound property. We write \(\mathbb{R}_+\) for the set of positive reals, and \(\overline{\mathbb{R}_+}\) for the set of nonnegative reals.

Proposition 18

The real numbers form a linear continuum.

Proof

Given real numbers \(x\), \(y\), if \(x < y\) then \(x < (x + y)/2 < y\). \(\Box\)

Definition 19

A subset \(A\) of the real numbers is said to be inductive iff it contains the number 1, and if for every \(x \in A\), the number \(x+1\) is also in \(A\). Let \(\mathcal{A}\) be the set of all inductive subsets of \(\mathbb{R}\). Then the set \(\mathbb{Z}_+\) of positive integers is defined by the equation.

\[ \mathbb{Z}_+ = \bigcap \mathcal{A} \enspace . \]

Proposition 20

\[ \mathbb{Z}_+ \subseteq \mathbb{R}_+ \]

Proof

Since \(\mathbb{R}_+\) is inductive. \(\Box\)

Proposition 21

1 is the least element of \(\mathbb{Z}_+\).

Proof

Since \(\{x \in \mathbb{R} : x \geq 1\}\) is inductive. \(\Box\)

Proposition 22

\(\mathbb{Z}_+\) is inductive.

Proof

Since 1 is in every inductive set, and if \(x\) is in every inductive set then \(x+1\) is in every inductive set. \(\Box\)

Proposition 23: Principle of Induction

If \(A\) is an inductive set of positive integers then \(A = \mathbb{Z}_+\).

Proof

Immediate from definitions. \(\Box\)

Definition 24: Integers

The set \(\mathbb{Z}\) of integers is \(\mathbb{Z}_+ \cup \{0\} \cup \{-n : n \in \mathbb{Z}_+\}\).

Proposition 25

If \(n \in \mathbb{Z}\) then \(-n \in \mathbb{Z}\).

Proof

If \(n \in \mathbb{Z}_+\) then \(-n \in \mathbb{Z}\).

Immediate from definitions.

\(-0 \in \mathbb{Z}\)

Since \(-0 = 0\)

If \(n \in \mathbb{Z}_+\) then \(-(-n) \in \mathbb{Z}\).

Since \(-(-n) = n\)

\(\Box\)

Proposition 26

The sum of two integers is an integer.

Proof

\(\langle 1 \rangle 1\)For any integer \(n\) we have \(n+1\) is an integer.

If \(n\) is a positive integer then \(n+1\) is a positive integer.

From Proposition 22

\(0+1\) is an integer.

It is the positive integer 1.

If \(n\) is a positive integer then \(-n+1\) is an integer.

\(-1+1\) is an integer.

It is the integer 0.

If \(n\) is a positive integer then \(-(n+1)+1\) is in integer.

It is the integer \(-n\).

\(\langle 1 \rangle 2\) For any integer \(m\) and \(n \in \mathbb{Z}_+\), we have \(m + n \in \mathbb{Z}\).

For any integer \(m\), we have \(m + 1 \in \mathbb{Z}\)

From \(\langle 1 \rangle 1 \).

Let \(m\) and \(n\) be integers. If \(m + n\) is an integer then \(m + n + 1\) is an integer.

From \(\langle 1 \rangle 1\).

For any integer \(m\) we have \(m + 0 \in \mathbb{Z}\).

Since \(m+0=m\).

For any integer \(m\) and \(n \in \mathbb{Z}_+\), we have \(m + (-n) \in \mathbb{Z}\).

Since \((-m)+n\) is an integer by \(\langle 1 \rangle 2\) and \(m + (-n) = -((-m)+n)\).

\(\Box\)

Proposition

The difference between two integers is an integer.

Proof

Since, for integers \(m\) and \(n), we have \(m - n = m + (-n)\), and \(m\) and \(-n\) are integers. \(\Box\)

Proposition

The product of two integers is an integer.

Proof

\(\langle 1 \rangle 1\) For any integer \(m\) and positive integer \(n\), we have \(mn\) is an integer.

Let \(m\) be an integer.
\(m \cdot 1\) is an integer.

Since \(m \cdot 1 = m\).

For any positive integer \(n\), if \(mn\) is an integer then \(m(n+1)\) is an integer.

Since \(m(n+1) = mn + m\) and the sum of two integers is an integer.

For any integer \(m\), we have \(m \cdot 0\) is an integer.

Since \(m \cdot 0 = 0\).

For any integer \(m\) and positive integer \(n\), we have \(m(-n)\) is an integer.

We have \(mn\) is an integer by \(\langle 1 \rangle 1 \) and \(m(-n) = -(mn)\).

\(\Box\)

Proposition

For any integer \(n\), there is no integer \(a\) such that \(n < a < n + 1\).

Proof

\( \langle 1 \rangle 1 \) For any positive integer \(n\), there is no integer \(a\) such that \(n < a < n + 1\).

There is no integer \(a\) such that \(1 < a < 2\).

There is no positive integer \(a\) such that \(1 < a < 2\).

Since for any positive integer \(a\), either \(a = 1\) or \(2 \leq a\).

We do not have \(1 < 0 < 2\).

Since \(0 < 1\).

There is no positive integer \(a\) such that \(1 < -a < 2\).

If \(a\) is positive then \(-a < 0 < 1\).

For any positive integer \(n\), if there is no integer \(a\) such that \(n < a < n+1\), then there is no integer \(a\) such that \(n+1 < a < n+2\).

Since if \(n+1 < a < n+2\) then \(n < a-1 < n+1\).

There is no integer \(a\) such that \(0 < a < 1\).

If \(0 < a < 1\) then \(1 < a+1 < 2\) contradicting \(\langle 1 \rangle 1\).

For any positive integer \(n\), there is no integer \(a\) such that \(-n < a < -n+1\).

If \(-n < a < -n+1\) then \(n-1 < -a < n\) and so \(n < 1-a < n+1\) contradicting \(\langle 1 \rangle 1\).

Example

The quotient of two integers is not necessarily an integer. For example, \(1/2\) is not an integer, because \(0 < 1/2 < 1\).

Definition: Rational Number

A rational number is a real number that is the quotient of two integers. Let \(\mathbb{Q}\) be the set of rational numbers.

Definition: Section

For \(n\) a positive integer, let \(S_n = \{ k \in \mathbb{Z}_+ : k < n\}\). We call \(S_n\) a section of the positive integers.

Theorem 4.1: Well-ordering Property

Every nonempty subset of \(\mathbb{Z}_+\) has a smallest element.

Proof

Let \(S \subseteq \mathbb{Z}_+\).
Assume \(S\) has no smallest element. Prove: \(S = \emptyset\).
For every positive integer \(n\), we have \(S_n \subseteq \mathbb{Z}_+ - S\).

\(S_1 \subseteq \mathbb{Z}_+ - S\)

Since \(S_1 = \emptyset\).

For any positive integer \(n\), if \(S_n \subseteq \mathbb{Z}_+ - S\) then \(S_{n+1} \subseteq \mathbb{Z}_+ - S\).

Let \(n\) be a positive integer.
Assume \(S_n \subseteq \mathbb{Z}_+ - S\)
\(n \notin S\)

If \(n \in S\) then \(n\) is the smallest element of \(S\).

\(S_{n+1} \subseteq \mathbb{Z}_+ - S\)

\(\mathbb{Z}_+ = \mathbb{Z}_+ - S\)
\(S = \emptyset\)
\(\Box\)

Theorem 4.2: Strong Induction Principle

Let \(A\) be a set of positive integers. Suppose that for each positive integer \(n\), the statement \(S_n \subseteq A\) implies the statement \(n \in A\). Then \(A = \mathbb{Z}_+\).

Proof

Since the set \(\mathbb{Z}_+ - A\) has no smallest element. \(\Box\)

Archimedean ordering property

The set \(\mathbb{Z}_+\) has no upper bound.

Proof

Assume for a contradiction \(\mathbb{Z}_+\) is bounded above.
Let \(u\) be its supremum.
Pick \(n \in \mathbb{Z}_+\) such that \(u-1 < n\).
\(u < n+1\)
This contradicts the fact that \(u\) is an upper bound for \(\mathbb{Z}_+\).
\(\Box\)

Proposition

For every positive real \(a\), there exists a unique positive real \(b\) such that \(y^2 = x\).

Proof

Let \(a\) be a positive real.
\( \langle 1 \rangle 1 \) For any reals \(x\) and \(h\), if \(x > 0\) and \(0 \leq h < 1\) then \((x+h)^2 < x^2 + h(2x+1)\).

\((x+h)^2 = x^2 + 2hx + h^2 < x^2 + 2hx + h\)

For any reals \(x\) and \(h\), if \(x > 0\) and \(0 < h < 1\) then \((x-h)^2 > x^2 - 2hx\).

\((x-h)^2 = x^2 - 2hx + h^2 > x^2 - 2hx\)

\( \langle 1 \rangle 2 \)For any real \(x\), if \(0 < x\) and \(x^2 < a\) then there exists \(h > 0\) such that \((x+h)^2 < a\).

Assume w.l.o.g. \(a < (x+1)^2\)

Otherwise take \(h = 1/2\).

Let \(h = (a - x^2)/(2x+1)\).
\(0 < h\)

Since \(a - x^2 > 0\) and \(2x + 1 > 0\)

\(h < 1\)

Since \(a < x^2 + 2x + 1\) so \(a - x^2 < 2x + 1\)

\((x+h)^2 < x^2 + h(2x+1) = a\).

By \(\langle 1 \rangle 1\).

\(\langle 1 \rangle 3\) For any real \(x\), if \(0 < x\) and \(x^2 > a\) then there exists \(h > 0\) such that \((x-h)^2 > a\).

Let \(x\) be a positive real.
Assume \(x^2 > a\)
Assume w.l.o.g. \(a \geq (x-1)^2\)

Otherwise take \(h = 1\).

Let \(h = (x^2 - a) / 2x\)
\( 0 < h \)
\( h < 1 \)

Since \(a \geq x^2 - 2x + 1 > x^2 - 2x\).

\((x-h)^2 > x^2 - 2xh = a\)

Let \(B = \{x \in \mathbb{R} \mid x^2 < a\}\).
\(B\) is bounded above.

If \(x \geq a + 1\) then \(x^2 \geq a^2 + 2a + 1 > a\). Therefore if \(x \in B\) then \(x < a + 1\).

\(B\) contains a positive real.

Pick a positive integer \(n\) such that \(n > 1/a\).

Archimedean property

\(n^2 > 1/a\)
\(1/n^2 < a\)
\(1/n \in B\)

Let \(b = \sup B\).
\(b^2 = a\)

\(b^2 \nless a\)

Assume for a contradiction \(b^2 < a\)
Pick \(h > 0\) such that \((b+h)^2 < a\)

By \( \langle 1 \rangle 2 \).

\(b + h \in B\)
This contradicts the fact that \(b\) is an upper bound for \(B\).

\(b^2 \not > a\)

Assume for a contradiction \(b^2 > a\).
Pick \(h > 0\) such that \((b-h)^2 > a\).

By \(\langle 1 \rangle 3\).

Pick \(x \in B\) such that \(b-h < x\)

Since \(b-h < b\) so \(b-h\) is not an upper bound for \(B\).

\(x^2 > a\)

\(x^2 > (b-h)^2 > a\)

This contradicts the fact that \(x \in B\)

For any positive real numbers \(b\) and \(c\), if \(b^2 = c^2\) then \(b = c\).

If \(b < c\) then \(b^2 < c^2\), and if \(c < b\) then \(c^2 < b^2\).

\(\Box\)

Definition: Square Root

For \(a\) a positive real, the square root of \(a\), denoted by \(\sqrt{a}\), is the unique positive real such that \((\sqrt{a})^2 = a\).

Definition: Even

An integer \(m\) is even iff \(m / 2 \in \mathbb{Z}\); otherwise \(m\) is odd.

Proposition

If \(m\) is odd then there exists an integer \(n\) such that \(m = 2n + 1\).

Proof

Let \(n\) be the integer such that \(n < m/2 < n+1\). Then \(2n < m < 2n+2\) and so \(m = 2n+1\). \(\Box\)

Proposition

For any integers \(p\) and \(q\), if \(p\) and \(q\) are odd then \(pq\) is odd.

Proof

Let \(p = 2m+1\) and \(q = 2n+1\) where \(m\) and \(n\) are integers. Then \(pq = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1\). \(\Box\)

Proposition

For any rational number \(a > 0\), there exist positive integers \(m\), \(n\) such that \(a = m/n\) and \(m\) and \(n\) are not both even.

Proof

Let \(n\) be the least element of the set \(S = \{ x \in \mathbb{Z}_+ \mid xa \in \mathbb{Z}_+ \}\).
Let \(m = na\).
\(a = m/n\)
Assume for a contradiction \(m\) and \(n\) are both even.
\(a = (m/2)/(n/2)\)
\(n/2 \in S\)
This contradicts the leastness of \(n\).
\(\Box\)

Theorem

\(\sqrt{2}\) is irrational.

Proof

Assume for a contradiction \(\sqrt{2}\) is rational.
Pick positive integers \(m\), \(n\) such that \(\sqrt{2} = m / n\) and \(m\) and \(n\) are not both even.
\(2 = m^2 / n^2\)
\(m^2 = 2n^2\)
\(m^2\) is even.
\(m\) is even.
Let \(m = 2k\) where \(k \in \mathbb{Z}_+\).
\(4k^2 = 2n^2\)
\(2k^2 = n^2\)
\(n^2\) is even.
\(n\) is even.
This contradicts the fact that \(m\) and \(n\) are not both even.
\(\Box\)

Exercises

Exercise 1

Prove the following "laws of algebra" for \(\mathbb{R}\), using only axioms (1)-(5):

(a)

If \(x + y = x\) then \(y = 0\).

Solution

We have \(- x + x + y = -x + x\), hence \(0 + y = 0\) by (4), and so \(y = 0\) by (3). \(\Box\)

(b)

\[0x=0\]

Solution

We have \(0x = (0+0)x = 0x+0x\) by (3) and (5), and so \(0x = 0\) by (a).

(c)

\[-0 = 0\]

Solution

This holds because \(0 + 0 = 0\) by (3).

(d)

\[ -(-x) = x\]

Solution

This holds because \(x + (-x) = 0\) by (4).

(e)

\[ x(-y) = -(xy) = (-x)y \]

Solution

We have \(xy + x(-y) = x(y + (-y)) = x0 = 0\) by (5), (4) and (b); hence \(-(xy) = x(-y)\). We prove \(-(xy) = (-x)y\) similarly.

(f)

\[ (-1)x = -x \]

Solution

We have \(x + (-1)x = 1x + (-1)x = (1 + (-1))x = 0x = 0\) by (3), (5), (4) and (b).

(g)

\[x(y-z) = xy-xz \]

Solution

\[ \begin{align} x(y-z) & = x(y + (-z)) \\ & = xy + x(-z) & (5) \\ & = xy + (-(xz)) & \text{(e)} \\ & = xy - xz \end{align} \]

(h)

\[ -(x+y) = -x-y; -(x-y) = -x+y \]

Solution

\[ \begin{align} -(x+y) & = (-1)(x+y) & \text{(f)} \\ & = (-1)x + (-1)y & (5) \\ & = -x-y & \text{(f)} \\ -(x-y) & = -x-(-y) & \text{(from above)} \\ & = -x+y & \text{(d)} \end{align} \]

(i)

If \(x \neq 0\) and \(xy = x\) then \(y = 1\).

Solution

\[ \begin{align} y & = 1y & \text{(3)} \\ & = (1/x)xy & \text{(4)} \\ & = (1/x)x \\ & = 1 & \text{(4)} \end{align} \]

(j)

\( x/x = 1\) if \(x \neq 0\)

Solution

Immediate from (4).

(k)

\[ x/1 = x\]

Solution

We have \(1/1 = 1\) since \(1 \cdot 1 = 1\) by (3). Hence \(x/1 = x \cdot 1 = x\) by (3).

(l)

If \(x \neq 0\) and \(y \neq 0\) then \(xy \neq 0\).

Solution

Assume \(x \neq 0\) and \(xy = 0\); we prove that \(y = 0\). We have

\[ \begin{align} (1/x)xy & = (1/x)0 \\ y & = 0 & \text{(4),(b)} \end{align} \]

(m)

\((1/y)(1/z) = 1/(yz)\) if \(y,z \neq 0\).

Solution

Since \(yz(1/y)(1/z) = y(1/y)z(1/z) = 1 \cdot 1 = 1\)

(n)

\((x/y)(w/z) = (xw)/(yz)\) if \(y,z \neq 0\)

Solution

\[ \begin{align} (x/y)(w/z) & = x (1/y) w (1/z) \\ & = xw(1/y)(1/z) & (2) \\ & = xw(1/yz) & \text{(m)} \\ & = xw/yz \end{align} \]

(o)

\((x/y)+(w/z) = (xz+wy)/yz\) if \(y,z \neq 0\)

Solution

\[ \begin{align} (x/y) + (w/z) & = (x/y)1 + (w/z)1 & \text{(3)} \\ & = (x/y)(z/z) + (w/z)(y/y) & \text{(4)} \\ & = xz/yz + wy/yz & \text{(n)} \\ & = xz(1/yz) + wy(1/yz) \\ & = (xz + wy)(1/yz) & \text{(5)} \\ & = (xz + wy)/yz \end{align} \]

(p)

If \(x \neq 0\) then \(1/x \neq 0\)

Solution

We have \(x(1/x) = 1 \neq 0\) by (4) and (3), and so we cannot have \(1/x=0\) by (b).

(q)

\(1/(w/z) = z/w\) if \(w,z \neq 0\)

Solution

This holds because \((w/z)(z/w) = wz/wz = 1\) by (n) and (4)

(r)

\((x/y)/(w/z) = xz/yw\) if \(y,w,z \neq 0\)

Solution

\[ \begin{align} (x/y)/(w/z) & = (x/y)(1/(w/z)) \\ & = (x/y)(z/w) & \text{(q)} \\ & = xz / yw & \text{(n)} \end{align} \]

(s)

\((ax)/y = a(x/y)\) if \(y \neq 0\)

Solution

Both are equal to \(ax(1/y)\) by definition.

(t)

\((-x)/y = x/(-y) = -(x/y)\) if \(y \neq 0\)

Solution

We have \((-x)/y = (-x)(1/y) = -(x(1/y)) = -(x/y)\) by (e).

To show \(x/(-y) = -(x/y)\), we reason:

\[ \begin{align} x/(-y) + x/y & = x/(-y) + (x/y)1 & \text{(3)} \\ & = x/(-y) + (x/y)(-1/-1) & \text{(4)} \\ & = x/(-y) + (-x/-y) & \text{(n),(f)} \\ & = x(1/(-y)) + (-x)(1/(-y)) \\ & = (x + (-x))(1/(-y)) & \text{(5)} \\ & = 0(1/(-y)) & \text{(4)} \\ & = 0 & \text{(b)} \end{align} \]

Hence \(x/(-y) = -(x/y)\) by (4).

Exercise 2

Prove the following "laws of inequalities" for \(\mathbb{R}\), using axioms (1)-(6) along with the results of Exercise 1:

(a)

\(x > y\) and \(w > z \Rightarrow x + w > y + z\)

Solution

We have \(x + w > y + w\) by (6) and \(y + w > y + z\) by (6), hence \(x + w > y + z\) by transitivity.

(b)

\(x > 0\) and \(y > 0 \Rightarrow x + y > 0\) and \(xy > 0\)

Solution

\[ \begin{align} x + y & > 0 + 0 & \text{(a)} \\ & = 0 & \text{(3)} \\ xy & > 0y & \text{(6)} \\ & = 0 & \text{1(b)} \end{align} \]

(c)

\[ x > 0 \Leftrightarrow -x < 0 \]

Solution

If \(x > 0\) then \(x + (-x) > 0 + (-x)\) by (6), and so \(0 > -x\) by (3) and (4).

If \(-x < 0\) then \(x + (-x) < x + 0\) by (6), and so \(0 < x\) by (3) and (4).

(d)

\[ x > y \Leftrightarrow -x < -y \]

Solution

If \(x > y\) then \(x + (-x) + (-y) > y + (-x) + (-y)\) by (6), and so \(-y > -x\) using (3) and (4).

If \(-x < -y\) then \(-x + x + y < -y + x + y\) by (6), and so \(y < x\) using (3) and (4).

(e)

\(x > y\) and \(z < 0 \Rightarrow xz < yz\)

Solution

If \(x > y\) and \(z < 0\), we have \(0 < -z\) by (c), and so \(x (-z) > y(-z)\) by (6). Hence \(-(xz) > -(yz)\) by 1(e), and so \(xz < yz\) by (d).

(f)

\(x \neq 0 \Rightarrow x^2 > 0\) where \(x^2 = xx\)

Solution

If \(x > 0\) then \(x^2 > 0x = 0\) by (6) and 1(b).

If \(x < 0\) then \(x^2 > 0x = 0\) by (e) and 1(b).

(g)

\[ -1 < 0 < 1 \]

Solution

We have \(1^2 > 0\) by (f); that is \(1 > 0\), because \(1^2 = 1\) by (3).

We therefore have \(-1 < 0\) by (c).

(h)

\(xy > 0 \Leftrightarrow x\) and \(y\) are both positive or both negative.

Solution

If \(x > 0\) and \(y > 0\) then \(xy > 0\) by (b).

If \(x < 0\) and \(y < 0\) then \(xy > 0\) by (e).

If either is 0 then \(xy = 0\) by 1(b).

If \(x > 0\) and \(y < 0\) then \(xy < 0\) by (e).

If \(x < 0\) and \(y > 0\) then \(xy < 0\) by (e).

(i)

\[ x > 0 \Rightarrow 1/x > 0 \]

Solution

We have \(x(1/x) = 1 > 0\) by (4) and (g). So \(x\) and \(1/x\) are both positive or both negative by (h). Since \(x\) is positive, it must be that \(1/x\) is positive.

(j)

\[ x > y > 0 \Rightarrow 1/x < 1/y \]

Solution

Assume \(x > y > 0\).

\[ \begin{align} 1/y & > 0 & \text{(i)} \\ x(1/y) & > y(1/y) & \text{(6)} \\ & = 1 & \text{(4)} \\ 1/x & > 0 & \text{(i)} \\ x(1/x)(1/y) & > 1(1/x) & \text{(6)} \\ 1/y & > 1/x & \text{(3),(4)} \end{align} \]

(k)

\[ x < y \Rightarrow x < (x+y)/2 < y \]

Solution

Assume \(x < y\). Then \(x + x < x + y\) by (6); that is, \(2x < x+y\). We have \(2 > 0\) using (g), so \(1/2 > 0\) by (i). Hence \(2x\cdot(1/2) < (x+y)(1/2) \) by (6); that is, \(x < (x+y)/2\).

We also have \(x + y < y + y = 2y\) and so \((x+y)/2 < y\) similarly.

Exercise 3

See above.

Exercise 4

(a)

Prove by induction that given \(n \in \mathbb{Z}_+\), every nonempty subset of \(\{1, \ldots, n\}\) has a largest element.

Solution

The only nonempty subset of \(\{1\}\) is \(\{1\}\), which has largest element 1.

Assume that every nonempty subset of \(\{1, \ldots, n\}\) has a largest element. Let \(S \subseteq \{1, \ldots, n+1\}\) be nonempty. If \(n + 1 \in S\) then \(n+1\) is the largest element of \(S\). Otherwise, \(S\) is a nonempty subset of \(\{1, \ldots, n\}\), and therefore has a largest element by the induction hypothesis.

(b)

Explain why you cannot conclude from (a) that every nonempty subset of \(\mathbb{Z}_+\) has a largest element.

Solution

Let us try the same argument as in the text. Let \(A\) be a nonempty subset of \(\mathbb{Z}_+\). Pick \(n \in A\) since \(A\) is nonempty. Then \(A \cap \{1, \ldots, n\}\) is a nonempty subset of \(\{1, \ldots, n\}\), and so has a largest element \(k\) say (in fact \(k = n\)). But we cannot conclude from this that \(k\) is the largest element of \(A\). When reasoning about smallest elements, we used the fact that any element smaller than \(k\) would be an element of \(A \cap \{1, \ldots, n\}\). The corresponding statement with "larger" in place of "smaller" is not true.

Exercise 5

See above.

Exercise 6

Let \(a \in \mathbb{R}\). Define inductively

\[ \begin{align} a^1 & = a \\ a^{n+1} & = a^n a \end{align} \] for \(n \in \mathbb{Z}_+\). (See §7 for a discussion of the process of inductive definition.) Show that for \(m,n \in \mathbb{Z}_+\) and \(a,b \in \mathbb{R}\), \[ \begin{align} a^n a^m & = a^{n+m} \\ (a^n)^m & = a^{nm} \\ a^m b^m & = (ab)^m \end{align} \]

These are called the laws of exponents.

Solution

\( \langle 1 \rangle 1 \) For all \(a \in \mathbb{R}\) and \(m,n \in \mathbb{Z}_+\), we have \(a^n a^m = a^{n+m}\).

Let \(a \in \mathbb{R}\) and \(n \in \mathbb{Z}_+\).
\(a^n a^1 = a^{n+1}\)

We have \(a^n a^1 = a^n a = a^{n+1}\) by definition.

For all \(m \in \mathbb{Z}_+\), if \(a^n a^m = a^{n+m}\) then \(a^n a^{m+1} = a^{n+(m+1)}\).

\( \langle 3 \rangle 1 \) Let \(m \in \mathbb{Z}_+\) and assume \(a^n a^m = a^{n+m}\).
\(a^n a^{m+1} = a^{n+m+1}\)

For all \(a \in \mathbb{R}\) and \(m,n \in \mathbb{Z}_+\), we have \((a^n)^m = a^{nm}\).

Let \(a \in \mathbb{R}\) and \(n \in \mathbb{Z}_+\).
\((a^n)^1 = a^{n1}\)

\((a^n)^1 = a^n = a^{n1}\).

For any \(m \in \mathbb{Z}_+\), if \((a^n)^m = a^{nm}\) then \((a^n)^{m+1} = a^{n(m+1)}\).

\( \langle 3 \rangle 1 \) Let \(m \in \mathbb{Z}_+\). Assume \((a^n)^m = a^{nm}\).

For all \(a,b \in \mathbb{R}\) and \(m \in \mathbb{Z}_+\), we have \(a^m b^m = (ab)^m\).

Let \(a,b \in \mathbb{R}\).
\(a^1 b^1 = (ab)^1\)

\(a^1 b^1 = ab = (ab)^1\).

For any \(m \in \mathbb{Z}_+\), if \(a^m b^m = (ab)^m\) then \(a^{m+1} b^{m+1} = (ab)^{m+1}\).

\( \langle 3 \rangle 1 \) Let \(m \in \mathbb{Z}_+\). Assume \(a^m b^m = (ab)^m\).

Exercise 7

Let \(a \in \mathbb{R}\) and \(a \neq 0\). Define \(a^0 = 1\), and for \(n \in \mathbb{Z}_+\), \(a^{-n} = 1/a^n\). Show that the laws of exponents hold for \(a,b \neq 0\) and \(n,m \in \mathbb{Z}\).

Solution

\( \langle 1 \rangle 1 \) For \(a \neq 0\) and \(n,m \in \mathbb{Z}\) we have \(a^n a^m = a^{n+m}\).

Let \(a \neq 0\).
\( \langle 2 \rangle 1 \) For \(n \in \mathbb{Z}\) we have \(a^n a = a^{n+1}\).

For \(n \in \mathbb{Z}_+\) we have \(a^n a = a^{n+1}\).

By definition.

\(a^0 a = a^{0+1}\)

\(a^0 a = 1a = a = a^1\)

For \(n \in \mathbb{Z}_+\) we have \(a^{-n} a = a^{-n+1}\).

\(a^{-1} a = a^0\)

\(a^{-1}a = (1/a)a = 1 = a^0\)

For \(n \in \mathbb{Z}_+\), we have \(a^{-(n+1)} a = a^{-n}\).

\(a^{-(n+1)}a = (1/a^{n+1})a = (1/a^n)(1/a)a = 1/a^n = a^{-n}\)

\( \langle 2 \rangle 2 \) For \(n \in \mathbb{Z}\) we have \(a^n a^{-1} = a^{n-1}\).

\(a^{n-1} a = a^n\)

By \( \langle 1 \rangle 1 \).

\(a^{n-1} a a^{-1} = a^n a^{-1}\)
\(a^{n-1} = a^n a^{-1}\)

\( \langle 2 \rangle 3 \) For \(n \in \mathbb{Z}\) and \(m \in \mathbb{Z}_+\) we have \(a^n a^m = a^{n+m}\).

Let \(n \in \mathbb{Z}\).
\(a^n a^1 = a^{n+1}\)

By \( \langle 1 \rangle 1 \).

For \(m \in \mathbb{Z}_+\), if \(a^n a^m = a^{n+m}\) then \(a^n a^{m+1} = a^{n+m+1}\).

\( \langle 3 \rangle 1 \) Let \(m \in \mathbb{Z}_+\). Assume \(a^n a^m = a^{n+m}\).
\(a^n a^{m+1} = a^{n+m+1}\)

For \(n \in \mathbb{Z}\) we have \(a^n a^0 = a^{n+0}\).

\(a^n a^0 = a^n 1 = a^n = a^{n+0}\)

For \(m \in \mathbb{Z}_+\) and \(n \in \mathbb{Z}\), we have \(a^n a^{-m} = a^{n-m}\).

Let \(m \in \mathbb{Z}_+\) and \(n \in \mathbb{Z}\).
\(a^{n-m} a^m = a^n\)

\( \langle 2 \rangle 3 \)

\(a^{n-m} = a^na^{-m}\)

For \(a \neq 0\) and \(n,m \in \mathbb{Z}\) we have \((a^n)^m = a^{nm}\).

Let \(a \neq 0\) and \(n \in \mathbb{Z}\).
\( \langle 2 \rangle 1 \) For \(m \in \mathbb{Z}_+\), we have \((a^n)^m = a^{nm}\).

\((a^n)^1 = a^n\)
For any \(m \in \mathbb{Z}_+\), if \((a^n)^m = a^{nm}\) then \((a^n)^{m+1} = a^{nm + n}\).

Let \(m \in \mathbb{Z}_+\). Assume \((a^n)^m = a^{nm}\).
\((a^n)^{m+1} = a^{nm+n}\)

\((a^n)^0 = a^0\)

Both are equal to 1.

For \(m \in \mathbb{Z}_+\), we have \((a^n)^{-m} = a^{-nm}\).

Let \(m \in \mathbb{Z}_+\).
We have \(a^{-nm} (a^n)^m = 1\)
\((a^n)^{-m} = a^{-nm}\)

For \(a,b \neq 0\) and \(m \in \mathbb{Z}\) we have \(a^m b^m = (ab)^m\).

I'd written up some more solutions but Blogger ate them. I'm skipping ahead.

Exercise 8(c)

Show that given \(a\) with \(0 < a < 1\), \( \inf \{a^n \mid n \in \mathbb{Z}_+ \} = 0\).

Solution

\( \langle 1 \rangle 1 \) Let \(h = (1-a)/a\)
\( \langle 1 \rangle 2 \) For \(n \in \mathbb{Z}_+\) we have \((1+h)^n \geq 1+nh\).

\((1+h)^1 = 1+1h\)

Both are equal to \(1+h\).

For \(n \in \mathbb{Z}_+\), if \((1+h)^n \geq 1+nh\) then \((1+h)^{n+1} \geq 1+(n+1)h\).

Let \(n \in \mathbb{Z}_+\). Assume \((1+h)^n \geq 1+nh\).
\((1+h)^{n+1} \geq 1+(n+1)h\)

0 is a lower bound for \(\{a^n \mid n \in \mathbb{Z}_+\}\).

\(0 < a^1\)
For any positive integer \(n\), if \(0 < a^n\) then \(0 < a^{n+1}\).

Because \(a^{n+1} = a^n a\) is the product of two positive reals.

For any lower bound \(l\) for \(\{a^n \mid n \in \mathbb{Z}_+\}\), we have \(l \leq 0\).

\( \langle 2 \rangle 1 \) Let \(l\) be a lower bound for \(\{a^n \mid n \in \mathbb{Z}_+\}\).
Assume for a contradiction \(l > 0\).
\( \langle 2 \rangle 2 \) Pick a positive integer \(n\) such that \(n > (1/l - 1)/h \).

Archimedean property.

We have \(1/a^n > 1/l\)
\(a^n < l\)
This contradicts \(\langle 2 \rangle 1 \).

\(\Box\)

Exercise 9

(a)

Show that every nonempty subset of \(\mathbb{Z}\) that is bounded above has a largest element.

Solution

Let \(S\) be a nonempty subset of \(\mathbb{Z}\) bounded above.
Pick \(k \in S\)
There exists a positive integer \(n\) such that \(k+n-1\) is an upper bound for \(S\).

Pick an upper bound \(u\) for \(S\).
Pick a positive integer \(n\) such that \(u -k + 1 \leq n\).

Archimedean property.

\(u \leq k + n - 1\)
\(k + n - 1\) is an upper bound for \(S\).

Let \(n\) be the least positive integer such that \(k + n-1\) is an upper bound for \(S\).
\(k + n - 1 \in S\)

Case \(n = 1\)

\( k + n - 1 = k \in S\)

Case \(n \neq 1\)

If \(k + n - 1 \notin S\) then \(k + n - 2\) is an upper bound for \(S\), contradicting the leastness of \(n\).

\(k + n - 1\) is the greatest element in \(S\).
\(\Box\)

(b)

If \(x \notin \mathbb{Z}\), show that there is exactly one \(n \in \mathbb{Z}\) such that \(n < x < n+1\).

Solution

Let \(S = \{n \in \mathbb{Z} : n < x \}\).
\(S\) is a nonempty set of integers bounded above.

\(S\) is nonempty.

Pick an integer \(m\) such that \(-x < m\).

Archimedean property.

\(-m \in S\)

\(S\) is bounded above by \(x\).

Let \(n\) be the largest element of \(S\).

By part (a).

\( n < x \)

Since \(n \in S\).

\( x < n + 1 \)

\(x \leq n+1\)

Otherwise \(n+1 \in S\).

\(x \neq n+1\)

Since \(x\) is not an integer.

If \(m\) is an integer and \(m < x < m+1\) then \(m = n\).

Let \(m\) be an integer such that \(m < x < m+1\).
\(m \in S\)
For all \(m' > m\) we have \(m' \geq m+1\) and so \(m' \notin S\).
\(m = n\)

Since both \(m\) and \(n\) are the greatest element of \(S\).

\(\Box\)

(c)

If \(x-y>1\), show that there is at least one \(n \in \mathbb{Z}\) such that \(y < n < x\).

Solution

Let \(n\) be the integer such that \(n < x < n+1\).
\(y < n\)

Since \(y < x-1 < n\).

(d)

If \(y < x\), show that there is a rational number \(z\) such that \(y < z < x\).

Solution

Let \(y < x\).
Pick a positive integer \(n\) such that \(nx - ny > 1\).

By the Archimedean property, there exists a positive integer \(n\) such that \(n > 1/(x-y)\).

Pick an integer \(m\) such that \(ny < m < nx\).

By part (c)

\(y < m/n < x\)
\(\Box\)