# Thread: set of functions

1. ## set of functions

Given two sets $\displaystyle A$ and $\displaystyle B$, let $\displaystyle A^{B}$ be the set of all functions $\displaystyle f: B \to A$. Prove that for any set $\displaystyle A$, $\displaystyle \text{card}(\bar{2}^{A}) = \text{card}(\mathcal{P}(A))$.

Here, $\displaystyle \bar{2} = \{1,2\}$. In other words, we want to prove that $\displaystyle \text{card}(\bar{2}^{A}) = 2^{n}$?

So $\displaystyle \bar{2}^{A}$ is the set of all functions $\displaystyle f: A \to \bar{2}$. It does not say anything about the sets being countable/uncountable, or finite/infinite. Since any element $\displaystyle x \in A$ maps to either of two values, then using the characteristic function, the total number of functions is $\displaystyle 2^{n}$ if $\displaystyle A$ is countably infinite or finite. But if $\displaystyle A$ is uncountable/infinite, then $\displaystyle \text{card}(\bar{2}^{A}) = 2^{\aleph_{1}}$?

2. Allow me to point out that it is usual to define $\displaystyle \overline 2 = \left\{ {0,1} \right\}$.
This proof also uses the idea of characteristic function: $\displaystyle B \in P(A),\;\chi _B (x) = \left\{ {\begin{array}{lr} {0,} & {x \notin B} \\ {1,} & {x \in B} \\ \end{array}} \right.$
Note that $\displaystyle \chi _B \in \overline 2 ^A$.
Now define $\displaystyle \Psi :P(A) \mapsto \overline 2 ^A ,\;\left[ {\forall B \in P(A)\,,\,\Psi (B) = \chi _B } \right]$.

Now it up to you to show that $\displaystyle \Psi$ is a bijection.

3. Originally Posted by particlejohn
Here, $\displaystyle \bar{2} = \{1,2\}$. In other words, we want to prove that $\displaystyle \text{card}(\bar{2}^{A}) = 2^{n}$?

So $\displaystyle \bar{2}^{A}$ is the set of all functions $\displaystyle f: A \to \bar{2}$. It does not say anything about the sets being countable/uncountable, or finite/infinite.
Well, if you're going to prove $\displaystyle 2^n$, then shouldn't A be a finite set with n elements?

It's a matter of combinatorics. Any element in A can be mapped to 0 or 1, so there are exactly two choices for it. Since there are n elements in A, there are $\displaystyle 2^n$ ways of mapping A to {0,1}; hence there are $\displaystyle 2^n$ functions from A to {0,1}.

4. That was the ambiguity that I pointed out.

5. Originally Posted by Catherine Morland
Well, if you're going to prove $\displaystyle 2^n$, then shouldn't A be a finite set with n elements?
Originally Posted by particlejohn
That was the ambiguity that I pointed out.
There is no ambiguity.
The outline of a proof that I gave you shows that for any set A we have a bijection $\displaystyle P(A) \leftrightarrow \overline 2 ^A$.
This works for any set, the cardinality does not matter.

6. Originally Posted by Plato
Allow me to point out that it is usual to define $\displaystyle \overline 2 = \left\{ {0,1} \right\}$.
This proof also uses the idea of characteristic function: $\displaystyle B \in P(A),\;\chi _B (x) = \left\{ {\begin{array}{lr} {0,} & {x \notin B} \\ {1,} & {x \in B} \\ \end{array}} \right.$
Note that $\displaystyle \chi _B \in \overline 2 ^A$.
Now define $\displaystyle \Psi :P(A) \mapsto \overline 2 ^A ,\;\left[ {\forall B \in P(A)\,,\,\Psi (B) = \chi _B } \right]$.

Now it up to you to show that $\displaystyle \Psi$ is a bijection.
We want to show that $\displaystyle \Psi(B) = \chi_B$ is a bijection. Suppose that $\displaystyle C \in \mathcal{P}(A)$. Then $\displaystyle \Psi(B) = \Psi(C) = \chi_{B}$ implies that $\displaystyle B = C$ for injectivity. For all $\displaystyle y \in \bar{2}^{A}$, $\displaystyle \Psi(B) = y$ for surjectivity.

7. Originally Posted by particlejohn
We want to show that $\displaystyle \Psi(B) = \chi_B$ is a bijection. Suppose that $\displaystyle C \in \mathcal{P}(A)$. Then $\displaystyle \Psi(B) = \Psi(C) = \chi_{B}$ implies that $\displaystyle B = C$ for injectivity. For all $\displaystyle y \in \bar{2}^{A}$, $\displaystyle \Psi(B) = y$ for surjectivity.
If $\displaystyle y \in \bar{2}^{A}$, let $\displaystyle D = \left\{ {a \in A:y(a) = 1} \right\}$ then $\displaystyle {\Psi (D) = \chi _D = y}$.
Do you see why?

8. Originally Posted by Plato
If $\displaystyle y \in \bar{2}^{A}$, let $\displaystyle D = \left\{ {a \in A:y(a) = 1} \right\}$ then $\displaystyle {\Psi (D) = \chi _D = y}$.
Do you see why?
$\displaystyle D$ is the set of all elements that belong to $\displaystyle A$ (e.g. value is $\displaystyle 1$). Hence $\displaystyle \Psi(D) = \chi_{D} = y$.

9. Originally Posted by particlejohn
Here, $\displaystyle \bar{2} = \{1,2\}$.
This is a little bit off topic but you might it interesting we define $\displaystyle 2$ to be $\displaystyle \{ 0,1\}$ where $\displaystyle 0=\emptyset$ and $\displaystyle 1=\{0\}$. This is what Plato said. Thus, there is no need to write $\displaystyle \bar 2 = \{ 0,1\}$ because in fact $\displaystyle 2=\{0,1\}$.

This might look strange but this is how we define natural numbers. We define $\displaystyle 0 = \emptyset$. We define $\displaystyle 1=\{ 0\} = \{ \emptyset \}$. We define $\displaystyle 2=\{0,1\} = \{ \emptyset, \{ \emptyset\} \}$. We define $\displaystyle 3=\{0,1,2\}=\{ \emptyset, \{ \emptyset\}, \{\emptyset, \{\emptyset\} \} \}$. We would like to say natural numbers are repetitions of this form. However, this is not a formal enough statement. So this is what we do. Let $\displaystyle x$ be a set and define $\displaystyle x+1 = x\cup \{ x\}$. Thus is follows $\displaystyle 0 = \emptyset, 1 = 0+1,2=1+1,3=2+1$. We cannot say "and so on" because that is not a formal term. To do this we define an inductive set to be a set $\displaystyle I$ such that $\displaystyle 0\in I$ and if $\displaystyle x\in I$ then $\displaystyle x+1\in I$. One of the axioms we place into Set Theory is called Axiom of Infinity which says "an inductive set exists", the reason we do this is because using the simpler axioms we cannot construct inductive sets and we would like to make set theory more interesting by allowing infinite sets. Finally, since there is an inductive set $\displaystyle I$ define $\displaystyle \mathbb{N} = \{ x\in I | x \mbox{ is in every inductive set } \}$. This set $\displaystyle \mathbb{N}$ are called the natural numbers and this is a purely formal construction of the naturals.

10. Originally Posted by ThePerfectHacker
This is a little bit off topic but you might it interesting we define $\displaystyle 2$ to be $\displaystyle \{ 0,1\}$ where $\displaystyle 0=\emptyset$ and $\displaystyle 1=\{0\}$. This is what Plato said. Thus, there is no need to write $\displaystyle \bar 2 = \{ 0,1\}$ because in fact $\displaystyle 2=\{0,1\}$.

This might look strange but this is how we define natural numbers. We define $\displaystyle 0 = \emptyset$. We define $\displaystyle 1=\{ 0\} = \{ \emptyset \}$. We define $\displaystyle 2=\{0,1\} = \{ \emptyset, \{ \emptyset\} \}$. We define $\displaystyle 3=\{0,1,2\}=\{ \emptyset, \{ \emptyset\}, \{\emptyset, \{\emptyset\} \} \}$. We would like to say natural numbers are repetitions of this form. However, this is not a formal enough statement. So this is what we do. Let $\displaystyle x$ be a set and define $\displaystyle x+1 = x\cup \{ x\}$. Thus is follows $\displaystyle 0 = \emptyset, 1 = 0+1,2=1+1,3=2+1$. We cannot say "and so on" because that is not a formal term. To do this we define an inductive set to be a set $\displaystyle I$ such that $\displaystyle 0\in I$ and if $\displaystyle x\in I$ then $\displaystyle x+1\in I$. One of the axioms we place into Set Theory is called Axiom of Infinity which says "an inductive set exists", the reason we do this is because using the simpler axioms we cannot construct inductive sets and we would like to make set theory more interesting by allowing infinite sets. Finally, since there is an inductive set $\displaystyle I$ define $\displaystyle \mathbb{N} = \{ x\in I | x \mbox{ is in every inductive set } \}$. This set $\displaystyle \mathbb{N}$ are called the natural numbers and this is a purely formal construction of the naturals.

And that is precisely why we can't have half integers contained in $\displaystyle \bold{N}$, because of the principle of induction?

Moreover, the natural numbers $\displaystyle \bold{N}$ never repeat (e.g. we cannot have $\displaystyle 1,2,3,3,4, \ldots )$? What is the difference between formal difference and actual difference (e.g. we have $\displaystyle a // b$ and $\displaystyle a--b$)?

11. Originally Posted by particlejohn
And that is precisely why we can't have half integers contained in $\displaystyle \bold{N}$, because of the principle of induction?
I do not know what you mean by this.

Moreover, the natural numbers $\displaystyle \bold{N}$ never repeat (e.g. we cannot have $\displaystyle 1,2,3,3,4, \ldots )$? What is the difference between formal difference and actual difference (e.g. we have $\displaystyle a // b$ and $\displaystyle a--b$)?
I do not know what you mean by this. Do define $\displaystyle a-b$ we find need to define what it means $\displaystyle a+b$ for arbitrary integers.