Results 1 to 6 of 6

Thread: Cardinality

  1. #1
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22

    Cardinality

    Hello friends, I have an idea of how to do this, but a nudge in the right direction wouldn't hurt!


    Let $\displaystyle \left\{X_i\right\},\text{ }i\in\mathcal{I}$ be a class of countably infinite sets where $\displaystyle \mathcal{I}$ is infinite (countably or uncountably). Prove that $\displaystyle \text{card }\bigcup_{i\in\mathcal{I}}X_i\le\text{card }\mathcal{I}$

    ------------------------------------------------------------------------

    If $\displaystyle \mathcal{I}$ is countably infinite this follows easily, otherwise I feel as though I can use Zorn's lemma.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,736
    Thanks
    2811
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    Let $\displaystyle \left\{X_i\right\},\text{ }i\in\mathcal{I}$ be a class of countably infinite sets where $\displaystyle \mathcal{I}$ is infinite (countably or uncountably). Prove that $\displaystyle \text{card }\bigcup_{i\in\mathcal{I}}X_i\le\text{card }\mathcal{I}$
    I freely admit that I am not at all sure if I understand your question.
    But suppose that $\displaystyle \mathcal{I}=\mathbb{Z}^+$ the let $\displaystyle X_i$ be the set of infinite bit-strings in which the $\displaystyle i^{th}$ entry is not 0.

    Is this a counter-example?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by Plato View Post
    I freely admit that I am not at all sure if I understand your question.
    But suppose that $\displaystyle \mathcal{I}=\mathbb{Z}^+$ the let $\displaystyle X_i$ be the set of infinite bit-strings in which the $\displaystyle i^{th}$ entry is not 0.

    Is this a counter-example?
    Thanks Plato. I'm not sure, but it looks as though your $\displaystyle X_i$ is uncountable though.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,736
    Thanks
    2811
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    Thanks Plato. I'm not sure, but it looks as though your $\displaystyle X_i$ is uncountable though.
    Well, I did say that I might not fully understand the question.
    Letís change the example.
    $\displaystyle X_i$ be the set of infinite bit-strings in which only the first $\displaystyle i^{th}$ terms are possibly non-zero.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    for every $\displaystyle i \in I$ put $\displaystyle Y_i=X_i \times \{i \}.$ see that $\displaystyle \text{card} \ \bigcup_{i \in I}X_i \leq \text{card} \ \bigcup_{i \in I} Y_i.$ clearly $\displaystyle \text{card} \ X_i = \text{card} \ Y_i$ and $\displaystyle Y_i \cap Y_j = \emptyset,$ for all $\displaystyle i \neq j.$ now let $\displaystyle J=I \times \mathbb{N}.$ then $\displaystyle \text{card} \ I = \text{card} \ J.$ we also have an

    one-to-one map $\displaystyle f_i : Y_i \longrightarrow \mathbb{N},$ for every $\displaystyle i \in I.$ finally define $\displaystyle g : \bigcup_{i \in I} Y_i \longrightarrow J$ by $\displaystyle g(y)=(i,f_i(y)),$ for all $\displaystyle i \in I, \ y \in Y_i.$ see that $\displaystyle g$ is one-to-one and thus $\displaystyle \text{card} \ \bigcup_{i \in I} Y_i \leq \text{card} \ J. \ \Box$
    Last edited by NonCommAlg; Jan 3rd 2010 at 08:40 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by NonCommAlg View Post
    for every $\displaystyle i \in I$ put $\displaystyle Y_i=X_i \times \{i \}.$ see that $\displaystyle \text{card} \ \bigcup_{i \in I}X_i \leq \text{card} \ \bigcup_{i \in I} Y_i.$ clearly $\displaystyle \text{card} \ X_i = \text{card} \ Y_i$ and $\displaystyle Y_i \cap Y_j = \emptyset,$ for all $\displaystyle i \neq j.$ now let $\displaystyle J=I \times \mathbb{N}.$ then $\displaystyle \text{card} \ I = \text{card} \ J.$ we also have an

    one-to-one map $\displaystyle f_i : Y_i \longrightarrow \mathbb{N},$ for every $\displaystyle i \in I.$ finally define $\displaystyle g : \bigcup_{i \in I} Y_i \longrightarrow J$ by $\displaystyle g(y)=(i,f_i(y)),$ for all $\displaystyle i \in I, \ y \in Y_i.$ see that $\displaystyle g$ is one-to-one and thus $\displaystyle \text{card} \ \bigcup_{i \in I} Y_i \leq \text{card} \ J. \ \Box$
    That looks great, except I don't see why it follows so easily that $\displaystyle \text{card }\mathcal{I}\times\mathbb{N}=\text{card }\mathcal{I}$? I think what we could do to prove it is to take $\displaystyle \mathfrak{F}$ to be a sufficiently large family (maybe $\displaystyle \mathfrak{F}=\left\{\mathcal{I}\times\{1,\cdots,n\ },n\in\mathbb{N}\right\}$)and transform it into a poset by letting $\displaystyle \left(\mathfrak{F},\le\right)$ be a poset with $\displaystyle A\le B\Leftrightarrow A\subseteq B\text{ and }\text{card }A\le\text{card }B$. Then if we can prove that $\displaystyle \text{card }\mathcal{I}\times\left\{1,\cdots,n\right\}=\text{ card }\mathcal{I}$ for all $\displaystyle n\in\mathbb{N}$ I think we can apply Zorn's lemma to show that $\displaystyle \mathfrak{F}$ has a maximal element $\displaystyle \mathfrak{M}$ and this $\displaystyle \mathfrak{M}$ is forced to be $\displaystyle \mathfrak{M}=\mathcal{I}\times\mathbb{N}$. This may very wrong, I just can't think straight right now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 07:08 AM
  2. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: Mar 18th 2010, 02:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 31st 2009, 03:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Feb 11th 2009, 05:36 PM
  5. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Feb 8th 2009, 02:23 PM

Search Tags


/mathhelpforum @mathhelpforum