Union of Nest of Injections is Injection
Jump to navigation
Jump to search
Theorem
Let $N$ be a nest of mappings which are all injections.
Then:
- $\bigcup N$ is an injection
where $\bigcup N$ denotes the union of $N$.
Proof
From Union of Nest of Mappings is Mapping we have that $\bigcup N$ is a mapping.
Aiming for a contradiction, suppose:
- $\exists x_1, x_2: \tuple {x_1, y} \in \bigcup N \land \tuple {x_2, y} \in \bigcup N$
such that:
- $x_1 \ne x_2$
Then:
- $\exists f \subseteq \bigcup N: \tuple {x_1, y} \in f$
and:
- $\exists g \subseteq \bigcup N: \tuple {x_1, y} \in g$
But because $N$ is a nest of mappings, either:
- $f \subseteq g$
or:
- $g \subseteq f$
That means either:
- $\tuple {x_1, y} \in g$
or:
- $\tuple {x_2, y} \in f$
Hence either $f$ or $g$ has both $\tuple {x_1, y}$ and $\tuple {x_2, y}$ in it.
That is, either $f$ or $g$ is not an injection.
From this contradiction it follows that if:
- $\exists x_1, x_2: \tuple {x_1, y} \in \bigcup N \land \tuple {x_2, y} \in \bigcup N$
then it has to be the case that:
- $x_1 = x_2$
It follows that $\bigcup N$ is a an injection.
$\blacksquare$
Sources
- 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $6$: Order Isomorphism and Transfinite Recursion: $\S 1$ A few preliminaries: Proposition $1.4$