1. ## Denumerable Partition

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

...

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

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

$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.)

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

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

I cannot find any way to construct such $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, $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 $\emptyset$.

2. Originally Posted by armeros
Suppose $A$ is denumerable. Prove that there is a partiion $P$ of $A$ such that
$P$ is denumerable and for every $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 $\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: $8\mathcal{R}32,~ 27\mathcal{R}81,~\&~6\mathcal{R}10$.

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

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

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

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

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

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

any infinite subset of a denumerable set is denumerable.
There was an exercise where I showed that $X \subseteq A$ and $A$ is countable implies $X$ is countable.

Hence, if $X$ is infitine, $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 $A$ and how do I relate an equivalence relation on $\mathbb{Z}^+$to the partition P?

4. Originally Posted by armeros
I don't get it. We are talking about any set $A$ and how do I relate an equivalence relation on $\mathbb{Z}^+$to the partition P?
Because $\mathcal{A}$ is denumerable, $\mathcal{A}=\left\{ {a_1 ,a_2 ,a_3 ,a_4 , \cdots } \right\}$.
In a word the subscripts turn $\mathcal{A}$ into $\mathcal{Z}^+$.

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

5. Thank you very much.

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