Are proofs by contradiction and counterexample two different techniques?
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$.
$\endgroup$ 22 Answers
$\begingroup$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.
$\endgroup$ 2 $\begingroup$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.
$\endgroup$
