20
$\begingroup$

Suppose it is asked:

Prove or find a counterexample: the sum of two integers is odd

The fact that 1 + 1 = 2 is a counterexample that disproves that statement. What is the proper format in which to write this? I will provide my attempt.

Theorem: the sum of two integers is odd

Proof:

1 + 1 = 2

=> the sum of two integers may be even

I understand the math, but I'm not sure how to properly present a counterexample relative to an initial theorem. Was this an acceptable presentation of a proof?

$\endgroup$
  • 5
    $\begingroup$ Should it be "Disproof"? And it definitely should be "Hypothesis" (or "Proposition") rather than "Theorem". $\endgroup$ – Joffan Jul 7 '16 at 23:29
  • 14
    $\begingroup$ It's not a theorem, and it's not a proof. So don't write that. $\endgroup$ – Daniel R. Collins Jul 8 '16 at 6:23
  • 2
    $\begingroup$ modus tollens $\endgroup$ – luser droog Jul 8 '16 at 7:47
  • 2
    $\begingroup$ I'm not actually sure that Mathematics.SE is the right forum for this, what you seem to really be asking is "How does my prof want this formatted so I receive maximum credit?" which is actually a question for him/her. Feel free to correct me if I'm wrong... $\endgroup$ – Jared Smith Jul 8 '16 at 13:21
  • 3
    $\begingroup$ More importantly you should not use the term Theorem to refer to such statement. A theorem is a true statement. Use the term claim instead. $\endgroup$ – Bakuriu Jul 8 '16 at 13:34

14 Answers 14

30
$\begingroup$

I would say something along the lines of:

The proposed result is false. Here is a counterexample...

$\endgroup$
27
$\begingroup$

In these cases on my homework when I type it up, I just change the statement of the theorem to match what is true. Given that problem on my homework I would write

$\textbf{Theorem:}$ It is not necessarily the case that the sum of two integers is odd.

$\textbf{Proof:}$ Observe that $1+1=2$. Since $1$ is an integer and $2$ is not odd, we have proved the result.$\blacksquare$

$\endgroup$
  • 25
    $\begingroup$ Even so, that's an odd proof. $\endgroup$ – Thomas Jul 8 '16 at 6:09
  • 2
    $\begingroup$ ^ I appreciate the subtletly of that word play ;) $\endgroup$ – Musa Al-hassy Jul 8 '16 at 6:32
  • 1
    $\begingroup$ ... but is it the oddest proof? $\endgroup$ – Eric Towers Jul 8 '16 at 20:40
  • 6
    $\begingroup$ @EricTowers: I would say it is. As is well, known $2$ is the oddest prime ... $\endgroup$ – Henning Makholm Jul 9 '16 at 0:14
  • 2
    $\begingroup$ It is trivial to prove that no proof is even odder than that one. $\endgroup$ – David Schwartz Jul 9 '16 at 22:51
14
$\begingroup$

Prove or find a counterexample: the sum of two integers is odd.

The above statement is not true and a counterexample can be easily found. It suffices to check the first few positive integers to discover that $1+1=2$.

I think the idea is that since it's not a Proof you shouldn't precede the statement of the counterexample with the word "Proof" like usual. The statement of the counterexample can be viewed just as commentary, and can be formatted as such. Of course the best way to format commentary depends on the context (academic paper, homework, etc).

In general, though, you don't need to worry so much about stuff like this. Always remember that the purpose of writing is to clearly communicate an idea to a reader. Don't stress over a correct way to format your writing. Just worry about your formatting making the meaning of your message clear.

$\endgroup$
  • 2
    $\begingroup$ One of my main concerns, Mike, was that I was disproving the theorem but was using the word proof. In class, the theorem and proof have been stated in this way every time. That's the source of my confusion. I agree with you that clarity is the most important thing when writing. $\endgroup$ – manbearpig1 Jul 7 '16 at 23:29
  • 4
    $\begingroup$ @manbearpig1 Yeah, I've seen many students do that before. I think that as students are learning to write proofs, they get hung up on being formal and proper and forget that the purpose of writing a proof is just to be clear and correct. Honestly I've never liked the decision to put the word "Proof" prior to every proof I write in papers. But I guess that's just the standard thing to do. $\endgroup$ – Mike Pierce Jul 7 '16 at 23:32
  • 2
    $\begingroup$ For an example of very good mathematical writing that doesn't strictly adhere to this kind of formal structure, see Hatcher's Algebraic Topology. I don't recall the use of the word "Proof" like that anywhere, and many key ideas/theorems are just presented in the text as commentary. $\endgroup$ – Mike Pierce Jul 7 '16 at 23:37
