1.2: Basic Axioms for Z

Basic Properties of \(\mathbb{Z}\)

Since number theory is concerned with properties of the integers, we begin by setting up some notation and reviewing some basic properties of the integers that will be needed later. We begin with our fundamental sets and their notation. Recall that \(x\in S\) means that \(x\) is an element of the set \(S\), and \(S \subset T\) means that set \(S\) is a subset of set \(T\).

\[\begin{aligned} \mathbb{N} &=\{1,2,3,\cdots\} \quad \text{(the set of }\textbf{natural numbers}\text{ or positive integers)} \\ \mathbb{Z} &=\{\cdots,-3,-2,-1,0,1,2,3,\cdots\} \quad\text{(the set of }\textbf{integers}) \\ \mathbb{Q} &=\left\{ \frac{n}{m} \mid n,m\in\mathbb{Z}\text{ and }m\neq 0\right\} \quad \text{(the set of }\textbf{rational numbers}) \\ \mathbb{R} &=\text{the set of }\textbf{real numbers}\\ \mathbb{C} &= \left\{a+bi \mid a,b \in \mathbb{R} \right\} \quad \text{(the set of }\textbf{complex numbers})\end{aligned}\]

In the last line, recall from previous mathematics classes that \(i\) is a (non-real, imaginary) number satisfying \(i^2=-1\). Note that \(\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R} \subset \mathbb{C}\).

We assume a knowledge of the basic rules of high school algebra which apply to \(\mathbb{R}\) and therefore to \(\mathbb{N}\), \(\mathbb{Z}\) and \(\mathbb{Q}\). This means things like \(ab=ba\) and \(ab+ac=a(b+c)\). (Most of these properties also apply to numbers in \(\mathbb{C}\).) We will not list all of these properties here. However, below we list some particularly important properties of \(\mathbb{Z}\) that will be needed. We call these axioms since we will not prove them in this course.\(^{1}\)

Some Basic Axioms for \(\mathbb{Z}\)

1. If \(a\), \(b\in\mathbb{Z}\), then \(a+b\), \(a-b\) and \(ab\in\mathbb{Z}\). (\(\mathbb{Z}\) is closed under addition, subtraction and multiplication.)
2. If \(a\in\mathbb{Z}\) then there is no \(x\in\mathbb{Z}\) such that \(a<x<a+1\).
3. If \(a\), \(b\in\mathbb{Z}\) and \(ab=1\), then either \(a=b=1\) or \(a=b=-1\).
4. Laws of Exponents: For \(n\), \(m\) in \(\mathbb N\) and \(a\), \(b\) in \(\mathbb{R}\) we have
   1. \(\left( a^n \right)^ m=a^{nm}\)
   2. \((ab)^n=a^nb^n\)
   3. \(a^na^m=a^{n+m}\).

   These rules hold for all \(n,m \in \mathbb{Z}\) if \(a\) and \(b\) are not zero.

5. Properties of Inequalities: For \(a\), \(b\), \(c\) in \(\mathbb{R}\) the following hold:
   1. (Transitivity) If \(a<b\) and \(b<c\), then \(a<c\).
   2. If \(a<b\) then \(a+c<b+c\).
   3. If \(a<b\) and \(0<c\) then \(ac<bc\).
   4. If \(a < b\) and \(c < 0\) then \(bc < ac\).
   5. (Trichotomy) Given \(a\) and \(b\), one and only one of the following holds: \[a=b , \quad a<b , \quad b<a.\nonumber \]
6. The Archimedean Property: For every real number \(r\) there exists a natural number \(n\) such that \(n>r\). In other words, the set \(\mathbb{N}\) is a subset of \(\mathbb{R}\) that has no upper bound.
7. The Well-Ordering Principle: Every non-empty subset of \(\mathbb{N}\) contains a least element.
8. The Principle of Mathematical Induction: Let \(P(n)\) be a statement concerning the integer variable \(n\). Let \(n_0\) be any fixed integer. \(P(n)\) is true for all integers \(n \ge n_0\) if one can establish both of the following statements:
   1. \(P(n)\) is true if \(n=n_0\).
   2. Whenever \(P(n)\) is true for \(n_0\le n\le k\) then \(P(n)\) is true for \(n=k+1\).

The use of the Principle of Mathematical Induction in proofs will be discussed in the next chapter. We illustrate a use of the Archimedean Property momentarily.

We use the usual conventions:

1. \(a\leq b \text{ means } a<b \text{ or } a=b\),
2. \(a>b \text{ means } b<a\), and
3. \(a\geq b \text{ means } b\leq a\).

Floors and ceilings of real numbers

Since this chapter discusses basic properties of integers and their relationships with real numbers, we take this opportunity to define the floor, a.k.a., the greatest integer, and the ceiling, a.k.a., the least integer, functions. According to Donald Knuth [6], who popularized the notation presented below, Kenneth Iverson introduced the notation, as well as the terms floor and ceiling, in the early 1960s. Since then the notation has become standard in most areas of mathematics.

Definition \(\PageIndex{1}\)

