Real Analysis/Counting Numbers

←Contents

Real Analysis Ordered Sets

Ordered Fields→

Ordered Sets

An ordered set is a group of objects with an unambiguous sense of what is bigger. Instead of giving an abstract definition of ordering we will begin with some examples of ordered sets and explore what basic assumptions are necessary to flesh them out. This approach, though not as rigorous, should be more approachable. Our first and most important set is the natural numbers.

Natural Numbers

The basic set of analysis is the natural numbers $\mathbb {N} =\{1,2,3,\ldots \}$ (Some authors take $\{0,1,2,\ldots \}$ — when we wish to refer to this set, we use $\mathbb {N} _{0}$). The natural numbers are all you need for counting. This set is defined by its properties. The first property of the set of natural numbers $\mathbb {N}$ is that it has an equivalence relation $=\$ meaning the following axioms are satisfied:

1. Reflexivity

   For all $n\in \mathbb {N} ,\ n=n;$

2. Symmetry

   For all $n,m\in \mathbb {N} ,\ n=m$ if and only if $m=n$;

3. Transitivity

   For all $n,m,l\in \mathbb {N}$ if $n=m$ and $m=l$, then $n=l$;

These terse mathematical statements can be written in a less rigorous way. The first statement simply states that every natural number is equal to itself. The second states that the statement of equality is true regardless of the order you say it. The last statement says that when two natural numbers are equal and one of them equals something else they all three must be equal. These are the simple assumptions we make when we loosely talk about equality. This short list gives us a way to check if a proposed equality satisfies our notions of what it means for two things to be equal. Associated with this equivalence relation is an ordering meaning these additional axioms are satisfied:

1. Trichotomy

   For all $m,n\in \mathbb {N}$, one and only one of the following hold:

   $m<n$

   $m=n$

   $m>n$

   The notation $m\leq n$ means $m<n$ or $m=n$, and the notation $m\geq n$ means $m>n$ or $m=n$.

2. Transitivity of < and >.

   For all $n,m,l\in \mathbb {N}$, if $n<m$ and $m\leq l$, then $n<l$.

   For all $n,m,l\in \mathbb {N}$, if $n>m$ and $m\geq l$, then $n>l$.

Trichotomy means that any two natural numbers are either equal or the bigger number can be uniquely chosen. Transitivity says that, if there is a third number that is bigger than the biggest of our first two, then it is bigger than the smaller one as well. With this we now have a concise definition of what it means for our numbers to have an order. Finally the natural numbers $\mathbb {N}$ have an associated operation called addition. The set $\mathbb {N}$ and the operation of addition $+$ satisfy the following axioms:

1. Closure

   For all $n,m\in \mathbb {N} ,n+m\in \mathbb {N}$.

2. Commutativity

   For all $n,m\in \mathbb {N} ,\ n+m=m+n$.

3. Associativity

   For all $n,m,l\in \mathbb {N} ,\ n+(m+l)=(n+m)+l$.

   Meaning we can unambiguously write $n+m+l$

4. Compatibility with Ordering

   For all $n,m\in \mathbb {N} ,\ n<n+m$

Meaning if we add two natural numbers the result is a natural number. The order in which we add the numbers is not important and if I add two natural numbers the sum is bigger than either of the ones I started with. This is our notion of addition of positive numbers simplified to the basic assumptions. There is only one more assumption needed to bring the natural numbers as we know them into a well defined existence, the set of natural numbers is not empty. We can name the smallest element of $\mathbb {N}$ the number 1.

There exists a number $1\in \mathbb {N}$ so that $1\leq n$ for all $n\in \mathbb {N}$

This statement simply says one exists and is less than or equal to any other natural number. With these assumptions we can go on and derive all the properties of $\mathbb {N}$.

Multiplication

On the natural numbers we can define a second operator, multiplication $\times$. The concept of multiplication on $\mathbb {N}$ is simply a shorthand for repeated addition. Here are the axioms of multiplication.

1. Closure

   For all $n,m\in \mathbb {N} ,\ n\times m\in \mathbb {N}$.

2. Identity

   For all $n\in \mathbb {N} ,\ n\times 1=n$.

3. Commutativity

   For all $n,m\in \mathbb {N} ,\ n\times m=m\times n$.

4. Associativity

   For all $n,m,l\in \mathbb {N} ,\ (n\times m)\times l=n\times (m\times l)$,

   meaning we may unambiguously write $n\times m\times l$.

5. Distributivity

   For all $n,m,l\in \mathbb {N} ,\ n\times (m+l)=n\times m+n\times l$.

6. Compatibility with ordering

   For all $n,m\in \mathbb {N} ,\ m\leq n\times m$.

Meaning natural numbers when multiplied give natural numbers. Any number times 1 gives itself. The order and the grouping is not important for multiplication. The last two give how multiplication behaves with respect to addition and the ordering on $\mathbb {N}$. Always writing $n\times m$ for multiplication is tedious so we abbreviate it as $nm\$. Furthermore we abbreviate a repeated product of a particular number with a superscript counting the number of times the number is repeated. For example,

