Preimages All Exist iff Surjection/Corollary

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $f: S \to T$ be a mapping.

Let $f^{-1}$ be the inverse of $f$.


$\forall B \subseteq T, B \ne \O: f^{-1} \sqbrk B \ne \O$

if and only if:

$f$ is a surjection

where $f^{-1} \sqbrk B$ denotes the preimage of $B \subseteq T$.


Proof

Necessary Condition

Let $f$ be a surjection.

Let $B \subseteq T$ such that $B \ne \O$.

Then:

$\exists t \in T: t \in B$

From Preimages All Exist iff Surjection:

$\map {f^{-1} } t \ne \O$

As $t \in B$ it follows from Preimage of Subset is Subset of Preimage that:

$f^{-1} \sqbrk B \ne \O$

$B$ is arbitrary, so:

$\forall B \subseteq T, B \ne \O: f^{-1} \sqbrk B \ne \O$

$\Box$


Sufficient Condition

Suppose that:

$\forall B \subseteq T, B \ne \O: f^{-1} \sqbrk B \ne \O$

Aiming for a contradiction, suppose $f$ is not a surjection.

Then by definition:

$\exists t \in T: \neg \paren {\exists s \in S: \map f s = t}$

That is:

$\exists \set t \subseteq T: f^{-1} \sqbrk {\set t} = \O$

which contradicts the hypothesis.

So by Proof by Contradiction, $f$ is a surjection.

Hence the result.

$\blacksquare$


Sources