Dedekind Cuts

Peano Natural Numbers

A Peano system consists of a set

ℕ

, an element

0 \in ℕ

, and a function

S : ℕ \to ℕ

, called the successor function, such that:

$0 \notin S (ℕ)$ .
$S$ is injective.
If $A \subseteq ℕ$ , $0 \in A$ , and $S (A)$ $\subseteq A$ , then $A = ℕ$ .

The elements of

ℕ

are called natural numbers.

The familiar natural numbers are recovered by repeatedly applying the successor function from the Peano natural numbers. We write $1 : = S (0), 2 : = S (1), 3 : = S (2), \dots$ so $S$ is the operation of moving to the next natural number. The final Peano axiom is the induction principle. To prove a statement $P (n)$ for every $n \in ℕ$ , it is enough to prove $P (0)$ , and then prove that $P (n)$ implies $P (S (n))$ . Indeed, let $A$ be the set of natural numbers for which $P$ is true. The base case says $0 \in A$ , and the implication $P (n) \Rightarrow P (S (n))$ says that whenever $n \in A$ , its successor $S (n)$ is also in $A$ . Thus $A$ contains $0$ , then $S (0)$ , then $S (S (0))$ , and so on. The Peano induction axiom says that any subset of $ℕ$ with this property must already be all of $ℕ$ , so $P$ holds for every natural number.

Another way to read the induction axiom is that a proper finite initial piece of the natural numbers cannot be closed under successors. If $A$ contains only finitely many familiar natural numbers, then among them there is a last one, the number obtained by applying $S$ the most times. Applying $S$ to that element produces the next natural number, which was not already in $A$ . Thus for such a finite $A$ , the image $S (A)$ would include an element outside $A$ , so $S (A) \subseteq A$ would fail. The axiom says that the only subset of $ℕ$ that contains $0$ and survives this successor test forever is $ℕ$ itself.

Recursive Addition on Natural Numbers

Addition on

ℕ

is defined recursively by

a + 0 = a, a + S (b) = S (a + b) .

Recursive Multiplication on Natural Numbers

Multiplication on

ℕ

is defined recursively by

a \cdot 0 = 0, a \cdot S (b) = a \cdot b + a .

Zero is Additive Identity for Natural Numbers

The element

0

is an identity element for addition on

ℕ

. That is, for every

a \in ℕ

0 + a = a = a + 0.

We must show that $0 + a = a$ and that $a + 0 = a$ for every $a \in ℕ$ . The latter equality is part of the recursive definition of addition.

To handle $0 + a = a$ , we prove the claim by induction on $a$ . For the base case, $0 + 0 = 0$ by the recursive definition. Now assume $0 + k = k$ for some $k \in ℕ$ . We want to show that $0 + S (k) = S (k)$ . By the recursive definition, $0 + S (k) = S (0 + k) .$ By the inductive hypothesis, $0 + k = k$ , so $S (0 + k) = S (k)$ . Therefore $0 + S (k) = S (k)$ . By induction, $0 + a = a$ for every $a \in ℕ$ , so $0$ is an identity element for addition.

Addition on Natural Numbers is Associative

The recursively defined addition on

ℕ

is associative. That is, for all

a, b, c \in ℕ

(a + b) + c = a + (b + c) .

Let $a, b \in ℕ$ . We prove the claim by induction on $c$ .

For the base case, suppose $c = 0$ . We want to show $(a + b) + 0 = a + (b + 0) .$ Since zero is an additive identity, we have $(a + b) + 0 = a + b$ and $a + (b + 0) = a + b$ . Thus the base case holds.

Now assume $(a + b) + c = a + (b + c) .$ We want to prove $(a + b) + S (c) = a + (b + S (c)) .$ By the recursive definition of addition, $(a + b) + S (c) = S ((a + b) + c) .$ On the other hand, start with $a + (b + S (c))$ . Applying the same recursive rule to $b + S (c)$ gives $b + S (c) = S (b + c)$ . Then applying the recursive rule again to $a + S (b + c)$ gives $a + (b + S (c)) = a + S (b + c) = S (a + (b + c)) .$ By the inductive hypothesis, $a + (b + c) = (a + b) + c$ , so both sides are equal to $S ((a + b) + c)$ . Therefore addition is associative.

Addition on Natural Numbers is Commutative

The recursively defined addition on

ℕ

is commutative. That is, for all

a, b \in ℕ

a + b = b + a .

First prove by induction on $b$ that $S (a) + b = S (a + b) .$ The base case follows from $S (a) + 0 = S (a) = S (a + 0)$ , and the successor step follows by applying the recursive definition to both sides.

