What is the mistake in this proof? During a long night without sleep I managed to come up with a proof for a statement I know is false, and for the life of me I cannot figure out what I did wrong. Where is my mistake?

Theorem: Let $f:A\to B$ be any function. There is a bijection from A onto B.
Proof: By contradiction. Assume there is no bijection from A onto B. Consider the statement "If f is a surjection, then f is an injection." This statement is true iff either f is not a surjection or f is an injection (this is material implication). But this statement is false, because if f is a surjection it can't be an injection because there are no bijections. So then the statement "Either f is not a surjections or it is an injection" is false, meaning f is a surjection and not an injection (demorgan). But if f is not an injection then either f is not an injection or it is a surjection. Using material implication again, this is equivalent to the statement "if f is an injection then it is a surjection," which is false because then there would be a bijection. So f is an injection and not a surjection, which is clearly a contradiction.

This is obviously absurd but I'm having trouble thinking straight. Where is my error?
 A: Your material implication mix the variables:

"If f is a surjection, then f is an injection." This statement is true iff either f is not a surjection or f is an injection (this is material implication).

should be:

"If f is a surjection, then f is an injection." This statement is true iff there exist a function  $g$ such that  $g$ is not an injection and $g$ is a surjection or for all $g$ $g$ is not a surjection (this is material implication).

which is false, so your material application you applied more than two times is actually false.

Edit This was the origin of the mistake and the following statements are just consequences of the negation of this statement. Read this if you want to understand clearly where is the minstakes:
Let's rewrite your proof:

Proof: By contradiction. Assume there is no bijection from $A$ onto $B$. Consider the statement :
  $$P \, \, \text{ "If f is a surjection, then f is an injection."}$$

$P$ does not depend on $f$ , so this statement $P$ is true if and only if  every surjection is an injection. (this is clearly false)

This statement is true iff either f is not a surjection or f is an injection (this is material implication). 

First of all you did not fix any function $f$, so this would be: this statement is true if and only if every surjection is an injection. But the problem in the proof it's the fact you seem to have fixed a function in the biginig but you did not fix any function. If we want to continue to analyse the proof we must fix a function $f$ so let's restart the proof and fix a function:

Proof: By contradiction. Assume there is no bijection from $A$ onto $B$. Fix a function $f$,Consider the statement :
  $$P_f \, \, \text{ "If f is a surjection, then f is an injection."}$$

Now I agree that this a statement will match your thoughts and satisfy your creteria:

This statement $P_f$ is true iff either f is not a surjection or f is an injection (this is material implication). 

now your reasoning is correct and this follows easily.

But this statement is false, because if f is a surjection it can't be an injection because there are no bijections. So then the statement "Either f is not a surjections or it is an injection" is false,



*

*So if $f$ is a surjection then the statement $P_f$ is false

*What if $f$ is not a surjection?, if we investigate a little, it turns out that $P_f$ is true.


And this is not correct , you concluded that $P_f$ is false, but no $P_f$ is not false for every function $f$  , it's false only for functions $f$ which are not surjective (onto) and here in order to pass this step we must assume in the beginning that $f$ is a surjection but every thing will not work simply because what we're trying to prove is not correct!
A: Consider these two statements:

If $f$ is a surjection, then $f$ is an injection.
If $f$ is a surjection, then $f$ is not an injection.

As you noted, your assumption that there are no bijections implies the second statement must be true.  The rest of your reasoning amounts to asserting that only one of the two statements can be true.  But that's not the case.  Both statements are true if the premise, that $f$ is a surjection, is false.  Said symbolically,
$$((P\implies Q)\land(P\implies\lnot Q))\iff \lnot P$$
A: Hint: try a simple example: e.g., let $A = \{1\}$ and $B = \{1, 2\}$, then there is a function from $A$ to $B$, e.g., the function $f$ that maps $1$ to $1$. Now work through your argument to see where it breaks down.