$n\times n\equiv n^{2}.$

Peano Axioms

An alternate derivation of the set of natural numbers can be characterized by a few axioms called the Peano or Dedekind–Peano axioms. A slight modification of the definitions of addition and multiplication in the Peano axioms would construct a different set where the element "0" (soon to be described) can actually be some natural number different from 0. These axioms can thus serve as the definition of the set of natural numbers.

1. $\exists 0\in \mathbb {N} _{0}$

   There exists an element called "0" within the set of natural numbers.

2. $\forall x\in \mathbb {N} _{0}\ \exists S_{x}\in \mathbb {N} _{0}$

   Every natural number has a successor which is also a natural number.

3. $\forall x\in \mathbb {N} _{0}\ S_{x}\not =0$

   There is no natural number whose successor is 0.

4. $\forall x,y\in \mathbb {N} _{0}\ S_{x}=S_{y}\implies x=y$

   The successor function is one-to-one.

5. $\left(0\in A\land \left(x\in A\implies S_{x}\in A\right)\right)\implies \mathbb {N} _{0}\subset A$

   Mathematical induction: if 0 is within the set, and n being within the set implies that its successor is also within the set, then all natural numbers are within the set.

A natural number can be defined as an element of the set of natural numbers. These axioms can be used to prove very important basic theorems about basic operations and predicates, which are addition, multiplication, and order. Addition and multiplication are very important binary operators, and ordering is a very important binary predicate. They can be defined as follows:

• Ordering

  $S_{y}>y\$

  The successor of a number y is greater than the number y.

  $x>y\implies S_{x}>y$

  If a number x is greater than a number y then the successor of x is greater than y.

• Addition

  $x+0=x\$

  The sum of any number and zero returns the number.

  $x+S_{y}=S_{x+y}\$

  The sum of a number x and the successor of a number y is the successor of the sum of x and y.

• Multiplication

  $x\ 0=0$

  The product of any number and zero is zero.

  $x\ S_{y}=x+xy$

  The product of a number x and the successor of a number y is the sum of x and the product of x and y.

It is not necessary to know these definitions to know what addition, multiplication, and ordering mean. However, these definitions show how it is possible to construct addition, multiplication, and ordering from the Peano axioms.

Alternative constructions of addition and multiplication

The basic element does not necessarily have to be an identity for addition. Indeed, if the definitions of addition and multiplication were defined differently then the basic element is commonly written "1".

1. $\exists 1\in \mathbb {N}$

   1 is an element of the set.

2. $\forall x\in \mathbb {N} \implies (x+1)\in \mathbb {N} \$

   For any natural number x the sum of x and 1 is also a natural number.

3. $\forall x\in \mathbb {N} \ x+1\neq x$

   The sum of any natural number x and 1 is different from x.

4. $\forall x,y\in \mathbb {N} \ x+1=y+1\implies x=y$

   Adding one is a one-to-one function.

5. $(1\in A\land (x\in A\implies (x+1)\in A))\implies \mathbb {N} \subset A$

   Mathematical induction: If 1 is an element of a set A, where for any element x of A the sum of x and 1 is also in the set, then all the natural numbers are in the set A.

Zermelo Fraenkel Axioms

The natural numbers can also be constructed from sets. This is not a necessary step, and may be skipped, but it shows that set theory provides a sufficient basis for explaining the natural numbers. The Zermelo Fraenkel axioms provide sufficient conditions for a set which satisfies the Peano axioms.

1. Let 0 be associated with the empty set $\emptyset$.
2. Let the set $S_{n}=n\cup \{n\}$

   The successor of a natural number n is the union of the set associated with n and the set containing n. Thus, each natural number is a set containing its predecessors.

   For example, let 0 := $\emptyset$, then 1 := $S_{0}=0\cup \{0\}=\emptyset \cup \{0\}$ = {0}

   $2:=S_{1}=1\cup \{1\}$ = {0}∪{1} = {0} ∪ {{0}} = {0, {0}} = and hence {0,1}, 3 is {0,1,2}, and so on.

3. $\exists \mathbb {N} _{0}:\emptyset \in \mathbb {N} _{0}\land \left(\forall x\in \mathbb {N} _{0}\ x\cup \{x\}\in \mathbb {N} _{0}\right)$

   There is a set called $\mathbb {N} _{0}$ containing $\emptyset$ (the null set) and such that for any element x, the set $x\cup \{x\}$ is also within the set. This axiom is called the axiom of infinity and the set so constructed is identified with the natural numbers.

This construction of the natural numbers obviously satisfies the first three Peano axioms. The fact that S_x=S_y→x=y holds can be seen easily by the fact that $x\cup \{x\}=y\cup \{y\}\implies x=y$. The fifth Peano axiom holds because if $\emptyset \in A\land \left(\forall x\in A\ x\cup \{x\}\in A\right)$, then this set would be the natural numbers, and so the natural numbers would be a trivial subset of A.

