# Math Help - Cardinality

1. ## Cardinality

Let A be a non-empty set. Consider F = {f : A → {0, 1}}, the set of all functions on A with values in {0, 1}. Consider the function g : P (A) → F , B → X_B , where X_B is the characteristic function of the subset B ⊆ A: X_B(a) = 1, if a∈B, and X_B(a) = 0, if a∉B. Show that g is a bijection. As a consequence show that the number of subsets of a set with n elements is 2^n . This may justify the notation {0, 1}^A used for F.

Where P represents the power set of A.

I am very lost. We just started the chapter on cardinality and I am already struggling . I don't really know how to begin the question, so some direction would be nice. I tried to work out the one-to-one portion of the proof, but I am not sure if I am using the characteristic function correctly. Will I need to use it to show 1-1 and onto?

Here is my stab at 1-1:
Here is an attempt at a 1-1 proof:
So, I choose elements X_B1=X_B2∈P(A) where X_B1 and X_B2 are functions with same domain A and try to show g(X_B1)=g(X_B2). So, then ∃a∈A such that X_B1(a)=X_B2(a). I can then assume X_B1(a)=X_B2(a)=1. So, we know a∈B for both functions. So, g(X_B1)=g(X_B2). Therefore, g is one-to-one.

Is that how I use the characteristic equations? I am having a harder time with the onto proof.

--Dan

2. Here is some material I wrote several years ago.
I hope it helps.

3. Thanks for that. I followed most of it.

I think I have the first part of the proof down (that the function g is bijective). Although, I am still not sure how to do the second part of the proof:

"As a consequence show that the number of subsets of a set with n elements is 2^n . This may justify the notation {0, 1}^A used for F."

The way it's written it sounds like the afore proof should have guided me to some kind of answer, but I'm not seeing it.

Thanks for the help

4. Originally Posted by Plato
Here is some material I wrote several years ago.
I hope it helps.
Nice work!

Anyway, I think $2^M$ is not a proper notation for a set since 2 is not a set.

5. Originally Posted by HiLine
Nice work!
Anyway, I think $\color{red}2^M$ is not a proper notation for a set since 2 is not a set.
But 2 is a set.
$\begin{gathered}
0 = \emptyset \hfill \\
1 = \left\{ \emptyset \right\} \hfill \\
2 = \left\{ {0,1} \right\} = \left\{ {\emptyset ,\left\{ \emptyset \right\}} \right\} \hfill \\
\vdots \hfill \\
\end{gathered}$

6. Originally Posted by Plato
But 2 is a set.
$\begin{gathered}
0 = \emptyset \hfill \\
1 = \left\{ \emptyset \right\} \hfill \\
2 = \left\{ {0,1} \right\} = \left\{ {\emptyset ,\left\{ \emptyset \right\}} \right\} \hfill \\
\vdots \hfill \\
\end{gathered}$
Is it? I thought $\begin{gathered}\left\{ {0,1} \right\}\end{gathered}$ is a set and 2 is a cardinal number. Is that what you mean in the argument?

Or it could be a new notation to me. Sorry if that is the case.

7. Originally Posted by HiLine
Is it? I thought $\begin{gathered}\left\{ {0,1} \right\}\end{gathered}$ is a set and 2 is a cardinal number. Is that what you mean in the argument? Or it could be a new notation to me. Sorry if that is the case.
From those remarks, it appears that you may not have studied an axiomatic construction of the natural numbers.
Herbert Enderton’s book ELEMENTS OF SET THEORY does a good job of that construction.

8. That is the case then. I'm sorry, Plato. My bad.

9. Originally Posted by Plato
Here is some material I wrote several years ago.
I hope it helps.
Infectivity ? Nice mathematical concept
Blood Analysis showed we're infected by mathematics