elementary-set-theory
Prove that the set of Real numbers R can be partitioned into a denumerable collection of uncountable sets
My thoughts on the problem were to show the break down of the set of real numbers into subsets such as rational, irrational, and integers.
Im not sure if im over complicating this. The wording is confusing to me because i have never done something like this in class.
There are a few possibilities, but here is the one approach. Even the starting point—the set of natural numbers $\mathbb{N}$—can be defined in several ways, but the standard definition takes $\mathbb{N}$ to be the set of finite von Neumann ordinals. Let us assume that we do have a set $\mathbb{N}$, a constant $0$, a unary operation $s$, and binary operations $+$ and $\cdot$ satisfying the axioms of second-order Peano arithmetic.
First, we need to construct the set of integers $\mathbb{Z}$. This we can do canonically as follows: we define $\mathbb{Z}$ to be the quotient of $\mathbb{N} \times \mathbb{N}$ by the equivalence relation $$\langle a, b \rangle \sim \langle c, d \rangle \text{ if and only if } a + d = b + c$$ The intended interpretation is that the equivalence class of $\langle a, b \rangle$ represents the integer $a - b$. Arithmetic operations can be defined on $\mathbb{Z}$ in the obvious fashion: $$\langle a, b \rangle + \langle c, d \rangle = \langle a + c, b + d \rangle$$ $$\langle a, b \rangle \cdot \langle c, d \rangle = \langle a c + b d, a d + b c \rangle$$ (Check that these respect the equivalence relation.) Again, this is not the only way to construct $\mathbb{Z}$; we can give a second-order axiomatisation of the integers which is categorical (i.e. any two models are isomorphic). For example, we may replace the set $\mathbb{Z}$ by $\mathbb{N}$, since the two sets are in bijection; the only thing we have to be careful about is to distinguish between the arithmetic operations for $\mathbb{Z}$ and for $\mathbb{N}$. (In other words, $\mathbb{Z}$ is more than just the set of its elements; it is also equipped with operations making it into a ring.)
Next, we need to construct the set of rational numbers $\mathbb{Q}$. This we may do using equivalence relations as well: we can define $\mathbb{Q}$ to be the quotient of $\mathbb{Z} \times (\mathbb{Z} \setminus \{ 0 \})$ by the equivalence relation $$\langle a, b \rangle \sim \langle c, d \rangle \text{ if and only if } a d = b c$$ The intended interpretation is that the equivalence class of $\langle a, b \rangle$ represents the fraction $a / b$. Arithmetic operations are defined by $$\langle a, b \rangle + \langle c, d \rangle = \langle a d + b c, b d \rangle$$ $$\langle a, b \rangle \cdot \langle c, d \rangle = \langle a c, b d \rangle$$ And as before, we can give an axiomatisation of the rational numbers which is categorical.
Now we can construct the set of real numbers $\mathbb{R}$. I describe the construction of Dedekind cuts, which is probably the simplest. A Dedekind cut is a pair of sets of rational numbers $\langle L, R \rangle$, satisfying the following axioms:
The intended interpretation is that $\langle L, R \rangle$ is the real number $z$ such that $L = \{ x \in \mathbb{Q} : x < z \}$ and $R = \{ y \in \mathbb{Q} : z < y \}$. The set of real numbers is defined to be the set of all Dedekind cuts. (No quotients by equivalence relations!) Arithmetic operations are defined as follows:
John Conway gives an alternative approach generalising the Dedekind cuts described above in his book On Numbers and Games. This eventually yields Conway's surreal numbers.
The idea for the first one is the following: Given a partition $\Delta$ of $X$, that partition induces an equivalence relation on $X$. Namely, we say $x$ and $y$ stand in relation if they belong to the same set of the partition. You can check that this is indeed an equivalence relation. Because
$(1)$ $x$ is always in the same set as $x$.
$(2)$ If $x$ is in the same set as $y$, then $y$ is in the same set as $x$.
$(3)$ If $x$ is in the same set as $y$, and $y$ is in the asme set as $z$, then $x$ is in the asme set as $z$.
Given a relation $\sim $ on a set $X$, we say it is an equivalence relation if it has the following three properties:
$(1)$ Reflexivity $x\sim x$. That is, every element stands in relation with itself.
$(2)$ Symmetry If $x\sim y$, then $y\sim x$. That is, if $x$ stands in relation with $y$, then $y$ stands in relation to $x$.
$(3)$ Transitivity If $x\sim y$ and $y\sim z$, then $x\sim z$. That is if $x$ stands in relation with $y$ and $y$ stands in relation with $z$, then $x$ stands in relation with $z$.
You can check that the relation divisibility is transitive and reflexive. You an check the relation of inclusio is transitive and reflexive, too, but not symmetryc. You can check that congruence $\mod{}$ a number $n$ is a equivalence relation, and so is usual equality of numbers.
Given a relation $\sim$ on a set $X$, and an element of $X$, we define the equivalence class $[[x]]$ of $x$ as all elements in $X$ that stand in relation to $x$. That is
$$[[x]]=\{a\in X:a\sim x\}$$
You can check equivalence classes are:
$(1)$ Non-empty: For each $x$, $x\in [[x]]$.
$(2)$ Either disjoint or equal: If there is one element $p$ in $[[x]]\cap[[y]]$ then we have that $p\sim y$ and $p\sim x$. Reflexivity means $y\sim p$ and $p\sim x$ so transitivity means $y\sim x$. Reflexivity once more gives $y\sim x$. Thus whenever $a\in [[x]]$, $a\sim x$ and $x\sim y$, whence $a\sim y$. Similarily whenever $b\in [[y]]$, $b\sim y$ and $y\sim x$, whence $b\sim x$. This means $[[x]]=[[y]]$.
This means that they are a partition of $X$. So any partition induces an equivalence relation, and conversely.
As to the first thing you say: if by unique you mean $x\sim y\iff x=y$, then what you have is the equivalence relation of equality which simply induces the partition of $X$ into singletons of its elements.
On you last question you talk about an equivalence on the partitioned subsets. I presume you mean an equivalence relation , but what do you mean by "on the partitioned subsets"?
Regarding the part on the "partitioning the real numbers into subsets of equal number of decimal places." Recall there are some rational numbers with nonterminating decimal expansion, and any irrational number will have a nonterminating decimal expansion. Thus, maybe you will have to work with rationals whose decimal expansion has the same amount of decimal numbers, and say talk about "number of decimal places" with nonterminating rationals acording to the period of the expansion. For example, $3^{-1}=0.\hat 3$. Else, if the number is irrational, it goesto $\mathbb I$, the set of irrational numbers.
Best Answer
How about the union of the intervals $[n, n+1); n $
in $\mathbb Z^+ $ ? and $(n-1,n]$ for $n$ in the negative integers less than or equal to $-1$, and $(-1,0)$.
Basically, the partition is : { $ \cup (n-1,n ]; n \leq -1 \cup (-1,0) \cup [0,1) \cup [1,2) \cup....\cup [n, n+1) \cup.....$}