Integers

If we extend $\mathbb {N}$ by adding $0,$ we can get the notion of an identity for addition, given by:

$\exists 0:\forall n\in \mathbb {N} ,\ n+0=n,$

stating that there is a number $0$, which, when added to a natural number, gives that number back again. Here we have a choice to make: where in our ordering does $0$ fit? The usual choice is $0<1$ and is the one we will make here, though it is worth pointing out the curious nature of this choice. Having defined zero, the possibility of an inverse of $\mathbb {N}$ arises. We denote the set of inverses as $\mathbb {-N}$, and the set satisfies the following axiom:

$\forall n\in \mathbb {N} ,\ \exists (-n)\in \mathbb {-N} :n+(-n)=0.$

Combining all three we obtain the integers

$\mathbb {Z} =\{\mathbb {N} \}\cup \{0\}\cup \{\mathbb {-N} \}=\{\ldots ,-3,-2,-1,0,1,2,3,\ldots \}$.

The integers allow us to keep track of debts as well as count things, in other words to perform accounting. If you assume that the axioms for addition hold where the well ordering assumes takes the form

$(\forall z\in \mathbb {Z} )(\forall n\in \mathbb {N} ),\ z<z+n,$

and that the identity, closure and distributivity of multiplication hold for the integers $\mathbb {Z} ,$ then the multiplication operation can also be expanded to include all the integers $\mathbb {Z} .$

They can be constructed from the natural numbers easily. They can each be equivalence classes of ordered pairs (a,b) where a and b are both natural numbers. Then one can say that (a,b) and (c,d) are equal when a+d=b+c, the sum (a,b)+(c,d)=(a+c,b+d) and the product (a,b)(c,d)=(ac+bd,ad+bc) where the definitions of the sum and product of natural numbers are used. There is an additive identity element in the form (a,a) because (a,a)+(b,c)=(a+b,a+c) which is equivalent to (b,c) because a+b+c=a+b+c. All such elements of the form (a,a) are obviously equivalent. All elements (a,b) have the additive inverse (b,a) because (a,b)+(b,a)=(a+b,a+b). The best way to think of these ordered pairs (a,b) is to think of them as a-b. Thus, (a,a) can be thought of as "0."

Absolute Value

Typically, we think of the integers as extending to positive and negative infinity. Since this geometric notion is so fundamental to our understanding, we should like to talk about geometric properties. In particular, we need to know what is meant by the distance between two integers. To this end, we define the symbol $|x|$ as the function that gives the distance from $x$ to zero by mapping $\mathbb {-N}$ onto their respective inverses in $\mathbb {N}$ and mapping zero onto itself.

$|x|=\left\{{\begin{matrix}x&{\mbox{if }}x\geq 0\\-x&{\mbox{if }}x<0\\\end{matrix}}\right.$

We can now define the distance between two integers, which we refer to as points in any geometric context, by taking the absolute value of their difference: $d(x,y)=|x-y|\$. This distance function satisfies some nice, geometric properties:

1. Positivity

   $d(x,y)\geq 0$ and is equal to 0 iff $x=y$.

2. Symmetry

   $d(x,y)=d(y,x).$

3. Triangle Inequality

   $d(x,y)+d(y,z)\geq d(x,z).$

Pay special attention to the triangle inequality, as it will be used very often in later chapters.

In general, any set with a distance function satisfying these properties is called a metric space. It is easy to show that the integers form a metric space under the metric d:

1. Positivity
   • If $x\geq 0$, then $|x|=x\geq 0$.
   • If $x<0\$, then $|x|=-x\ >0$.
2. Symmetry
   • If $x-y\geq 0$, then $y-x\leq 0$, so $|x-y|=x-y=-(y-x)=|y-x|\$.
   • If $x-y\ <0$, then $y-x>0\$, so $|x-y|=-(x-y)=y-x=|y-x|\$.
3. Triangle Inequality
   • If $x\geq 0$, then $|x|=x\geq 0>-|x|$.
   • If $x<0\$, then $|x|>0>x=-|x|\$.
   • This gives us $-|x|\leq x\leq |x|$ and $-|y|\leq y\leq |y|$.
   • Adding, we see that $-(|x|+|y|)\leq x+y\leq |x|+|y|$.
   • If $x+y\geq 0$, then $|x+y|=x+y\leq |x|+|y|$.
   • If $x+y<0\$, then $|x+y|=-(x+y)\leq |x|+|y|$.
   • Thus in all cases $|x+y|\leq |x|+|y|$.
   • Replacing $x\$ with $x-y\$ and $y\$ with $y-z\$ yields $|x-y|+|y-z|\geq |x-z|$.

Another fundamental property of the absolute value is that it is multiplicative:

$|x||y|=|xy|.$

The proof is left as an exercise. As above, it is simply a matter of checking all the cases.