# Applied Combinatorics

## SectionB.17Obtaining the Reals from the Rationals

A full discussion of this would take us far away from a discrete math class, but let’s at least provide the basic definitions. A subset $$S\subset \rats$$ of the rationals is called a cut (also, a Dedekind cut), if it satisfies the following properties:
1. $$\emptyset\neq S\neq \rats\text{,}$$ i.e, $$S$$ is a proper non-empty subset of $$\rats\text{.}$$
2. $$x\in S$$ and $$y\lt x$$ in $$\rats$$ implies $$y\in S\text{,}$$ for all $$x,y\in \rats\text{.}$$
3. For every $$x\in S\text{,}$$ there exists $$y\in S$$ with $$x\lt y\text{,}$$ i.e., $$S$$ has no greatest element.
Cuts are also called real numbers, so a real number is a particular kind of set of rational numbers. For every rational number $$q\text{,}$$ the set $$\bar{q}= \{p\in \rats: p\lt q\}$$ is a cut. Such cuts are called rational cuts. Inside the reals, the rational cuts behave just like the rational numbers and via the map $$h(q)=\bar{q}\text{,}$$ we abuse notation again (we are getting used to this) and say that the rational numbers are a subset of the real numbers.
But there are cuts which are not rational. Here is one: $$\{p\in \rats: p\le 0\}\cup \{p\in \rats: p^2\lt 2\}\text{.}$$ The fact that this cut is not rational depends on the familiar proof that there is no rational $$q$$ for which $$q^2=2\text{.}$$
The operation of addition on cuts is defined in the natural way. If $$S$$ and $$T$$ are cuts, set $$S+T=\{s+t:s\in S, t\in T\}\text{.}$$ Order on cuts is defined in terms of inclusion, i.e., $$S\lt T$$ if and only if $$S\subsetneq T\text{.}$$ A cut is positive if it is greater than $$\bar{0}\text{.}$$ When $$S$$ and $$T$$ are positive cuts, the product $$ST$$ is defined by
\begin{equation*} ST= \bar{0}\cup\{st:s\in S, t\in T, s\ge0, t\ge 0\}. \end{equation*}
One can easily show that there is a real number $$r$$ so that $$r^2=\bar{2}\text{.}$$ You may be surprised, but perhaps not, to learn that this real number is denoted $$\sqrt2\text{.}$$
There are many other wonders to this story, but enough for one day.