2

New to proofs.

Suppose I want to prove $f: \mathbb Z \to \mathbb Z$ as $f(n) = 2n$ for all $n$ is not onto. Are the two arguments below valid, separate proofs? Are they invalid iterations of a single proof?

By contradiction:

Suppose $f$ is onto. Then for all $m \in \mathbb Z$, there's some $k \in \mathbb Z$ such that $f(k) = 2k = m$ which implies $k = \frac m2.$ Then $k \not \in \mathbb Z$ for all $m \in \mathbb Z.$ Contradiction.

By counter-example:

$1$ has no pre-image in $\mathbb Z$.

user366786
  • 37
  • They are both valid. In this case, you just need to find one integer that cannot be mapped to by the $f$ function. Personally I would prefer that you be more specific in the first proof (i.e., "then $k \notin \mathbb{Z}$ if $m$ is odd, contradiction"). Similar for the second (explain why 1 has no pre-image). – Michael Sep 06 '16 at 21:11
  • 2
    Math is not as flexible as English. I assume by "$k\notin \mathbb Z$ for all $m\in \mathbb Z$" you meant that for some $m\in \mathbb Z$ we have that $k\notin \mathbb Z$. It's incorrect to write it that way. What you wrote is only true if $k$ is never an integer. – Matt Samuel Sep 06 '16 at 21:19

2 Answers2

1

Your first proof seems to be wrong. Why does $k \notin \mathbb Z$? Your second proof seems to be correct, although if someone seriously wants a proof of the non-surjectivity of $f$, perhaps they want more detail.

As for the difference between proofs by counterexample and proofs by contradiction: there is no way to answer this question exactly without making precise by what you mean by a proof by counterexample, and what you mean by "different techniques", but I interpret it as something like this:

Let $P$ be some property. You are asked to prove $\neg\forall x P(x)$. A proof by counterexample constructs some $c$, and then proves $\neg P(c)$, effectively proving $\exists x \neg P(x)$. A proof by contradiction assumes $\forall xP(x)$ and then derives a contradiction.

In classical mathematics, these results are easily seen to be equivalent. However, if we move to constructive mathematics, then in fact these two are not equivalent; it is possible that you are able to prove $\neg \forall x P(x)$ without being able to prove $\exists x\neg P(x)$. This suggests that (even in classical mathematics) these are not quite the same proof technique, because by just slightly weakening what kind of argument we allow, the conclusion of one does not follow from the conclusion of the other.

Mees de Vries
  • 26,947
  • I think that statement in the first proof "then $k \notin \mathbb{Z}$ for all $m \in \mathbb{Z}$" is not intended to mean that there is no integer $m$ for which it is true, only that it is not true for all integers $m$ (i.e., there are some integers $m$, namely odds, for which it fails). I agree that statement could be clarified. – Michael Sep 06 '16 at 21:17
  • I understood this : $\exists m \in Z / k \notin Z$ –  Sep 06 '16 at 21:25
0

You first proof is not worded correctly. The statement "$k \notin \mathbb{Z}$ for all $m \in \mathbb{Z}$" is not true since there are some values of $m \in \mathbb{Z}$ for which $k \in \mathbb{Z}$. For the proof, you need to only exhibit one value of $m$ for which there does not exist a $k \in \mathbb{Z}$ satisfying $2k=m$.

One way to prove $p \Rightarrow q$ is to assume $p$ is true and $q$ is false and then arrive at a contradiction. This argument is valid because $(p \wedge \neg q) \Rightarrow F$ is logically equivalent to $p \Rightarrow q$. In the example given, the hypothesis is the definition of the function $f$ and the conclusion is that $f$ is not onto. So we can assume the hypothesis is true and the conclusion is false and arrive at a contradiction. Indeed, if $f$ is onto, then there exists an integer $k$ such that $2k=1$, which is impossible.

Both your proofs are essentially the same.

Ashwin Ganesan
  • 4,045
  • 11
  • 10