6
$\begingroup$

Cite the counterexample. Since $1 + 1 = 2$, the sum of two arbitrary integers is not always odd.

$\endgroup$
  • $\begingroup$ So this is less than formal? There is no predetermined way to present my proof? I am free to use the language, style, organization, etc of my choice? $\endgroup$ – manbearpig1 Jul 7 '16 at 23:28
  • 3
    $\begingroup$ @manbearpig1 One is almost always free to structure their writing however they please. I don't think forms like "Theorem: ___ Proof: ___" are necessarily more formal - they're just used a lot since they make it very clear how those two sections of text relate to each other. $\endgroup$ – Milo Brandt Jul 7 '16 at 23:36
5
$\begingroup$

The "theorem" you are proving, in the specific case you give, is not "the sum of two odd integers is always odd." A "theorem", by definition, is a true (or at least provable) statement. So the "theorem" cannot be "the sum of two odd integers is always odd," because your argument shows that statement to be false.

In fact what you are proving is "the sum of two odd integers may be even." So you could format it as follows, which would be better.

Theorem. The sum of two odd integers may be even.

Proof: The number $1$ is an odd integer, and $1+1=2,$ and $2$ is an even integer.

However, this statement is not really deserving of the name "theorem;" the word "theorem" means "behold" and is usually reserved for results that are worthy of beholding. Better would be "proposition," or, in my opinion, better still would just be "claim."


Side note: You are almost certainly aware of this, but we can of course do better in this situation. The sum of any two odd integers will always be even.

Proposition. Let $m$ and $n$ be odd integers. Then $m+n$ is even.

Proof: Since $m$ and $n$ are odd, there exist integers $k$ and $l$ with $m=2k+1$ and $n=2l+1.$ Hence $m+n=(2k+1)+(2l+1)=2(k+l+1).$ Since $k$ and $l$ are integers, so is $k+l+1,$ and it follows that $m+n$ is even, since it is an integer multiple of $2$.

$\endgroup$
4
$\begingroup$

It looks to me like the biggest step you might be missing is how to formulate the statement you want to prove, which is the complement of the (false) assertion you were given in the exercise. You certainly wouldn't write something like this in a paper (instead you would just express that you are showing a counterexample), but it might be helpful to your thought process to express it as:

Theorem: There exist integers $a$ and $b$ such that $a+b$ is not odd.

Proof: Let $a=b=1$. Then $a+b=2$, and $2|2$, so $a+b$ is even, and therefore not odd.

$\endgroup$
  • 1
    $\begingroup$ Yours is the only answer that states the theorem proven correctly. All the other answers had modals in them, which isn't quite the negation. $\endgroup$ – user21820 Jul 8 '16 at 11:01
4
$\begingroup$

I think you should add some text to help the reader. Here's my interpretation of an acceptable presentation:

Suppose that for any two integers $a$ and $b$, $a+b$ is odd. Letting $a=b=1$, it follows that $a+b=1+1=2$ is odd, a contradiction.

Edit: As pointed out in the comments, your presentation is not acceptable, since you have written "Theorem: the sum of two integers is odd". What you should have written is "Theorem: there exists two integers whose sum is not odd" (the negation of the statement).

$\endgroup$
  • $\begingroup$ It can never be "acceptable" to state "Theorem:" followed by a false statement. As others have pointed out, this is not a theorem. $\endgroup$ – Ari Brodsky Jul 8 '16 at 10:13
  • $\begingroup$ @AriBrodsky: fixed $\endgroup$ – parsiad Jul 8 '16 at 14:18
  • $\begingroup$ Or use "Claim" instead of "Theorem". $\endgroup$ – Laurent LA RIZZA Jul 9 '16 at 20:54
3
$\begingroup$

It would be as follows:

This theorem or proposition is false because the following example satisfy the hypothesis of the theorem but it doesn't satisfy the conclusion.

Example .......

$\endgroup$
3
$\begingroup$

To be a bit more formal: If I am choosing to disprove proposition $P$ is false, by exhibiting a counterexample, I would be proving.

