Results 1 to 4 of 4

Math Help - Cardinality Problem

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    62

    Cardinality Problem

    Show that if |X \times \mathbb{N}| = |X|, then |\{0,1\}^X| = |\mathbb{N}^X|.

    My attempt at the question is as follows:

    Since \{0,1\}^X \subseteq \mathbb{N}^X, |\{0,1\}^X| \leq |\mathbb{N}^X|.
    Since |X \times \mathbb{N}| = |X|, there exist 2 injective functions f: X \times \mathbb{N} \longrightarrow X and g: X \longrightarrow X \times \mathbb{N}.

    The problem here is what I should do to prove that |\{0,1\}^X| \geq |\mathbb{N}^X|.

    Thank you in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2011
    Posts
    1

    Re: Cardinality Problem

    Hey,

    We can think of functions from Y to {0, 1} as determining subsets of Y. For instance, a function f from Y to {0, 1} determines the set {x in Y: f(x) = 1} -- it basically `says' of every member of Y whether or not it's in this set, `yes' if f(x) = 1, and `no' if f(x) = 0. Conversely, for any subset A of Y, we can define such a function for A by f(x) = 1 if x is in A, and f(x) = 0 if not. We can call such a function a characteristic function for A.

    Now, any function g from X to N is a subset of X x N -- it consists solely of pairs whose first element is in X and whose second element is in N. So consider its characteristic function f(<x, n>) = 1 if <x, n> is in g, and f(<x, n>) = 0 if not. This will be a function from X x N to {0, 1}. Mapping each function from X to N to its characteristic function in this way, we get an injective mapping from the functions from X to N, to some functions from X x N to {0, 1}.

    Then your result follows easily.

    Hope this helps

    Sam
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2

    Re: Cardinality Problem

    My latex isn't working for some reason. Here's a really quick argument. Hope you can read this:

    N^X \subset P(N x X) ~ P(X) ~ {0,1}^X
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Cardinality Problem

    Quote Originally Posted by DrSteve View Post
    My latex isn't working for some reason. Here's a really quick argument. Hope you can read this:

    N^X \subset P(N x X) ~ P(X) ~ \{0,1\}^X
    Use the [TEX]...[/TEX] tags.

    [TEX]N^X \subset P(N \times X) \sim P(X) \sim \{0,1\}^X[/TEX]

    gives N^X \subset  P(N \times X) \sim P(X) \sim \{0,1\}^X
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality Problem (2)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 9th 2011, 08:11 AM
  2. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 7th 2010, 10:01 AM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 4th 2010, 02:45 AM
  4. cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 9th 2008, 03:37 AM
  5. Cardinality Problem
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: February 27th 2007, 03:04 PM

/mathhelpforum @mathhelpforum