# Proove: the sum of two even numbers is even

• March 29th 2009, 06:58 AM
bmp05
Proove: the sum of two even numbers is even
$E:= \{m: 2m, m \in \mathbb{N}\}$

$U:= \{n: 2n+1, n \in \mathbb{N}\}$

assume $E_1+E_2=U$

$\Rightarrow 2m_1+2m_2=2n+1$

$\Rightarrow 2m_1+2m_2-1=2n$

$\Rightarrow \nexists m \in \mathbb{N}: 2\mid(2m_1+2m_2-1)$

This contradicts the assumption, therefore E_1 + E_2 = E_3
• March 29th 2009, 11:51 AM
HallsofIvy
Isn't 2m+ 2n= 2(m+n) simpler?
• March 29th 2009, 11:53 AM
Hello bmp05
Quote:

Originally Posted by bmp05
$E:= \{m: 2m, m \in \mathbb{N}\}$

$U:= \{n: 2n+1, n \in \mathbb{N}\}$

assume $E_1+E_2=U$

$\Rightarrow 2m_1+2m_2=2n+1$

$\Rightarrow 2m_1+2m_2-1=2n$

$\Rightarrow \nexists m \in \mathbb{N}: 2\mid(2m_1+2m_2-1)$

This contradicts the assumption, therefore E_1 + E_2 = E_3

Are you required to prove this by contradiction? The direct proof is very straightforward. We define an even number in the obvious way: $n$ is even $\iff \exists \,m \in \mathbb{N}, n = 2m$.

Then $n_1$ is even and $n_2$ is even $\Rightarrow \exists \,m_1, m_2 \in \mathbb{N}, (n_1 = 2m_1) \wedge (n_2 = 2m_2)$

$\Rightarrow n_1 + n_2 = 2m_1 + 2m_2 = 2(m_1+m_2)$

$\Rightarrow n_1 + n_2$ is even

If you're going to use a 'contradiction' method, I think you have to be a little more careful with your use of notation. The definition of your sets should be

$E = \{m:m=2n, n \in \mathbb{N}\}$

$U = \{m:m=2n+1, n \in \mathbb{N}\}$

Assume $\exists\,m_1, m_2 \in E, m_1 + m_2 =m_3, m_3\in U$

Then $\exists\, n_1, n_2,n_3\in \mathbb{N},m_1=2n_1, m_2 = 2n_2, m_3 = 2n_3+1$

$\Rightarrow 2n_1+2n_2 = 2n_3+1$

$\Rightarrow 2(n_1+n_2 -n_3)=1$

$\Rightarrow 2 |1$. Contradiction.

• March 29th 2009, 12:21 PM
bmp05
Thanks grandad! I was trying to follow your last example as well, btw. I read that you should be careful to not neglect the direct proof, because it is easier if possible, but then I have hardly ever seen it used.(Clapping)
• March 29th 2009, 01:05 PM
bmp05
And now to prove uneven.even = even

$n$ is even $\iff \exists \,m \in \mathbb{N}, n = 2m$.
$i$ is uneven $\iff \exists \,m \in \mathbb{N}, i = 2m+1$.

Then $n$ is even and $i$ is uneven $\Rightarrow \exists \,m_1, m_2 \in \mathbb{N}, (n = 2m_1) \wedge (i = 2m_2+1)$

$\Rightarrow n.i = 2m_1 . (2m_2+1) = 2m_1.2m_2+2m_1 = 2.m_1(m_2+1)$

$\Rightarrow n.i$ is even