"The proposition $P$ is false."

And the proof would start from

"If $P$, then for all integer (or whatever) $n$, $<$ some statement about $n$ that is implied by $P$ $>$". Therefore, in particular, for $n=$ my counterexample number, . This is a contradiction, so $P$ cannot be true.

In your simple example:

The proposition "The sum of any two integers is odd" is false.

Proof:

If the sum of any two integers is odd, then (w) for all integers $a,b$, $a+b$ is odd. Consider in particular $a=1, b=1$. In that case $a+b=2$ which is not odd. This contradicts (w), thus our assumption that the sum of two integers is odd must be false.

PS - I have heard of a strong mathematician who excludes proof by contradiction from his axioms of what constitutes a valid proof. But I suspect that disproof by presenting a counterexample is still valid to him. In my formulation that would not work so there must be a better one.

$\endgroup$
  • $\begingroup$ Look up intuitionistic logic. I'm not intuitionistic, but it's not accurate to portray intuitionism wrongly. It does not reject a disproof by showing that the assumed statement leads (intuitionistically) to a contradiction, which in this case it does. $\endgroup$ – user21820 Jul 8 '16 at 11:00
3
$\begingroup$

I would suggest trying to present your example in a different manner though mostly correct. I also recommend presenting it in a manner of using exact language to avoid ambiguity and variables so as to mathematically represent the statement and proceed to use a Proof by contradiction where a Counterexample would be used.

So to present your problem:

Theorem: The sum of two integers is odd

Lets present this mathematically and use an assumption have more specific language. Because we are only concerned about the most general case of all integers I will present it like this:

$a+b=c $

Assume true for all integers $\mathbb{Z}$

$a,b \in \mathbb{Z}$,

$c$ is an odd number

Let $a=1$, $b=1$ $\Longrightarrow$ $1+1=c$ $\Rightarrow$$c=2$

CONTRADICTION

Proceed to write a conclusion like this:

$\therefore$ the Theorem "The sum of two integers is odd" is not true for all $a,b \in \mathbb{Z}$

Hope this was helpful

$\endgroup$
2
$\begingroup$

If you want to be formal, one way would be to negate the assertion. The original statement claimed:

The sum of any two integers is odd.

More formally,

For all integers $x,y$, their sum $x+y$ is odd.

The negation of this is:

There exist integers $x,y$ whose sum is not odd.

Or if you prefer,

There exist integers $x,y$ whose sum is even.

The proof of this is simple:

The sum of the integers $x=y=1$ is $x+y=2$, which is even. $\qquad\square$

How would you actually write it? Here is one option.

Q: Prove or refute: the sum of any two integers is odd.

A: The claim is false: there exist two integers whose sum is even. For example, $1+1=2$.

$\endgroup$
0
$\begingroup$

In general terms you assume that $\forall x \in V : P(x)$. But you've found, say, an $n \in V$ for which $\neg P(n)$, (i.e. your counterexample), therefore you may conclude that $\exists n \in V : \neg P(n)$. Using de Morgan this is equivalent to $\neg(\forall n \in V: \neg \neg P(n))$, and therefore $\neg \forall n \in V: P(n)$. But this conclusion and the assumption with the modus ponens rule results in a falsum i.e. a contradiction. Hence the assumption is untenable, and therefore not true. Because of the tertium non datur (or "excluded middle") rule, we have to conclude that the negation of the assumption must be true.

This explains why a counterexample is effective to reject a -faulty- assumption and, at the same time how you would format the proof formally (no pun intended ;-).

$\endgroup$
0
$\begingroup$

If a sentence $\varphi$ is false, then $\neg \varphi$ is a theorem, and needs to be proven as such. So I'd write:

Proposition. There exist integers $a$ and $b$ such that $a+b$ isn't odd.

Proof. Define $a=1$ and $b=1$. We will show that $a+b$ isn't odd.

Observe that: $$a+b=1+1 =2.$$ But since $2$ isn't odd, hence $a+b$ isn't odd, as required.

$\endgroup$
0
$\begingroup$

I'd stay with your original layout, as it answers the question asked, not emphasising a true statement; just change the labels:

Proposition: the sum of two integers is odd

Counterexample:

1 + 1 = 2

Thus the sum of two integers may be even

$\endgroup$

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.