1. ## Cardinality Problem

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

My attempt at the question is as follows:

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

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

2. ## 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}.

Hope this helps

Sam

3. ## 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

4. ## Re: Cardinality Problem

Originally Posted by DrSteve
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 $\displaystyle N^X \subset P(N \times X) \sim P(X) \sim \{0,1\}^X$