# Providing a bijective rule for a function

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.

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

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.

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.

• @DiscipleOfKant That's simpler: Since $Z\setminus\{x\}\subseteq Z$ and $x\in Z$, we have $(Z\setminus\{x\})\cup\{x\}\subseteq Z$. On the other hand, if $z\in Z$, then either $z=x$ or $z\in Z\setminus\{x\}$. – egreg Nov 10 '18 at 0:23
• I believe so. Let yY*∪ {*x}. Then there are two cases: yY or y = x. Case 1: yY . Since Y = Z \ {x} (which by definition of set difference, yZ \ {x} iff yZ and y ∉ {x}), and we know by supposition that y is not equal to x, then y is an element of Z. Case 2: y ∈ {x}. Then y = x and we know xZ by the principal supposition. Therefore yZ. In either case, yZ; therefore Y = Z \ {x} ⊆ Z. On the other hand, suppose yZ. We know that Y = Z \ {x}, so every element in Z is in Y, except for x. – DiscipleOfKant Nov 10 '18 at 0:25
• My apologies, my comments keep getting deleted for some reason. Thank you for your comments, they were very helpful. That is much simpler. – DiscipleOfKant Nov 10 '18 at 0:25