Thread: Denumerable Partition

Suppose $\displaystyle A$ is denumerable. Prove that there is a partiion $\displaystyle P$ of $\displaystyle A$ such that $\displaystyle P$ is denumerable and for every $\displaystyle X \in P, X$ is denumerable.

...

Note that for any partition $\displaystyle P$, it is not necessarily denumerable, and it is not necessarily that $\displaystyle X$ must be denumerable for all $\displaystyle X \in P$. For example, $\displaystyle A = \mathbb{Z}$ and $\displaystyle P = \{\mathbb{Z}^+, \{0\}, \mathbb{Z}^-\}$

I think I must construct some $\displaystyle P.$ Note that $\displaystyle A, P,$ and $\displaystyle X$ must be written as

$\displaystyle A = \{a_{11}, a_{12}, a_{13}, ..., a_{21}, a_{22}, a_{23}, ...,a_{31}, a_{32}, a_{33}...\}$ (A can be written like this since A is denumerable.)

$\displaystyle P = \{X_1, X_2, X_3,...\}$

$\displaystyle X_i = \{a_{i1}, a_{i2}, a_{i3},...\}.$

I cannot find any way to construct such $\displaystyle P$, other than what they should be by the characterization above.

Must I resort to proof by contradiction?

Thank you very much.

PS. Definition of partition, $\displaystyle 1. \bigcup P = A, 2. \forall X \in P, \forall Y \in P, X \cap Y = \emptyset, 3. \forall X \in P, X$ not equal $\displaystyle \emptyset$.

Originally Posted by armeros

Suppose $\displaystyle A$ is denumerable. Prove that there is a partiion $\displaystyle P$ of $\displaystyle A$ such that
$\displaystyle P$ is denumerable and for every $\displaystyle X \in P, X$ is denumerable.

This is an oddly worded problem. For one thing any infinite subset of a denumerable set is denumerable.
As for the construction, any equivalence relation on a set defines a partition of the set.
So if you can define an equivalence relation on $\displaystyle \mathbb{Z^+}$ with a denumerable collection of infinite equivalence classes that will also do for your set.

Here is a suggestion.
Two positive integers are related if they are powers of the same prime or neither is a power of a prime.

Examples: $\displaystyle 8\mathcal{R}32,~ 27\mathcal{R}81,~\&~6\mathcal{R}10 $.

Can you prove that $\displaystyle \mathcal{R}$ is an equivalence relation?

To show $\displaystyle \mathcal{R}$ is reflexive, choose $\displaystyle x$ and$\displaystyle y \in \mathbb{Z}^+ $such that $\displaystyle x \mathcal{R} y$. Consider the case that they are powers of the same prime. Then, $\displaystyle x = p^n$. Since $\displaystyle p^n \mathcal{R} p^n$, this means $\displaystyle \mathcal{R}$ is reflexive. The other case is not hard to show.

$\displaystyle \mathcal{R}$ is transitive, since $\displaystyle x \mathcal{R} y$ and $\displaystyle y \mathcal{R} z $means their bases must be the same, or if it is the latter case, thier bases cannot be prime.

$\displaystyle \mathcal{R}$ is symmetric, since $\displaystyle x \mathcal{R} y$ means $\displaystyle y \mathcal{R} x.$

.................................................

I could let $\displaystyle \mathcal{R} = \bigcup_{X \in P} (X \times X)$ defines the partition $\displaystyle P$, and for each $\displaystyle X=[x]_\mathcal{R}$ is an equivalence class. And let $\displaystyle P = A/\mathcal{R}$.

any infinite subset of a denumerable set is denumerable.

There was an exercise where I showed that $\displaystyle X \subseteq A$ and $\displaystyle A$ is countable implies $\displaystyle X$ is countable.

Hence, if $\displaystyle X$ is infitine, $\displaystyle X$ is denumerable.

define an equivalence relation on with a denumerable collection of infinite equivalence classes that will also do for your set.

I don't get it. We are talking about any set $\displaystyle A$ and how do I relate an equivalence relation on $\displaystyle \mathbb{Z}^+ $to the partition P?

Originally Posted by armeros

I don't get it. We are talking about any set $\displaystyle A$ and how do I relate an equivalence relation on $\displaystyle \mathbb{Z}^+ $to the partition P?

Because $\displaystyle \mathcal{A}$ is denumerable, $\displaystyle \mathcal{A}=\left\{ {a_1 ,a_2 ,a_3 ,a_4 , \cdots } \right\}$.
In a word the subscripts turn $\displaystyle \mathcal{A}$ into $\displaystyle \mathcal{Z}^+$.

Use the cells I suggested.
The cell containing $\displaystyle a_1$ contains all terms having a subscript that is not a power of a prime.
The cell containing $\displaystyle a_2$ contains all terms having a subscript that is a power of 2.
The cell containing $\displaystyle a_{11}$ contains all terms having a subscript that is a power of 11.
etc

Thank you very much.

(How could I be able to think of such cells?)