Results 1 to 5 of 5

Math Help - Denumerable Partition

  1. #1
    Junior Member
    Joined
    Apr 2009
    Posts
    54
    Thanks
    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.
    Last edited by armeros; May 19th 2009 at 06:00 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

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

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

  4. #4
    MHF Contributor

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

  5. #5
    Junior Member
    Joined
    Apr 2009
    Posts
    54
    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: October 2nd 2010, 12:26 PM
  2. Replies: 1
    Last Post: October 2nd 2010, 12:21 PM
  3. Denumerable Set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2010, 12:54 PM
  4. Denumerable sets...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 5th 2009, 11:26 PM
  5. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 15
    Last Post: December 14th 2008, 11:39 PM

Search Tags


/mathhelpforum @mathhelpforum