/sci/ - Science & Math

>>15043717
Well, going by your picture (which contains a typo in the definition of [math]g_B[/math]), the author implicitly defines the function [math]f:\mathcal{P}(A)\rightarrow\{0,1\}^{A}[/math] so that [math]f(B)=g_{B}[/math] for each [math]B \in \mathcal{P}(A)[/math] where [eqn]g_{B}(x)=\begin{cases} 0 & \text{if $x\in B$} \\ 1 & \text{if $x \in A \setminus B$} \end{cases}[/eqn]Now we need to prove that [math]f[/math] is a bijection

Proof that [math]f[/math] is injective:
Assume [math]X,Y \in \mathcal{P}(A)[/math] and [math]f(X)=f(Y)[/math]. then we have [math]g_X=f(X)=f(Y)=g_Y[/math], so if [math]z \in X[/math] then [math]g_Y(z)=g_X(z)=1[/math] so [math]z \in Y[/math], and similarly if [math]z \in Y[/math] then by the same reasoning we have [math]z \in X[/math] so [math]X=Y[/math] by the the Axiom of Extensionality.

Proof that [math]f[/math] is surjective:
Let [math]g \in \{0,1\}^{A}[/math] so [math]g[/math] is a function from [math]A[/math] to [math]\{0,1\}[/math], now consider the set [math]X = \{x \mid g(x) = 0\}[/math] (This is the inverse image of {0} under g if you understand what that means) then [math]X \subseteq A[/math], i.e. [math]X \in \mathcal{P}(A)[/math]. So we have [math]f(X)=g_X[/math], now you can check that [math]g=g_X[/math], and therefore we found an [math]X[/math] such that [math]f(X)=g[/math] so [math]f[/math] is surjective.


Note that this may be a bit too long and detailed because i'm bad at being concise, in practice you won't find many mathematicians who write a detailed step by step (formal) proof. So you should also try to practice being concise, this is something i'm still trying to learn myself.