Talk:Injection iff Left Inverse

From ProofWiki
Jump to navigation Jump to search

Possible error here, though I'm quite tired:

In proof 1., $\Leftarrow$ direction; there's a line ... "Note that the existence of such a g requires that $S \neq \emptyset$".

But $\exists g : T \to S : gf = \text{id}_S$ holds for any $g : T \to S$ when $S = \emptyset$ since $(\forall x \in S)(g(f(x)) = x)$ is vacuous.

So in fact the $\neq \emptyset$ hypothesis can be scrapped? --Linus44 04:23, 16 June 2011 (CDT)

If $S = \varnothing$ then $g: T \to S$ is not a mapping: $\forall t \in T: \not \exists s \in S: s = g(t)$.
Every element of the domain of $g$ needs to map to at least one element of the codomain of $g$.
Hence $S$ needs to be non-null for the mapping to be defined as a mapping. -- 05:31, 16 June 2011 (CDT)

The potential issue is that functions as defined here are required (among other things) to be left-total relations. Nevertheless, it would be okay for $S=\emptyset$ in the first part of the proof. Then the assumption that a left inverse exists just means that by assumption $T=\emptyset$ and the left-inverse is the empty function. This is irrelevant though anyway in this direction of the proof since $S=\emptyset$ implies that any function defined on $S$ is injective, we don't even need to suppose a left inverse exists.
It's a real issue in the other direction. Again, if $S=\emptyset$, any $f:S\to T$ is vacuously injective (so here the assumption is unnecessary), but it has no left inverse unless $T=\emptyset$. In this case, the obstruction to getting a left-inverse isn't the sentence asserting that it is the identity on $S$ (which you correctly observed would be vacuously satisfied even by any relation $g:T\times S$). The problem is that the definition of a function prohibits the existence of a function $g:T\to \emptyset$.
-- Qedetc 10:57, 16 June 2011 (CDT)

I see now, my mistake --Linus44 02:18, 17 June 2011 (CDT)