3
$\begingroup$

The example question is "prove that every integer that is divisible by 10 must be an even integer".

However this can be generalized to prove that every x is Q, where is a statement such as "must be an even integer". So what is the best way to approach this proof? Contradiction, contrapositive, direct?

My thinking was:

Question translates to $\forall A(10k=A\rightarrow A = 2c)$, such that $k\in\mathbb Z,c\in\mathbb Z$ (also can someone tell me if this way of translating the question is correct)

From there:

Let B be some number that is divisible by 10. In other words, $B=10K$, where $K\in\mathbb Z$

$B = 2(5K)\\B=2P$

Therefore, B is even because for some B, divisible by 10, B must be even by the definition of even numbers.

Is this form the best way to prove these types of questions? Does this count as a proof by contradiction?

Edit: Or would a proof by induction work best here? In that case how would this question be proven (I have an idea; just need a confirmation)?

$\endgroup$
  • 1
    $\begingroup$ What do you mean with "every $x$ is $Q$"? What is $Q$? $\endgroup$ – Cornman Aug 24 '18 at 20:51
  • $\begingroup$ Q is just some statement, for example, "must be an even integer". $\endgroup$ – user2793618 Aug 24 '18 at 22:42
3
$\begingroup$

So what is the best way to approach this proof? Contradiction, contrapositive, direct?

I think there is no "best way" to approach a proof. But most of the time a direct proof should be tried first, because they are most of the time more clear and have other advantages over a proof by contradiction, for example.

Like that a direct proof can give you an algorithm which you can use or implement.

Your translation of the question seems fine to me. Your proof also looks good, but it is not a proof by contradiction. That would be a direct proof.

A proof is generaly build like this. You assume, that $A$ holds and then you conclude $B$. $A\Rightarrow B$. $A$ is here the statement, that you have an integer $k$, which is divisable by $10$. And you want to conclude $B$, which is that $k$ has to be divisable by $2$.

In a proof by contradiction you assume, that not $B$ holds and conclude that not $A$ holds. $\neg B\Rightarrow \neg A$.

It is $A\Rightarrow B\leftrightarrow \neg B\Rightarrow \neg A$.

EDIT: (For the following note the answer of Arsen Berk)

[A proof by induction does not work here. First of all you are working over the integers, but induction is for statements over the natural numbers. Also I can not imagine how the inductive step should work out here. There is no link to this task and induction.]

$\endgroup$
  • 1
    $\begingroup$ Induction can work here by redefining the numbers that we are examining. OP defines the number as $B = 10K$ for example, where we can use induction on $K$ from $1$ to $n$ to examine the positive integers. But if we define the number as $B = -10K$, then, again, we can use induction on $K$ to examine the negative numbers. $B = 0$ is the trivial case so, maybe not in one case, but in three cases, we can complete our induction on $\mathbb{Z}$. $\endgroup$ – ArsenBerk Aug 24 '18 at 21:04
  • 2
    $\begingroup$ @ArsenBerk Thanks. Yeah I thought about that and of course it is true, but I think you should definitly not proof this by induction. :) I was about to comment this question under your answer. But what ever works, I guess. One should not go to crazy about induction as a newcomer in math, I think. $\endgroup$ – Cornman Aug 24 '18 at 21:09
  • 2
    $\begingroup$ Yes, you are right about induction's unsuitability for this case. That's why I also said "I don't think an inductive argument is needed for this kind of proof" :) After you mentioned it, I also realized that we would have three cases to consider while doing induction so that is really crazy. $\endgroup$ – ArsenBerk Aug 24 '18 at 21:14
  • 1
    $\begingroup$ @user2793618 You are right. $\neg B\Rightarrow\neg A$ would be the structure of a proof by contraposition. A proof by contradiction reads kinda like that. Let $A$ be true. Suppose $B$ is wrong. Then holds $\neg B$. Bla bla bla. This would be a contradiction. Therefor the assumtion is wrong. I mixed that up. Thanks for pointing that out. $\endgroup$ – Cornman Aug 25 '18 at 2:37
  • 1
    $\begingroup$ @user2793618 When a statement holds for every natural number, and you want to proof it. You can do this by induction. But it is not necessary and also not all the time possible. Sometimes induction is a good choice, sometimes it is not. Sometimes induction work, or a direct proof. In general it is up to you. I have never heard, that a direct proof requires a free variable. Not an expert on proof-theory. $\endgroup$ – Cornman Aug 25 '18 at 2:40
3
$\begingroup$

I think your proof does not count as proof by contradiction, it is more like direct way of proving it and if you can think the direct way, in my opinion, it is clear enough (but it is a matter of style so I can't say this is the "best" way). Induction would also work here, but in your direct way, the argument is simple and clear enough to be understood so I don't think an inductive argument is needed for this kind of proof.

Since you asked it, proof by contradiction would be as the following:

Suppose, for a contradiction, that $x \in \mathbb{Z}$ and $x$ is divisible by $10$ but $x$ is not even. But since $10 = 2\cdot 5$, we need to have $2|x$ and $5|x$. But if $2|x$, then $x$ is an even integer, which is a contradiction as required. Therefore, $x$ must be an even integer.

$\endgroup$
  • $\begingroup$ Thanks! So my logic was that since it asked for every integer, I figured a proof by contradiction would be best because you only have to prove one instance of something. I suppose I'm confused on when to use contradiction because doesn't doing a direct proof assumes that you only examine one instance of an integer, not all? $\endgroup$ – user2793618 Aug 25 '18 at 2:19
  • $\begingroup$ Also what can be improved? $\endgroup$ – user2793618 Aug 25 '18 at 2:21
  • 1
    $\begingroup$ In direct proof, what we do is not examining one instance actually. We generalize the form of that instance (like numbers that are divisible by $10$ are in the form of $10k$) and when we prove it for that form, we actually prove it for all instances of that form instead of a single example or examining the argument case by case. $\endgroup$ – ArsenBerk Aug 25 '18 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.