I am looking for a rule of association which establishes a natural bijection from $\{Y ⊆ X: x ∉ Y\}$ to $\{Y ⊆ X: x ∈ Y\}$ (where $x ∈ X$) and I would like to prove that the rule is a bijection.
Here's the rule I came up with: $X ↦ X ∪ \{x\}$
To show this is a bijection, we must show that it is both injective and surjective.
Showing that each element of the domain maps to a unique value in the codomain: Suppose there are two elements from the codomain, call them $B$ and $C$, such that $A ↦ B$ and $A ↦ C$. By the rule of association given, this would mean $A ∪ \{x\} = B$ and $A ∪ \{x\} = C$. So $B = C$.
Injective: Each element of the codomain would be mapped to by at most one element from the domain. Let $A$ be an element of the codomain and $B$, $C$ be elements of the domain such that $B ↦ A$ and $C ↦ A$. By the rule of association, $B ∪ \{x\} = A$ and $C ∪ \{x\} = A$. But then $B$ must be equal to $C$ since we are adding the same, single element to each set and as a result, they are equal.
I am pretty sure that what I have up to this point is correct (although if anyone spots any errors in the proof or the rule of association, that would be greatly appreciated). However, I am not quite sure how to prove that the rule is surjective. I was wondering if anyone can help me out.
Best Answer
The map is, more precisely, $Y\mapsto Y\cup\{x\}$. It certainly is a map $$ \{Y\subseteq X:x\notin X\}\to\{Y\subseteq X:x\in X\} $$ because obviously $Y\cup\{x\}$ is a subset of $X$ and $x\in Y\cup\{x\}$.
The map is injective. Suppose $Y\cup\{x\}=Z\cup\{x\}$, with $x\notin Y$ and $x\notin Z$. Let $y\in Y$; then $y\in Y\cup\{x\}=Z\cup\{x\}$, so $y\in Z$ or $y=x$; the latter case cannot happen, so $y\in Z$. Hence $Y\subseteq Z$ and, by symmetry, $Z\subseteq Y$.
The map is surjective. Suppose $x\in Z\subseteq X$; then $x\notin Y=Z\setminus\{x\}$. Can you prove that $Y\cup\{x\}=Z$?
Your argument is sound up to a detail: when you say
you should point out that the reason for $B=C$ is that $x\notin B$ and $x\notin C$.
As an example, if $B=\{0\}$, $C=\{0,1\}$ and $x=1$, then $B\cup\{x\}=C\cup\{x\}$, but $B\ne C$. This doesn't contradict injectivity of your map, because $x\in C$, in this case.