Results 1 to 5 of 5

Thread: Denumerable Partition

  1. #1
    Junior Member
    Joined
    Apr 2009
    Posts
    55
    Thanks
    1

    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$.
    Last edited by armeros; May 19th 2009 at 05:00 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Quote Originally Posted by armeros View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2009
    Posts
    55
    Thanks
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Quote Originally Posted by armeros View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2009
    Posts
    55
    Thanks
    1
    Thank you very much.

    (How could I be able to think of such cells?)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove that a set is denumerable iff...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 2nd 2010, 11:26 AM
  2. Replies: 1
    Last Post: Oct 2nd 2010, 11:21 AM
  3. Denumerable Set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2010, 11:54 AM
  4. Denumerable sets...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 5th 2009, 10:26 PM
  5. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 15
    Last Post: Dec 14th 2008, 10:39 PM

Search Tags


/mathhelpforum @mathhelpforum