1. ## 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|$.

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