Why does this proof of the Schröder Bernstein Theorem work?

Question

I have worked myself through the first proof of the Schröder - Bernstein - Theorem on ProofWiki (https://proofwiki.org/wiki/Cantor-Bernstein-Schr%C3%B6der_Theorem as a reference) and have understood the gist of it. However, I struggle with a few steps and I am fairly certain that it is due to my lack of fundamentals in logic/proof techniques/limits. A quick summary of what I understood:

• The author effectively constructs a nested interval sequence and uses set difference and union properties to create equivalent subsequences and "helping" sequences.

• Then he goes to show that the cardinality of the "sub set differences" are the same in the last few steps, and that one can therefore conclude the existence of a bijection.

So far so good. However, here my question arises:

At a point denoted by (1) in the proof, the author writes that $S = (S\backslash S_{1}) \cup (S_2\backslash S_{3}) \cup (S_4\backslash S_{5})...\cup D$. While it intuitively makes sense that this is true, I don't know why I am allowed to set up this infinite union. How can I prove this is true? I have a gut feeling that this might have to do something with the Axiom of Choice or induction or some logic rule but I don't know.

Answer 1

This has everything to do with recursion and nothing to do with the Axiom of Choice. The reason is that we are not selecting arbitrary sets (with some proprety) to be our $S_n$, but rather we have a concrete function we just keep applying.

The recursion theorem itself requires a modicum of Replacement axioms in general, however, in this case we can dispense of this using and rely only on Separation axioms (since we have a good set bounding this entire process).

So once we have the sequence of sets $\{S_n\mid n\in\Bbb N\}$, we are allowed to take its union or do all sort of pointwise manipulations (as long as they are done the same everywhere), which is why we are allowed to talk about $S_{n+1}\setminus S_n$, etc.

Answer 2

In that point (1) of the first proof, the author does not write $$S = (S\backslash S_{1}) \cup (S_2\backslash S_{3}) \cup (S_4\backslash S_{5})...\cup D$$ but $$S=(S \setminus S_1)\cup(S_1 \setminus S_2)\cup \ldots \cup(S_k \setminus S_{k + 1})\cup \ldots \cup D$$ (where $D=\bigcap_{k\in\Bbb N}S_k$), which means $$S=(S\setminus S_1)\cup\bigcup_{k\in\Bbb N}(S_k \setminus S_{k + 1})\cup D.$$ This equality is elementary: for any $x\in S_1\setminus D,$ $x$ belongs to $S_k\setminus S_{k+1}$ where $k$ is defined as the smallest such that $x\notin S_{k+1}.$