Denumerable Partition

**armeros** · May 19th 2009, 05:42 AM

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

**Plato** · May 19th 2009, 08:16 AM

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?

**armeros** · May 19th 2009, 09:08 AM

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?

**Plato** · May 19th 2009, 09:22 AM

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

**armeros** · May 19th 2009, 09:37 AM

Thank you very much.

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

Math Help - Denumerable Partition

LinkBack

Thread Tools

Display

Denumerable Partition

Similar Math Help Forum Discussions

Prove that a set is denumerable iff...

Prove if two sets are denumerable then their union is denumerable

Denumerable Set

Denumerable sets...

denumerable sets

Search Tags