Question

g

Answer 1

\[P(A) ~ \left\{ 0,1 \right\}^A\]

Answer 2

There's ~ between the two

Answer 3

In this case \(
\{0,1\}^A
\) means take the Cartesian product \(|A|\) times?

Answer 4

that is actually the next part of this question

Answer 5

How would you show the equivalence of a function to a set?

Answer 6

One is a set of functions, the other is a set of sets.

Answer 7

It's got to do with this idea if A ~ B then it means there exists a bijection from A to B. Or there's exists injections from A to B and B to A.

Answer 8

Well if the functions map from elements of the set to 0 or 1, you could interpret 0 as the element not being in a subset and 1 as being in the subset.

Answer 9

So each function could represent a subset.

Answer 10

I had that idea in my mind, but couldn't formalize it into a proof

Answer 11

Just do induction on \(|A|\).

Answer 12

Or do you have to prove it for the infinite case?

Answer 13

well yeah both for finite and infinite A

Answer 14

Let \(S_i\subseteq \mathcal{P}(A) \). We map \(S_i \) to \(f_i\) when the following is true: \( S_i = \{x\in A | f_i(x)=1\}\)

Answer 15

Also \(f_i \in \{0,1\}^A\)

Answer 16

Then you could try to show a mapping from \(i\) to a subset/function

Answer 17

Hmmm, actually you might try a proof by contradiction.

Answer 18

interesting

Answer 19

It seems you'd need axiom of choice to do this for the infinite case.

Answer 20

Let \(S_i \in \mathcal{P}(A)\) (clearly \(S_i\subseteq A\))
Let \(f_j \in \{0,1\}^A\) (where \(f_j:A\to \{0,1\} \))

Let \(G: \{0,1\}^A\to \mathcal{P}(A)\)
We can define the \(G\) as follows:
\(G(f_j) = \{x\in A|f_j(x)=1\}\)
\(G\) is a function which takes a function and returns a set.

Let \( H: \mathcal{P}(A) \to \{0,1\}^A\)
We can define \(H\subseteq A\times \{0,1\}\) as follows:
\(H(S_i) = \{(x,0)|x\notin S_i\} \cup\{(x,1) |x\in S_i\} \)
\(H\) is a function that takes a set and returns a function.

Answer 21

At this point it just becomes a matter of rigor. We've show a mapping from subsets to functions, and we've shown a mapping from functions to subsets.