Now prove $a + b = b + a$ by induction on $b$ . The base case is $a + 0 = a = 0 + a$ , using that zero is an additive identity. If $a + b = b + a$ , then $a + S (b) = S (a + b) = S (b + a) = S (b) + a .$ Hence addition is commutative.

Successor of Zero is Multiplicative Identity for Natural Numbers

The element

S (0)

is an identity element for multiplication on

ℕ

. That is, for every

a \in ℕ

S (0) \cdot a = a = a \cdot S (0) .

First note that $S (a) = a + S (0)$ , since $a + S (0) = S (a + 0) = S (a) .$ Also $a \cdot 0 = 0$ by definition.

The element $S (0)$ is a right multiplicative identity because $a \cdot S (0) = a \cdot 0 + a = 0 + a = a,$ using that zero is an additive identity.

It is a left multiplicative identity by induction on $a$ . The base case is $S (0) \cdot 0 = 0$ . If $S (0) \cdot a = a$ , then $S (0) \cdot S (a) = S (0) \cdot a + S (0) = a + S (0) = S (a) .$ Thus $S (0)$ is a multiplicative identity.

Multiplication Distributes Over Addition on Natural Numbers

The recursively defined multiplication on

ℕ

distributes over addition. That is, for all

a, b, c \in ℕ

a \cdot (b + c) = a \cdot b + a \cdot c .

Fix $a, b \in ℕ$ and induct on $c$ . The base case follows from $a \cdot (b + 0) = a \cdot b = a \cdot b + 0 = a \cdot b + a \cdot 0.$ If $a \cdot (b + c) = a \cdot b + a \cdot c$ , then $a \cdot (b + S (c)) = a \cdot S (b + c) = a \cdot (b + c) + a = (a \cdot b + a \cdot c) + a = a \cdot b + a \cdot S (c),$ using associativity of addition in the last step. Hence multiplication distributes over addition.

Multiplication on Natural Numbers is Associative

The recursively defined multiplication on

ℕ

is associative. That is, for all

a, b, c \in ℕ

(a \cdot b) \cdot c = a \cdot (b \cdot c) .

Fix $a, b \in ℕ$ and induct on $c$ . The base case follows because both sides are $0$ . If $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ , then $(a \cdot b) \cdot S (c) = (a \cdot b) \cdot c + a \cdot b = a \cdot (b \cdot c) + a \cdot b = a \cdot (b \cdot c + b) = a \cdot (b \cdot S (c)),$ using distributivity in the third equality. Hence multiplication is associative.

Multiplication on Natural Numbers is Commutative

The recursively defined multiplication on

ℕ

is commutative. That is, for all

a, b \in ℕ

a \cdot b = b \cdot a .

First prove by induction on $b$ that $S (a) \cdot b = a \cdot b + b .$ The base case is $S (a) \cdot 0 = 0 = a \cdot 0 + 0$ . The successor step follows from the recursive multiplication rule together with associativity and commutativity of addition.

Now prove $a \cdot b = b \cdot a$ by induction on $b$ . The base case follows from $a \cdot 0 = 0 = 0 \cdot a$ , where $0 \cdot a = 0$ is proved by induction on $a$ . If $a \cdot b = b \cdot a$ , then $a \cdot S (b) = a \cdot b + a = b \cdot a + a = S (b) \cdot a .$ Hence multiplication is commutative.

Order on Natural Numbers

For

a, b \in ℕ

, define

a \leq b

if and only if there exists

c \in ℕ

such that

a + c = b

. Define

a < b

a \leq b

and

a \neq b

Natural Numbers are Well-Ordered

Every non-empty subset of

ℕ

has a least element with respect to the order on natural numbers.

Integer Pair Relation

ℕ \times ℕ

, define a relation by

(a, b) \sim (c, d) ⟺ a + d = c + b .

Integer Pair Relation is an Equivalence Relation

The integer pair relation is an equivalence relation.

Integers as Equivalence Classes

The integers, denoted

ℤ

, are the equivalence classes of

ℕ \times ℕ

under the integer pair relation. The class of

(a, b)

represents the formal difference

a - b

Addition and Multiplication of Integers

Let

[(a, b)], [(c, d)] \in ℤ

. Define

[(a, b)] + [(c, d)] = [(a + c, b + d)]

and

[(a, b)] \cdot [(c, d)] = [(a c + b d, a d + b c)] .

Integer Addition and Multiplication are Well-Defined

The operations of addition and multiplication of integers do not depend on the chosen representatives of the equivalence classes.

