1
$\begingroup$

Consider the set $A =\{3,4\}$. Its power set is $P(A) = \{\varnothing, \{3\}, \{4\}, \{3,4\}\}$. $2^A$ is defined as the set of all functions from $A$ to $2$. Letting $2 = \{\varnothing, \{\varnothing\}\}$, we have the cartesian product $$A \times 2 = \{\langle 3, \varnothing \rangle, \langle 3, \{\varnothing\}\rangle,\langle4,\varnothing\rangle,\langle4,\{\varnothing\}\rangle\}$$ Finally, we know that $f \in 2^A \iff f \in P(A \times 2)$ and $f$ is a function.

Notice that the power set $P(A\times2)$ will have the singleton of each element in $A\times2$ (which will be functions in the set-theoretical sense), and other combinations like $\{\langle3,\varnothing\rangle, \langle4,\varnothing\rangle\}$. But this will mean that there are more than 4 elements of $P(A \times 2)$ that are functions (in the set-theoretical sense of a relation), and that therefore $P(A)$ and $2^A$ aren't equinumerous.

Clearly I'm doing something very wrong here, would anyone have a hint?

$\endgroup$
3
  • $\begingroup$ Your description of $f\in2^A$ is incorrect. you need $f$ to be a set-theoretic function and have domain equal to $A$. $\endgroup$
    – Arturo Magidin
    Aug 16, 2021 at 4:38
  • $\begingroup$ The bijection is trivial: given a function $f\colon A\to 2$, define the subset $A_f=\{a\in A\mid f(a)=1\}$. The inverse of this correspondence maps a subset $B\subseteq A$ to its indicator function $\xi_B\colon A\to 2$, $\xi_B(x) = 0$ if $x\notin B$, and $\xi_B(x)=1$ if $x\in B$. $\endgroup$
    – Arturo Magidin
    Aug 16, 2021 at 4:39
  • $\begingroup$ ah, that's what I was missing! thank you so much for the tip! $\endgroup$
    – shintuku
    Aug 16, 2021 at 4:40

1 Answer 1

Reset to default
0
$\begingroup$

The $4$ members of $2^A$ are $\{(3,0)(4,0)\},\{(3,0)(4,1)\}\{(3,1)(4,0)\}\{(3,1)(4,1)\}.$ These are subsets of $A\times 2$ but there are $12$ other subsets of $A\times 2$. A member of $P(A\times 2)$ is a member of $2^A$ iff it is the characteristic (indicator) function of a subset of $A.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.