1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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\}$. $\endgroup$ – egreg Nov 10 '18 at 0:23
  • $\begingroup$ 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. $\endgroup$ – DiscipleOfKant Nov 10 '18 at 0:25
  • $\begingroup$ My apologies, my comments keep getting deleted for some reason. Thank you for your comments, they were very helpful. That is much simpler. $\endgroup$ – DiscipleOfKant Nov 10 '18 at 0:25

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.