Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
I would say something along the lines of:
The proposed result is false. Here is a counterexample...
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$
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.
Cite the counterexample. Since $1 + 1 = 2$, the sum of two arbitrary integers is not always odd.
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$.
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.
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).
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 .......
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.
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
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$.
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 ;-).
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.
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