Is this a trivial case, because you prove that $2 \mid P(n)$ but $P(n) is 2m.n$ using the definition of an even number? (But that's the same for adding two even numbers as well...)
• March 29th 2009, 10:31 PM
Hello bmp05
Quote:

Originally Posted by bmp05
And now to prove uneven.even = even

$n$ is even $\iff \exists \,m \in \mathbb{N}, n = 2m$.
$i$ is uneven $\iff \exists \,m \in \mathbb{N}, i = 2m+1$.

Then $n$ is even and $i$ is uneven $\Rightarrow \exists \,m_1, m_2 \in \mathbb{N}, (n = 2m_1) \wedge (i = 2m_2+1)$

$\Rightarrow n.i = 2m_1 . (2m_2+1) = 2m_1.2m_2+2m_1 = \color{red}2.m_1(m_2+1)$

$\Rightarrow n.i$ is even

Is this a trivial case, because you prove that $2 \mid P(n)$ but $P(n) is 2m.n$ using the definition of an even number? (But that's the same for adding two even numbers as well...)

Well done. You've got this pretty well complete, except for the bit I've marked in red, where you've just gone back to the original expression.

I agree, it does look more or less trivial, but what you should have said is

$\Rightarrow n.i = 2m_1 . (2m_2+1) = 2 \color{red}\times (2m_1m_2+m_1)$

which is now in the format $2 \color{red}\times p\color{black}, p\in \mathbb{N}$

So that you can now say:

$\Rightarrow n.i$ is even

using the $\color{red}\Leftarrow$ part of the definition that $n$ is even $\color{red}\iff\color{black} \exists \,m \in \mathbb{N}, n = 2m$

Do you understand this subtle, but important, point?

• March 30th 2009, 12:23 AM
bmp05
Yes- thanks again, I realised that I needed to show something analogue to the definition of the even number, but I can see that it is much clearer to substitute of the natural numbers $(m_1.m_2+m_1)$ as opposed to $m_1(m_2+1)$. But the most important thing missing from the proof is this substitution of an equivalent natural number p.
This reminds me of another probelm that I'm having proving the distributive laws in set theory- it is somehow simple, but hard to express in the right way!

Proove $\forall k \in \mathbb{Z}: 3 \mid k \Leftrightarrow 3 \mid k^2$

$\equiv (3 \mid k \Rightarrow 3 \mid k^2) \wedge (3 \mid k^2 \Rightarrow 3 \mid k)$

Part1: $3 \mid k \Rightarrow 3 \mid k^2$

$3 \mid k \Leftrightarrow k = 3.l,$ $k,l \in \mathbb{Z}$

$\Rightarrow k^2 = (3.l)^2 = 3.(3.l^2)$

$\exists p \in \mathbb{Z}: p = (3.l^2)$

$\Rightarrow 3.(3.l^2) = 3.p$

$\Rightarrow 3 \mid k \Rightarrow 3 \mid k^2$

Part2: $3 \mid k^2 \Rightarrow 3 \mid k$

$3 \mid k^2 \Leftrightarrow k^2=3.l,$ $k,l \in \mathbb{Z}$

$3 \mid k \Leftrightarrow k = 3.m, k,m \in \mathbb{Z}$

$\exists m \in \mathbb{Z} : m=l$

$\Rightarrow 3.l \Rightarrow 3.m$

$3 \mid k^2 \Rightarrow 3 \mid k$

It follows that, $(3 \mid k \Rightarrow 3 \mid k^2) \wedge (3 \mid k^2 \Rightarrow 3 \mid k)$

$\forall k \in \mathbb{Z}: 3 \mid k \Leftrightarrow 3 \mid k^2$

Unfortunately, it's not very clear to read.
• March 30th 2009, 05:30 AM
Hello bmp05
Quote:

Part1: $3 \mid k \Rightarrow 3 \mid k^2$

$3 \mid k \Leftrightarrow k = 3.l,$ $k,l \in \mathbb{Z}$

$\Rightarrow k^2 = (3.l)^2 = 3.(3.l^2)$

$\exists p \in \mathbb{Z}: p = (3.l^2)$

$\Rightarrow 3.(3.l^2) = 3.p$

$\Rightarrow 3 \mid k \Rightarrow 3 \mid k^2$
Part 1 of your proof is fine.
Quote:

Part2: $3 \mid k^2 \Rightarrow 3 \mid k$

$3 \mid k^2 \Leftrightarrow k^2=3.l,$ $k,l \in \mathbb{Z}$

$3 \mid k \Leftrightarrow k = 3.m, k,m \in \mathbb{Z}$

$\exists m \in \mathbb{Z} : m=l$

$\Rightarrow 3.l \Rightarrow 3.m$

$3 \mid k^2 \Rightarrow 3 \mid k$
This is not so good. One way to check to see if it makes sense is this: $p|k^2 \Rightarrow p|k$ only works if $p$ is a prime number, or a product of single powers of prime numbers. (For instance, $3|36 \Rightarrow 3|6$ is OK, but $4|36 \Rightarrow 4|6$ isn't.) But you haven't used the fact anywhere in your proof that 3 is a prime.

You need to use the Fundamental Theorem of Arithmetic and say that if
$k=\prod p_i^{r_i}$, where the $p_i$ are primes, then $k^2=\prod p_i^{r_i}\times\prod p_i^{r_i}=\prod p_i^{2r_i}$. So $3|k^2 \Rightarrow 3 = p_i$, for some $i$, and therefore $3 | k$.

• March 31st 2009, 12:26 PM
bmp05
I'm not sure about the Fundamental Theorem of Arithmetic, I had a look at the wikipedia page and it looks interesting, but the course is moving very quickly, unfortunately and although I can't write very good proofs yet, we have already moved onto fields (help!)- anyway, I thought of a good idea for this problem, but I'm not sure how to proove it.
The idea is that $\forall k \in \mathbb{Z},~k = 3m,~3m+1,~3m+2, ~m \in \mathbb{Z}$
This would mean that I can jump straight into the $3 | k^2 \Rightarrow 3 | k$ proof, because $k^2$ can only ever equal one of the 3 possibilities above. But the proof becomes something like:

$\forall k \in \mathbb{Z},~(k=3m)~\vee~(k=3m+1)~\vee~(k=3m+2)$, so I would like to say something like:

Proof by contraditiction, suppose $k = 3m+1~~or~~k = 3m+2$

$\Rightarrow k^2~= (3m+1)^2~~or~~(3m+2)^2$

$\Rightarrow k^2~=(9m^2 + 6m + 1)~~or~~(9m^2 + 12m + 4)$

$\Rightarrow 3 \mid (9m^2 + 6m + 1)~~or~~3 \mid (9m^2 + 12m + 4)$

[Errr... well, I- this seems to be true, but I don't know how to...?]

$\Rightarrow (9m^2 + 6m + 1) = 3 . n,~~\exists~n \in \mathbb{Z}$

$\Rightarrow 3m^2 + 2m + \frac{1}{3} = n$

[... do the same for the other or]

This is a contradiction, therefore $3 \mid k^2 \Leftrightarrow 3 \mid k$

Well, this is a terrible proof, but on the good side, if done correctly this would actually be an "if and only if" proof! (?)
• April 1st 2009, 12:54 AM
Hello bmp05

Well done. I think this is pretty well OK. I should just change the last part a bit (the part where you weren't so sure) so that instead of:
Quote:

Originally Posted by bmp05
$\Rightarrow (9m^2 + 6m + 1) = 3 . n,~~\exists~n \in \mathbb{Z}$

$\Rightarrow 3m^2 + 2m + \frac{1}{3} = n$

This is a contradiction, therefore $3 \mid k^2 \Leftrightarrow 3 \mid k$

I think I'd factorise the right-hand sides, and say:

$3 \mid (9m^2 + 6m + 1)~~or~~3 \mid (9m^2 + 12m + 4)$

$\Rightarrow 3 \mid 3(3m^2 + 2m) + 1~~or~~3\mid 3(3m^2 + 4m + 1) + 1$

Contradiction, since $3(3m^2 + 2m) + 1$ and $3(3m^2 + 4m + 1) + 1$ both leave remainder $1$ when divided by $3$.