Intereting Posts

Why a linear numerator for fractions with irreducible denominators?
Why is the group of units mod 8 isomorpic to the Klein 4 group?
Do Ramsey idempotent ultrafilters exist?
$1/r^2\int_{\mathbb{S}_r}u-u(x)$ converging to $\Delta u(x)$?a
How to construct $\{\{\{…\}\}\}$ in ZF without axiom of foundation
Eigen Values Proof
Can an odd perfect number be divisible by $101$?
Idempotents in $\mathbb Z_n$
The center of a group with order $p^2$ is not trivial
What's the difference between arccos(x) and sec(x)
Long exact sequence into short exact sequences
If p is prime and k is the smallest positive integer such that a^k=1(modp), then prove that k divides p-1
Abelian $p$-group with unique subgroup of index $p$
Is $f$ measurable with respect to the completion of the product $\sigma$-algebra $\mathcal{A} \times \mathcal{A}$ on $^2$?
References on Inverse Problems, Approximation theory and Algebraic geometry

I got this question in homework:

Let $\{0,1\}^A$ the set of all functions from A (not necessarily a finite set)

to $\{0,1\}$. Find a correspondence (function) between $\{0,1\}^A$ and

$\mathcal P(A)$ (The power set of $A$).

Prove that this correspondence is one-to-one and onto.

I don’t know where to start, so I need a hint. What does it mean to find a correspondence?

I’m not really supposed to define a function, right?

I guess once I have the correspondence defined somehow, the proof will be easier.

- Uniqueness proof for $\forall A\in\mathcal{P}(U)\ \exists!B\in\mathcal{P}(U)\ \forall C\in\mathcal{P}(U)\ (C\setminus A=C\cap B)$
- What are good books/other readings for elementary set theory?
- Union of Cartesian products: $X \times (Y \cup Z)= (X \times Y) \cup(X\times Z)$
- Bijection Contruction
- $F$ is a free abelian group on a set $X$ , $H \subseteq F$ is a free abelian group on $Y$, then $|Y| \leq |X|$
- Does $f^{-1}(Y)$ make sense if $Y$ is “bigger” than $X$

Any ideas? Thanks!

- Making sense out of “field”, “algebra”, “ring” and “semi-ring” in names of set systems
- substituting a variable in a formula (in logic)
- how to solve binary form $ax^2+bxy+cy^2=m$, for integer and rational $ (x,y)$
- Is Russell's paradox really about sets as such?
- Proving $\kappa^{\lambda} = |\{X: X \subseteq \kappa, |X|=\lambda\}|$
- What does the Axiom of Choice have to do with right inversibility?
- Why does Newton's method work?
- For sets $A,B$, $A \cap (B \setminus A) \subseteq \varnothing$
- A limit ordinal $\gamma$ is indecomposable if and only if $\alpha + \gamma = \gamma$ if and only if $\gamma = \omega^{\alpha}$ for some $\alpha$.
- How do I rigorously show $f(\cap \mathcal{C}) \subset \cap f(\mathcal{C})$

This is essentially the same as Martin and yuone’s answers:

Fix a set $A$. For a function $f$ from $A$ to $\{0,1\}$, let $ A_f$ be the set of elements of $A$ that are mapped to 1 by $f$. That is, $a\in A_f$ if and only if $f(a)=1$.

Consider the map $\Phi(f) =A_f$.

Now if $f\ne g$, there is an $a\in A$ with $f(a)=0$ and $g(a)=1$ (or $f(a)=1$ and $g(a)=0$).

Then $A_f\ne A_g$. So $\Phi$ is one-to-one.

Now let $B\in{\cal P}(A)$. Define $f(x)=\cases{1,&x\in B\cr 0,&x\notin B }$.

Then $\Phi(f)=B$. This shows that $\Phi$ is onto ${\cal P}(A)$

For any function $f\in\{0,1\}^A$ try associating it with $f^{-1}(1)$ in $\mathcal{P}(A)$, that is, the subset of $A$ whose elements map to $1$ under $f$.

What about $f:{\mathcal P (A)}\to {\{0,1\}^A}$ and $g:{\{0,1\}^A}\to{\mathcal P(A)}$ given by

$$

\begin{align}

&f(X)=\chi_X &\text{ for $X\subseteq A$,}\\

&g(h)=\{x\in A; h(x)=1\} &\text{ for $h:A\to{\{0,1\}}$,}

\end{align}

$$

where $\chi_X(x)=1$ for $x\in X$ and $\chi_X(x)=0$ for $x\notin X$,

i.e. $\chi_X$ is the characteristic function of the set $X$.

Can you show that these two functions are inverse to each other?

NOTE: This is basically the same thing as yunone’s answer, I’ve just added the inverse function too.

I’ll try to say this without all the technicalities that accompany some of the earlier answers.

Let $B$ be a member of $\mathcal{P}(A).$

That means $B\subseteq A$.

You want to define a function $f$ corresponding to the set $B$. If $x\in A$, then what is $f(x)$? It is: $f(x)=1$ if $x\in B$ and $f(x) = 0$ if $x\not\in B$.

After that, you need to show that this correspondence between $B$ and $f$ is really a one-to-one correspondence between the set of **all** subsets of $A$ and the set of **all** functions from $A$ into $\{0,1\}$. If has to be “one-to-one in both directions”; i.e. you need to check both, and you need to check that the word “all” is correct in both cases.

- Flatness and intersection of ideals
- Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$
- Proof that a sequence converges to a finite limit iff lim inf equals lim sup
- Manifolds with boundaries and partitions of unity
- Using floor, ceiling, square root, and factorial functions to get integers
- Example of $f,g: \to$ and riemann-integrable, but $g\circ f$ is not?
- Evaluating $\int\frac{x^b}{1+x^a}~dx$ for $a,b\in\Bbb N$
- “Eigenrotations” of a matrix
- How can we construct *Fine uniformities*?
- Show that $(X\times Y)\setminus (A\times B)$ is connected
- The probability of countably infinite independent sequence of events as a product of probabilities
- Surjectivity of a map between a module and its double dual
- Prove that $T$ is an orthogonal projection
- Inclusionâ€“exclusion principle
- The proof of the Helmholtz decomposition theorem through Neumann boundary value problem