What is the contrapositive of the definition of onto?

Question

I feel that the problem I am working on will be easier to prove by contrapositive, namely instead of showing surjective I want to show the contrapositive of surjective.

Answer 1

The term "contrapositive" refers to a certain formal transformation of implications.

Specifically, the contrapositive of $$p\implies q$$ is $$\lnot q \implies \lnot p.$$

It doesn't really make sense to ask for the contrapositive of a property like surjectivity.

Edit:

The statement "$f\colon A \to B$ is surjective" (when $f$ is known to be a function from $A$ to $B$) can be written $$(\forall y\in B)(\exists x \in A)\bigl((x,y)\in f\bigr).$$

The negation of this statement is $f\colon A \to B$ is not surjective.

By the usual laws of predicate logic, this is equivalent to $$(\exists y\in B)(\forall x \in A)\lnot\bigl((x,y)\in f\bigr).$$

Answer 2

What you're (probably) looking for is the negation of the definition of surjective. To find the negation, remember that "for alls become there exists" and "there exists become for alls". So,

$$ \neg (\forall b\in B\exists a\in A: f(a)=b)\quad\text{is}\quad (\exists b\in B:\forall a\in A, f(a)\neq b) $$ Try to really think about what surjective means though, and what it would mean to not be that. Drawing pictures always helps!

Answer 3

A function $f:X\to{Y}$ is surjective if:

$$(\forall y)\space(\exists x)\space{f(x)}=y$$

Negating this:

$$\lnot((\forall y)\space(\exists x)\space{f(x)}=y)$$

$$(\exists y)\space\lnot((\exists x)\space{f(x)}=y)$$

$$(\exists y)\space(\forall x)\space{f(x)}\ne{y}$$

Therefore the contrapositive of the standard definition of surjective is:

If there exists a $y\in{Y}$ such that for all $x\in{X}$ $f(x)\ne{y}$, then $f:X\to{Y}$ is not surjective.

Answer 4

Surjectivity of $f:A\to B$ can be expressed as:

If $b\in B$, then $\exists a\in A: f(a)=b$.

The contrapositive of this is:

If $(\forall a\in A: f(a)\neq b)$ then $b\notin B$.

I can't imagine any case where that would be any easier to prove, however.