This proof seems contradictory

Question

I was thinking about a proof I read of the statement, that no bijections exist from a set $X$ onto its power set $P(X)$ exists:

Proof (by contradiction)

Let $X$ be a nonempty set, $f:X\rightarrow P(X)$ be a bijection, and $A\subset X$ be defined as $A:=\{x\in X|\;x\not\in f(x)\}$. Consequently, for $x_0\in X$ with $f(x_0)=A$ (which exists since f is bijective) we get $x\in A\Leftrightarrow x\not\in A$, a contradiction. Therefore $f$ cannot be bijective.
End of proof.

I would like to know if there isn't any restriction or rule against the definition of $A$, since it seems to me that if it is permissible, then you should also be allowed to define a set $B:=\{x\in X|\; x\not\in B\}$ for every set X. This would always lead to the contradiction $x\in B\Leftrightarrow x\not\in B$.
I know I probably am just confused, but I need someone to explain to me what I got wrong. Where is the mistake?

Answer 1

That rule is fine. If you defined $B = \{x \in X\ |\ x \not\in X\}$, then $B$ would simply be the empty set.

Defining $B = \{x \in X\ |\ x \not\in B\}$ is problematic since it is self-referential.

Answer 2

You are right, this isn't so easy.

We get problems if definitions are referring to themself (like in your example) or when they go into circles, like this: \begin{align} a &:= b+1 \\ b &:= a+1 \end{align}

To protect ourself from evil things like this, there is a trick: Not only is it important how things are defined, but also the order in which they are. A definition is allowed to use things that are defined already, but none that are defined just in that moment.

In the proof:

1. Some nonempty set $X$
2. The Powerset of $X$, namly $P(X)$
3. A funktion $f : X \rightarrow P(X)$
4. A set $A:=\{x\in X|\;x\not\in f(x)\}$
5. An element $x_0$ from $X$

Number 4 does use Number 3, 3 uses 2 and 1. But at no point you use the point you are already in.

Your counterexample would look like this:

1. A set $B:=\{x\in X|\; x\not\in B\}$

But number 1 uses number 1 already. This is forbidden, for exactly the reason you came up with.

---

Note: I see, there are recursive definitions like

\begin{equation} x! = \begin{cases} 1 & \text{if } x = 1 \\ x \cdot (x-1)! & \text{else} \end{cases} \end{equation}

But these are actually problematic if you get them wrong, so they have too be checked carefully before they are allowed, so writer and reader can make sure they do make sense. For example this one would be refused by every mathematican:

\begin{equation} f(x) = \begin{cases} 1 & \text{if } x = 1 \\ x \cdot f(x) & \text{else} \end{cases} \end{equation}

---

Actually (as always in maths) things can get even a bit more complicated. Things might not be defined in an order, but in levels, enumerated with $\mathbb{N}_0$. Things defined in level $0$ are axioms. Things in a higher level $n$ are allowed to use level $0$ to $n-1$ in their definition, but not higher. Logicians will have fun from there on.