If \(x\) is any real number we define \[\lfloor x\rfloor =\text{ the greatest integer less than or equal to }x\text{, and}\nonumber\] \[\lceil x\rceil =\text{the least integer greater than or equal to }x.\nonumber\]

Here \(\lfloor x\rfloor \) is called the floor of \(x\) and \(\lceil x\rceil \) is called the ceiling of \(x\). (Note: the floor \(\lfloor x\rfloor \) is in some texts denoted \([x]\) and called the greatest integer function.) Here are a few simple examples:

1. \(\lfloor 3.1\rfloor =3\text{ and }\lceil 3.1\rceil =4\)
2. \(\lfloor 3\rfloor =3\text{ and }\lceil 3\rceil =3\)
3. \(\lfloor -3.1\rfloor =-4\text{ and }\lceil -3.1\rceil =-3\)

For a more detailed treatment of both the floor and ceiling see the book Concrete Mathematics [5].
By the definitions, we have \[\lfloor x\rfloor =\max\{n\in\mathbb{Z}|n\leq x\}\text{ and }\lceil x\rceil =\min\{n\in\mathbb{Z}|n\geq x\}.\nonumber\]

The fact that \(\lfloor x\rfloor \) exists for every real number \(x\) follows from the Archimedean Property and the Well-Ordering Principle. By a similar argument (see Exercise \(\PageIndex{6}\)), \(\lfloor x\rfloor\) also exists for every real number \(x\).

By definition, \(\lfloor x\rfloor\leq x\) for all \(x\). Going further, note that for an integer \(n\), \[\lfloor x\rfloor =n\iff n\leq x<n+1.\label{eq:1}\] By Basic Axiom 2 above we also have that \[\lfloor x\rfloor =x\iff x\in\mathbb{Z} .\nonumber\]

The following lemma is helpful in proving facts involving floors.

Lemma \(\PageIndex{1}\)

For all \(x\in\mathbb{R}\) \[x-1<\lfloor x\rfloor\leq x.\nonumber\]

Proof

Let \(n =\lfloor x\rfloor\). Then by \(\eqref{eq:1}\) we have \(n\leq x<n+1\). This gives immediately that \(\lfloor x\rfloor\leq x\), as already noted above. It also gives \(x < n + 1\) which implies that \(x-1<n\), that is, \(x-1<\lfloor x\rfloor\).

Important Convention

Since in this course we will be almost exclusively concerned with integers we shall assume from now on, unless otherwise stated, that all lower case roman letters \(a,b,\ldots ,z\) denote integers.

Exercises

Exercise \(\PageIndex{1}\)

Using only the properties of inequalities listed in this chapter, and stating which ones you use (in other words, do not assume anything else about how inequalities behave when you operate on them), carefully prove that if \(x\) and \(y\) are positive real numbers and \(x < y\), then

1. \(x^2<y^2;\)
2. \(x<y+5;\)
3. \(x^3+2x+3<y^3+2y+4.\)

Exercise \(\PageIndex{2}\)

Find \(\lfloor\pi\rfloor\), \(\lceil\pi\rceil\), \(\lfloor\sqrt{2}\rfloor\), \(\lceil\sqrt{2}\rceil\), \(\lfloor -\pi\rfloor\), \(\lceil -\pi\rceil\), \(\lfloor -\sqrt{2}\rfloor\), and \(\lceil -\sqrt{2}\rceil\).

Exercise \(\PageIndex{3}\)

Sketch the graph of the function \(f(x) = \lfloor x\rfloor\) for \(-3.5\leq x\leq 3.5\).

Exercise \(\PageIndex{4}\)

Sketch the graph of \(y=\lceil x\rceil -\lfloor x\rfloor\) for \(-3.5\leq x\leq 3.5\), and describe in words how the function \(f(x) = \lceil x\rceil -\lfloor x\rfloor\) behaves for all \(x\in\mathbb{R}\).

Exercise \(\PageIndex{5}\)

If \(x\) is a real number, are \(\lfloor 2x\rfloor\) and \(2\lfloor x\rfloor\) always the same? If not, then which one is bigger than the other? Does the answer depend on whether \(x\) is positive, negative, or zero? Once you think you know the answer, state your answer as an inequality, and carefully prove it by using Lemma \(\PageIndex{1}\) and properties of inequalities or equations.

Exercise \(\PageIndex{6}\)

Prove that \(\lfloor x\rfloor\), as it has been defined in this chapter, exists for every real number \(x\).
(Hint: either think about what would happen if \(\lfloor x\rfloor\) didn't exist, and explain why this violates one or more of the Basic Axioms in this chapter, or show that \(\lfloor x\rfloor =-\lceil -x\rceil\) for all real numbers \(x\) and rely on the fact that ceilings always exist, as explained in this chapter.)

Footnotes

[1] These are not the simplest axioms we could use. Indeed, the Archimedean Property follows from a stronger property of \(\mathbb{R}\), and strictly speaking, the Well-Ordering Principle and Principle of Mathematical Induction shouldn't both be axioms, since each can be derived from the other.