Union of Nest of Injections is Injection/Proof

From ProofWiki
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