Negation of Integers

Let

[(a, b)] \in ℤ

. Define

- [(a, b)] = [(b, a)] .

Order on Integers

Let

[(a, b)], [(c, d)] \in ℤ

. Define

[(a, b)] \leq [(c, d)] ⟺ a + d \leq c + b .

Order on Integers is Well-Defined

The order on integers does not depend on the chosen representatives of the equivalence classes.

Integers Form an Ordered Integral Domain

The integers

ℤ

, with the operations and order defined above, form an ordered integral domain.

Rational Number Pair Relation

ℤ \times (ℤ ∖ {0})

, define a relation by

(a, b) \sim (c, d) ⟺ a d = b c .

Rational Number Pair Relation is an Equivalence Relation

The rational number pair relation is an equivalence relation.

Rational Numbers as Equivalence Classes

The rational numbers, denoted

ℚ

, are the equivalence classes of

ℤ \times (ℤ ∖ {0})

under the rational number pair relation. The class of

(a, b)

is denoted by

\frac{a}{b}

Addition and Multiplication of Rationals

Let

\frac{a}{b}, \frac{c}{d} \in ℚ

. Define

\frac{a}{b} + \frac{c}{d} = \frac{a d + b c}{b d}

and

\frac{a}{b} \cdot \frac{c}{d} = \frac{a c}{b d} .

Rational Addition and Multiplication are Well-Defined

The operations of addition and multiplication of rationals do not depend on the chosen representatives of the equivalence classes.

Additive and Multiplicative Inverses of Rationals

Let

\frac{a}{b} \in ℚ

. Define

- \frac{a}{b} = \frac{- a}{b} .

a \neq 0

, define

{(\frac{a}{b})}^{- 1} = \frac{b}{a} .

Order on Rationals

Let

\frac{a}{b}, \frac{c}{d} \in ℚ

. Choose representatives with

b > 0

and

d > 0

. Define

\frac{a}{b} < \frac{c}{d} ⟺ a d < b c .

Order on Rationals is Well-Defined

The order on rationals does not depend on the chosen positive-denominator representatives.

Rationals Form an Ordered Field

The rational numbers

ℚ

, with the operations and order defined above, form an ordered field.

Dedekind Cut

Let

A \subseteq ℚ

. The set

A

is a Dedekind cut if:

$A \neq \emptyset$ and $A \neq ℚ$ .
If $x \in A$ , $y \in ℚ$ , and $y \geq x$ , then $y \in A$ .
If $x \in A$ , then there exists $y \in A$ such that $y < x$ .

Rational Upper Rays are Dedekind Cuts

Let

r \in ℚ

. Then

{x \in ℚ : x > r}

is a Dedekind cut.

Rational Cut

Let

r \in ℚ

. The rational cut at $r$ , denoted

D_{r}

, is the Dedekind cut

D_{r} = {x \in ℚ : x > r} .

Irrational Cut

An irrational cut is a Dedekind cut that is not equal to

D_{r}

for any

r \in ℚ

Square Root Two Cut

The set

T = {x \in ℚ : x > 0 \land x^{2} > 2}

is the Dedekind cut corresponding to the missing rational boundary

\sqrt{2}

Complement of a Dedekind Cut

Let

A \subseteq ℚ

be a Dedekind cut. Then:

$ℚ ∖ A = {x \in ℚ : x < a for all a \in A}$ .
If $x \in ℚ ∖ A$ , $y \in ℚ$ , and $y \leq x$ , then $y \in ℚ ∖ A$ .

Dedekind Cuts are Linearly Ordered by Containment

Let

A, B \subseteq ℚ

be Dedekind cuts. Then exactly one of the following holds:

A ⊊ B, A = B, B ⊊ A .

Union of Dedekind Cuts is a Dedekind Cut

Let

𝒜

be a non-empty family of subsets of

ℚ

. Suppose that every

X \in 𝒜

is a Dedekind cut. If

⋃_{X \in 𝒜} X \neq ℚ,

then

⋃_{X \in 𝒜} X

is a Dedekind cut.

Dedekind Cut Operation Closure

Let

A, B \subseteq ℚ

be Dedekind cuts. Then:

${r \in ℚ : r = a + b for some a \in A and b \in B}$ is a Dedekind cut.
${r \in ℚ : - r < c for some c \in ℚ ∖ A}$ is a Dedekind cut.
If $0 \in ℚ ∖ A$ and $0 \in ℚ ∖ B$ , then ${r \in ℚ : r = a b for some a \in A and b \in B}$ is a Dedekind cut.
If there exists $q \in ℚ ∖ A$ such that $q > 0$ , then ${r \in ℚ : r > 0 and \frac{1}{r} < c for some c \in ℚ ∖ A}$ is a Dedekind cut.

