# Build $\mathbb{R}$ from $\mathcal{P}(\mathbb{N})$

It's well known that $\mathbb{R}$ has the same cardinality as $\mathcal{P}(\mathbb{N})$; but I would fain know if there is a way to construct $(\mathbb{R}, +,\cdot, \leq )$ using only definitions that rely upon $\mathcal{P}(\mathbb{N})$'s elements and their respective properties.

-
Have you seen the Dedekind cuts? –  Srivatsan Jan 25 '12 at 15:45
The real numbers in interval $(0,1\rangle$ can be described using infinite binary expansions, which are in bijective correspondence with infinite subsets of $\mathbb N$. –  Martin Sleziak Jan 25 '12 at 15:54
Have you read the following essay by Tim Gowers? dpmms.cam.ac.uk/~wtg10/decimals.html –  Christian Blatter Jan 25 '12 at 16:59
Not quite what you're asking for, but it's possible to construct $\mathbb R$ solely from $\mathbb Z$: Wikipedia. The construction draws on the idea that drawing a (non-vertical) line through $0$ on an infinite computer display ($\mathbb Z \times \mathbb Z$) corresponds to choosing a slope - which can be any real number –  kahen Feb 11 '12 at 21:59
For what it's worth, while interesting I don't see much point in such construction. The fact that we can prove that $\mathbb R$ has the same cardinality as $\mathcal P(\mathbb N)$ allows us to define it using the rationals and transfer the structure at will. –  Asaf Karagila Feb 19 '12 at 23:09

Although the variant construction I propose below still uses rationals, it is more directly and naturally related to ${\cal P}(\mathbb N)$ (and not to one of its quotients by some equivalence relation) and so gets closer to the "perfect" solution the OP is expecting. As noted in other answers here, it suffices to construct the field structure on the set $\cal S$ of inifinite sequences of zeroes and ones (thanks to characteristic functions).

Consider the following four types of intervals (in $\mathbb Q$) with rational endpoints :

$$T_1 = {\mathbb Q}, T_2(a) = ]-\infty,a[ \ (a\in {\mathbb Z}), T_3(a) = [a,+\infty [ \ (a\in {\mathbb Z}), T_4(a,b)= [a,b[ \ (a,b\in {\mathbb Q})$$

Let us denote by $\cal T$ the set of all those intervals. We define a "splitting map" $\sigma=(\sigma_1,\sigma_2)$ from $\cal T$ to ${\cal T}^2$. This map $\sigma$ splits any $I\in \cal T$ into two parts $\sigma_1(I)$ and $\sigma_2(I)$ such that $\sigma_1(I)$ is always "to the left" of $\sigma_2(I)$ (in the sense that $x\leq y$ whenever $x\in {\sigma}_1(I), y\in {\sigma}_2(I)$).

Here is the formal definition of $\sigma$ :

$$\sigma(T_1) = (T_2(0),T_3(0)), \\ \sigma(T_2(a)) = (T_2(a-1),T_4(a-1,a)), \\ \sigma(T_3(a)) = (T_4(a,a+1),T_3(a+1)), \\ \sigma(T_4(a,b))=(T_4(a,\frac{a+b}{2}),T_4(\frac{a+b}{2},b))$$

Now for any finite sequence $(a_1, \ldots ,a_n)$ with each $a_k$ in $\lbrace 0,1 \rbrace$, define an interval $I_{(a_1, \ldots ,a_n)}$ inductively~: for the empty sequence $()$ we set $I_{()}=T_1$, and for the others sequences we define $I_{(a_1, \ldots ,a_{n-1},0)}=\sigma_1(I_{(a_1, \ldots ,a_{n-1})})$ and $I_{(a_1, \ldots ,a_{n-1},1)}=\sigma_2(I_{(a_1, \ldots ,a_{n-1})})$.

For any $n\geq 1$ and $\varepsilon \in \lbrace 0,1 \rbrace$ let $J(n,\varepsilon)$ denote the union of all $I_{a}$ where $a$ is an $n$-element sequence ending with $\varepsilon$.

Let $a=(a_1,a_2, \ldots )$ and $b=(b_1,b_2, \ldots )$ be two sequences in $\cal S$. Recall that a (finite) initial segment of $a$ is a sequence of the form $(a_1,a_2, \ldots ,a_k)$ for some $k$.

For any $n\geq 1$, define $c_n$ to be $0$ if $I_{a'}+I_{b'} \subseteq J(n,0)$ for some initials segments $a',b'$ of $a$ and $b$ respectively, and $1$ otherwise. Then the Feanor sum $a+b$ of $a$ and $b$ is the sequence $c=(c_1,c_2, \ldots )$.

For any $n\geq 1$, define $d_n$ to be $0$ if $I_{a'} \times I_{b'} \subseteq J(n,0)$ for some initials segments $a',b'$ of $a$ and $b$ respectively, and $1$ otherwise. Then the Feanor product $a \times b$ of $a$ and $b$ is the sequence $d=(d_1,d_2, \ldots )$.

Finally, define the Feanor order on $\cal S$ as follows $a \leq b$ iff $a=b$, or $I_{a'}$ is "to the left" of $I_{b'}$ (in the sense that $x\leq y$ whenever $x\in I_{a'}, y\in I_{b'}$) for some initials segments $a',b'$ of $a$ and $b$ respectively.

Then $\cal S$ endowed with Feanor addition, multiplication and order has all the properties required of $\mathbb R$.

-
+1 for the "Feanor order" –  ItsNotObvious Feb 22 '12 at 20:24

I do not know if this is what you are looking for, or my reasoning is totally correct, as I have not studied this for a while. We have an obvious bijection between irrationals in $(0,1)$ and $\mathbb{N}^{\mathbb{N}}$ by: $$f:(a_{1},a_{2},a_{3}....)\rightarrow 1/(a_{1}+1/(a_{2}+...))$$

Thus for any finite subset of $\mathbb{N}$, this should generate a rational number, and the bijection between irrationals with the infinite subsets should be clear. Further one may argue that under this correspdondence $f(a_{1},a_{2},a_{3}....)>f(b_{1},b_{2},b_{3}....)$ if for some $i$, $\forall k<i, a_{k}=b_{k}$, while $a_{i}>b_{i}$. Thus we may define an order on the irrational numbers via such ordering of posets of $\mathbb{N}$. It is not clear to me how one may define addition, multiplication, etc via such construction.

This construction is related to the Farey tree.

-
But you use the real numbers. The question requested the addition and multiplication be defined directly from the properties of the sets. –  Asaf Karagila Feb 19 '12 at 23:00
@AsafKaragila:That is why I wrote "I do not know if this is what you are looking for". –  Kerry Feb 20 '12 at 3:43
@Asaf: The hard part is not defining addition and multiplication: the hard part is finding the correspondence. Once you have the correspondence, you just "solve" for the definitions of arithmetic operations. I don't think continued fractions answers the OP's question, because it only yields irrational numbers. :( –  Hurkyl Feb 20 '12 at 20:07
@Hurkyl: If you took a basic course in set theory you should know how to prove the existence of this bijection. It is not defined "by the properties of the sets" therefore is not an actual answer in this case. Also finite continued fraction give rationals. However one has to consider sequences and not sets of natural numbers. –  Asaf Karagila Feb 20 '12 at 21:03
@Asaf: Proving its existence isn't all that hard. Unfolding the proof to give the field structure explicitly is rather a pain, and appears not to be what the OP is interested in. –  Hurkyl Feb 21 '12 at 0:04

for any $x \in \mathcal{P}(\mathbb{N})$ consider the sequence $u_x =\left\{\sum_{k \in t}\frac{1}{2^{k}}\mid t \subset x\text{ and }t\text{ is finite}\right\}$

then consider the relation of equivalence $x R y \iff u_x=u_y$

then use $\mathbb{Z} \times \mathcal{P}(\mathbb{N}) / R$

note: $\mathbb{R}$ is the smallest field (modulo a homomorfism) that contains $\mathbb{Q}$, and where Cauchy sequences converge

-
In the second line, you should write that all $t$'s are subsets of $x$? –  Damian Sobota Feb 11 '12 at 18:55
yes, thanks, i will fix that –  Hassan Feb 11 '12 at 18:58
I see a few problems here: 1) The equivalence relation $R$ is equality: if $u_x=u_y$, then $x=y$; 2) Since you only have $\mathbb{N}$, what is $1/2^k$? And what is $\sup$? 3) It is not immediate from this definition (to me, at least) how to define addition and multiplication. –  Martin Argerami Feb 11 '12 at 20:36
think about the intevale [0,1[ as if here represented in binary. so all element are writen like this 0.011001... this may be identified with the caractesetique function of an element in P(IN): f(x) = y such that y is a function from IN to {0,1} such that y(i) = 1 if i is momber of x and 0 otherwise –  Hassan Feb 11 '12 at 21:17
Dear hassan: When you take the sup, don't you presuppose the existence of $\mathbb R$? –  Pierre-Yves Gaillard Feb 20 '12 at 20:04

I will construction $\mathbb R$ from sequences in $\mathbb{Z}$. This is not precisely a construction from $\mathcal{P}(\mathbb N)$, but it can be turned into one by observing that every sequence in $\mathbb Z$ can be constructed from $\mathcal{P}(\mathbb{N})$ by mapping

$$\left\{x_1+2^{\sigma_1}1\cdot10^{\lceil\log_{10}x_1\rceil+1},x_2+2^{\sigma_2}11\cdot10^{\lceil\log_{10}x_2\rceil+1},x_3+2^{\sigma_3}111\cdot10^{\lceil\log_{10}x_3\rceil+1},\ldots\right\}\mapsto \left((-1)^{\sigma_n}x_n\right)_{n\in\mathbb N}$$

where each $\sigma_i\in\{0,1\}$ is chosen to determine the sign. This can be done independent of the ordering of the set, as we can tell which element is $x_n+2^{\sigma_n}1\cdots1\cdot10^{\lceil\log_{10}x_1\rceil+1}$ by counting the number of $1$'s or $2$'s before the first $0$. There are of course many other ways this could be done; this is merely the first one I thought of.

I cannot take credit for the method below. It was invented by Steve Schanuel and was given to me in sketch form in a real analysis problem set. Here is the sketch of the method with details filled in by me:

Let $G$ be the collection of sequences $f:\mathbb N\to\mathbb Z$ so that there is a constant $C$ so that $$\forall m,n\in\mathbb N, |f(m)+f(n)-f(m+n)|\leq C.$$ Let $H$ be the collection of all $f:\mathbb N\to\mathbb Z$ so that there is a constant $C$ satisfying $|f(n)|\leq C$ for all $n\in\mathbb N$.

(1) Prove that if $f\in G$, then $\lim\limits_{n\to\infty} f(n)/n$ exists in $\mathbb R$.

Proof: To begin, we note that if $f,C$ are such that $|f(n)+f(m)-f(n+m)|\leq C,\forall n,m\in\mathbb N$, then $|nf(m) - f(nm)|\leq (n-1)C,\forall n,m\in\mathbb N$ by induction on $n$. The base case of this ($n=1$) is trivial, as $|f(m)-f(m)|=0\leq 0,\forall m\in\mathbb N$, while if we have that $|nf(m) - f(nm)|\leq (n-1)C$ then $$\begin{eqnarray}|(n+1)f(m) - f((n+1)m)| &=& |nf(m) + f(m) - f(nm+m)|\\ &\leq& |nf(m) - f(nm)| + |f(nm) + f(m) - f(nm+m)|\\ &\leq& (n-1)C + C = nC.\end{eqnarray}$$ Thus for $f\in G$ and $m>n\geq N\in \mathbb N$ we have that $$\begin{eqnarray}|f(m)/m - f(n)/n| &=& |nf(m) - mf(n)|/(nm)\\ &=& |nf(m) - f(nm) - (mf(n) - f(nm))|/(nm)\\ &\leq& (|nf(m)-f(nm)| + |mf(n)-f(nm)|)/(nm)\\ &\leq& ((n-1)C+(m-1)C)/(nm)\\ &\leq& C(n+m)/(nm)\leq 2C/n\leq 2C/N\end{eqnarray}$$ so given any $\epsilon>0$ we can choose $N$ such that $N > 2C/\epsilon$ thus $|f(m)/m - f(n)/n|\leq 2C/N < \epsilon$. From this we see that the sequence $f(n)/n,n\in\mathbb N$ is Cauchy, so by the completeness of $\mathbb R$ we see that $\lim\limits_{n\to\infty} f(n)/n$ exists in $\mathbb R$.

(2) If $f,g\in G$, show that $\lim\limits_{n\to\infty} f(n)/n=\lim\limits_{n\to\infty} g(n)/n$ if and only if $f-g\in H$.

Proof: Let $f,g\in G$ with the corresponding constants $A$ and $B$. Assume first that $f-g\in H$, so there exists some constant $C$ such that $|f(n)-g(n)|\leq C,\forall n\in\mathbb N$. Since $\lim\limits_{n\to\infty} f(n)/n$ and $\lim\limits_{n\to\infty} g(n)/n$ exist, we have that $\lim\limits_{n\to\infty} f(n)/n - \lim\limits_{n\to\infty} g(n)/n$ equals $\lim\limits_{n\to\infty} (f(n)-g(n))/n$, and since $|(f(n) - g(n))/n|\leq C/n$ and $\lim\limits_{n\to\infty} C/n = C\lim\limits_{n\to\infty} 1/n = 0$ we have $\lim\limits_{n\to\infty} f(n)/n - \lim\limits_{n\to\infty} g(n)/n = 0$ thus $\lim\limits_{n\to\infty} f(n)/n = \lim\limits_{n\to\infty} g(n)/n$. If on the other hand we have $\lim\limits_{n\to\infty} f(n)/n = \lim\limits_{n\to\infty} g(n)/n$ then we have $\lim\limits_{n\to\infty} (f(n)-g(n))/n = 0$. It is important to note that $n,m\in\mathbb N$ $$|f(n) - g(n) + f(m) - g(m) -(f(m+n) - g(n+m))|< A + B$$ which gives us that $$(n-1)(A+B)\geq |n(f(m)-g(m)) - f(nm)+g(nm)| \geq |n|f(m)-g(m)| - |f(nm)-g(nm)||$$ thus $$n|f(m)-g(m)| - (n-1)(A+B) \leq |f(nm)-g(nm)|\leq n|f(m)-g(m)|+(n-1)(A+B)$$ If we have some $m\in\mathbb N$ such that $|f(m)-g(m)| > A + B+1$, then we have $$n|f(m)-g(m)| - (n-1)(A+B) > n(A+B+1) - (n-1)(A+B) = n + A + B > n$$ so $|f(nm)-g(nm)|/(nm) > 1/m,\forall n\in\mathbb N$, contradicting the fact that $\lim\limits_{n\to\infty} (f(n)-g(n))/n = 0$. Hence we must have $|f(m)-g(m)| \leq A + B+1,\forall m\in\mathbb N$ thus $f-g\in H$.

(3) For $f,g\in G$, we put $f\sim g$ if $f-g\in H$. Prove that $\sim$ is an equivalence relation. The set of equivalence classes is denoted by $G/H$. The equivalence class of $f\in G$ is denoted by $[f]$. Show that there is a function $j:G/H\to\mathbb R$ so that $j([f])=\lim\limits_{n\to\infty} f(n)/n$ for all $f\in G$. Show that $j$ is one-to-one.

Proof: Let $f,g,h\in G$ be such that $f\sim g$ and $g\sim h$, thus $f-g,g-h\in H$. Since $|f(n)-f(n)|\leq 0,\forall n\in \mathbb N$ and $|g(n)-f(n)| = |f(n)-g(n)|$ we see that $f-f,g-f\in H$ so $f\sim f,g\sim f$ giving us the reflexive and commutative properties, while the fact that $|f(n) - h(n)|\leq |f(n)-g(n)|+|g(n)-h(n)|$, both of which are bounded, gives us $f-h\in H$ so $f\sim h$ thus $\sim$ is transitive as well. Hence $\sim$ is an equivalence relation. We can define a function $j:G/H\rightarrow \mathbb R$ by setting $j([f]) = \lim\limits_{n\to\infty} f(n)/n$, which is well-defined because $[f] = [g]\implies f - g\in H$ thus $\lim\limits_{n\to\infty} f(n)/n = \lim\limits_{n\to\infty} g(n)/n$. We can also see that $j$ is one-to-one, as if $j([f])=j([g])$ then $\lim\limits_{n\to\infty} f(n)/n = \lim\limits_{n\to\infty} g(n)/n$ thus $f-g\in H$ so $[f] = [g]$.

(4) Prove that $j:G/H\to\mathbb R$ is a bijection.

Proof: We already have that $j$ is one-to-one, so we need only prove that $j$ is surjective. Let $r\in \mathbb R$ be an arbitrary real number and define $f(n)$ as the least integer greater than or equal to $rn$. For $m,n\in\mathbb N$ we have $$|f(n)+f(m)-f(n+m)|\leq 3 + |nr + mr - (n+m)r| = 3$$ so $f\in G$. We also have that $|f(n)/n - r| = |f(n) - rn|/n < 1/n$ so for any $k\in\mathbb N$, $n\geq k\implies |f(n)/n - r| < 1/k$, hence $\lim\limits_{n\to\infty} f(n)/n = r$. This gives us $j([f]) = r$, completing the proof.

Thus we have constructed $\mathbb R$.

-