Dedekind Cut Approximation

Let

A \subseteq ℚ

be a Dedekind cut.

If $y \in ℚ$ and $y > 0$ , then there exist $u \in A$ and $v \in ℚ ∖ A$ such that $y = u - v$ , and $v < e$ for some $e \in ℚ ∖ A$ .
If $y \in ℚ$ , $y > 1$ , and there exists $q \in ℚ ∖ A$ such that $q > 0$ , then there exist $r \in A$ and $s \in ℚ ∖ A$ such that $s > 0$ , $y > \frac{r}{s}$ , and $s < g$ for some $g \in ℚ ∖ A$ .

Real Numbers as Dedekind Cuts

The set of real numbers, denoted

ℝ

, is defined by

ℝ = {A \subseteq ℚ : A is a Dedekind cut} .

Order on Dedekind Real Numbers

Let

A, B \in ℝ

, where

ℝ

is defined as Dedekind cuts. Define

A < B ⟺ A ⊋ B,

and

A \leq B ⟺ A \supseteq B .

Addition and Negation of Dedekind Reals

Let

A, B \in ℝ

, where

ℝ

is defined as Dedekind cuts. Define

A + B = {r \in ℚ : r = a + b for some a \in A and b \in B}

and

- A = {r \in ℚ : - r < c for some c \in ℚ ∖ A} .

Order Comparison with Rational Cuts

Let

A \in ℝ

and

r \in ℚ

$A > D_{r}$ if and only if there exists $q \in ℚ ∖ A$ such that $q > r$ .
$A \geq D_{r}$ if and only if $r \in ℚ ∖ A$ , if and only if $a > r$ for all $a \in A$ .
If $A < D_{0}$ , then $- A \geq D_{0}$ .

Multiplication and Inverse of Dedekind Reals

Let

A, B \in ℝ

, where

ℝ

is defined as Dedekind cuts. Multiplication is defined by cases:

If $A \geq D_{0}$ and $B \geq D_{0}$ , then $A \cdot B = {r \in ℚ : r = a b for some a \in A and b \in B}$ .
If $A < D_{0}$ and $B \geq D_{0}$ , then $A \cdot B = - ((- A) \cdot B)$ .
If $A \geq D_{0}$ and $B < D_{0}$ , then $A \cdot B = - (A \cdot (- B))$ .
If $A < D_{0}$ and $B < D_{0}$ , then $A \cdot B = (- A) \cdot (- B)$ .

For

A \neq D_{0}

, multiplicative inverse is defined by cases:

If $A > D_{0}$ , then $A^{- 1} = {r \in ℚ : r > 0 and \frac{1}{r} < c for some c \in ℚ ∖ A}$ .
If $A < D_{0}$ , then $A^{- 1} = - ({(- A)}^{- 1})$ .

Dedekind Reals Form an Ordered Field

Let

A, B, C \in ℝ

, where

ℝ

is defined as Dedekind cuts. Then

ℝ

, with the operations and order defined above, satisfies the ordered-field laws: associativity and commutativity of addition and multiplication, additive and multiplicative identities

D_{0}

and

D_{1}

, additive inverses, multiplicative inverses for non-zero elements, distributivity, trichotomy, compatibility of addition with order, and compatibility of multiplication by positive elements with order.

Greatest Lower Bound Property for Dedekind Reals

Let

𝒜 \subseteq ℝ

. If

𝒜

is non-empty and bounded below, then

𝒜

has a greatest lower bound.

Least Upper Bound Property for Dedekind Reals

Let

𝒜 \subseteq ℝ

. If

𝒜

is non-empty and bounded above, then

𝒜

has a least upper bound.

Rationals Embed into Dedekind Reals

Define

i : ℚ \to ℝ

i (r) = D_{r}

for all

r \in ℚ

. Then:

The function $i : ℚ \to ℝ$ is injective.
$i (0) = D_{0}$ and $i (1) = D_{1}$ .
For $r, s \in ℚ$ , $i (r + s) = i (r) + i (s)$ .
For $r \in ℚ$ , $i (- r) = - i (r)$ .
For $r, s \in ℚ$ , $i (r s) = i (r) i (s)$ .
If $r \neq 0$ , then $i (r^{- 1}) = i {(r)}^{- 1}$ .
$r < s$ if and only if $i (r) < i (s)$ .