1

Prove that there is an infinite number of even numbers:

Assume there is a largest even number, $E$.

$E + 2$ would also be even, as $E$ must be divisible by 2, so $E + 2$ is divisible by $2$, and clearly greater than $E$.

If $E$ is the largest even number, then $-E$ is the largest negative even number.

$-E - 2$ would also be even, as $-E$ must be divisible by 2, so $-E - 2$ is divisible by $2$, and clearly -E - 2 is a greater negative even number than E

Therefore, this contradicts the original assumption, so it must be incorrect.

Therefore, there is an infinite number of even numbers.

Is this proof sufficient, or is something missing? As the textbook's answer was much longer.

EDIT: Textbook's answer is: Suppose that there is a finte number N of even numbers

This finite list can be ordered so that E1 < E2 < E3 < ...

Then the largest even number is En

But 2En would also be even and clearly greater than En, so is not in the list.

Therefore, there are more than N even numbers.

This contradicts the initial proposition.

Therefore, there are infinitely many even numbers

  • 1
    The existence of a largest even number does not contradict the assumption of an infinite number of even numbers. You need something else (not much, but you do need it). – Brian Tung Mar 13 '19 at 19:53
  • 1
    $E=0$ is even, yet $2E=0$ is not greater than $E$. Worse, $E=-2$ is even, but $2E=-4$ is less than $E$. Try $E+2$ instead of $2E$. – lisyarus Mar 13 '19 at 19:54
  • @BrianTung But non-existence of a largest even number (together with existence of at least one even number) is sufficient for infiniteness. – lisyarus Mar 13 '19 at 19:55
  • EDIT: Does my new application of E + 2 instead of E make the proof sufficient? –  Mar 13 '19 at 19:57
  • @lisyarus: There is no largest odd even number. That doesn't prove there's an infinite number of odd even numbers. – Brian Tung Mar 13 '19 at 19:57
  • Just a general point: if you want to prove there are infinitely many of something, you need to know what you mean by that. "No largest example" actually isn't enough; it depends on the order type of that set of objects. You would something like the current answer's strategy, wherein we clarify, "by infinite I mean it or a subset thereof binders with the integers" (actually, either positive or non-negative integers would be OK too). – J.G. Mar 13 '19 at 19:58
  • @BrianTung Sure, that's why I added "together with existence of at least one even number". There does not exist an odd even number, that's where the argument fails. – lisyarus Mar 13 '19 at 19:59
  • I'd personally like to see more details as to why if $E$ is even then $E + 2$ is also even (but that is the way to go). – fleablood Mar 13 '19 at 19:59
  • @lisyarus: I hadn't seen that when I made my response. – Brian Tung Mar 13 '19 at 20:02
  • @J.G. Are you sure you didn't confuse "isn't enough" with "isn't necessary"? As soon as the order is linear, non-existence of largest and non-emptiness suffice to prove infiniteness (but are certainly not required for this), since any finite set does have a largest element. – lisyarus Mar 13 '19 at 20:02
  • Alternative approach. There are an infinite number of integers, $n$ (that's a given, right?). If $m \ne n$ then $2m \ne 2n$ so as there are an infinite number of $n$ there are an infinite number of $2n$. – fleablood Mar 13 '19 at 20:03
  • @BrianTung I've added it a few seconds after writing the original comment, as soon as realized the possible flaw. I'm sorry if it lead to confusion! – lisyarus Mar 13 '19 at 20:03
  • The text answer leaves out an essential step: $E_n \ge 2 > 0$ so $2E_n > E_n$. If $E_n \le 0$ then $2E_n \le E_n$. You must state and explain why $E_n > 0$. – fleablood Mar 13 '19 at 20:06
  • So could you use the E + 2 shows there is an even number greater than E (if E is assumed to be the greatest even number). And use -E as the greatest negative even number and then use E - 2 instead. And then conclude there's been a contradiction? –  Mar 13 '19 at 20:14
  • Okay, is the proof sufficient now? As I've taken into consideration positive and negative even numbers. –  Mar 13 '19 at 20:40
  • @J.G.: Sorry, I'm not sure what comment of mine you're responding to, but I wasn't responding to you; I was responding to lisyarus. – Brian Tung Mar 13 '19 at 20:45
  • @lisyarus I know what I meant. It's neither necessary nor sufficient. It's not sufficient because a finite set can have an ordering that loops back round. Consider a simpler example: $\Bbb Z/10\Bbb Z$ is finite but, like $\Bbb Z$, is closed under $x\mapsto x+1$. – J.G. Mar 13 '19 at 20:55
  • 1
    @J.G. An ordering that "loops back round" is not an ordering: it fails to satisfy the axioms of an order relation. – lisyarus Mar 13 '19 at 21:08
  • @lisyarus Depending on the definition, yes; but a "local" inequality could easily mislead someone with this sort of proof. – J.G. Mar 13 '19 at 21:11

3 Answers3

1

Consider mapping even numbers to odd numbers. $$\varphi : A\to B\quad:\quad2n\mapsto2n-1$$ where $A$ is the set of even numbers and $B$ is the set of odd numbers.

This will give you a bijection. As $\mathbb{N}=A\cup B$ shows the set of natural numbers $\mathbb{N}$ is finite giving you a contradiction.

$\Big($ Assuming you can show every even and odd number is of the form $2n$ and $2n-1$ for $n\in\mathbb{N}$ respectively. $\Big)$

Yadati Kiran
  • 2,320
0

The cardinality of the set $2\Bbb Z$ equals the cardinality of the set $\Bbb Z$. We can consider the map $x\mapsto 2x$ from $\Bbb Z\rightarrow 2\Bbb Z$. Since we know that $|\Bbb Z|=\infty$, we also know that $|2\Bbb Z|=\infty$.

Dietrich Burde
  • 130,978
  • 1
    This starts from a theorem (and indeed a concept, cardinality) that the OP almost certainly is not yet up to in the class presenting this problem. – Mark Fischler Mar 13 '19 at 19:57
  • Countable infinite Cardinality is not more difficult than divisibility, I think. Students should be up to both in fact. – Dietrich Burde Mar 13 '19 at 20:04
  • 1
    I can confirm I'm not even at university so have no idea what countable infinite cardinality means. Plus, such an answer I don't think would be accepted by the specification as there is a clear push towards using a similar method to what I've used. We only learnt proof by contradiction today. –  Mar 13 '19 at 20:06
  • 1
    @SamConnell I understand you. Still, sometimes I think, this is not what it's about for you. It should be fascinating to see new ideas and a bit boring only to follow the "specification" and the "clear push" etc. And this site is an opportunity for this. Otherwise you can just copy the answer from some book or someone. – Dietrich Burde Mar 13 '19 at 20:18
  • @DietrichBurde I love maths and i'm studying it further at university but it just seems if there is a simpler proof or an easy way to correct my proof I'd prefer that to a different and more advanced proof. –  Mar 13 '19 at 20:32
  • 1
    To be fair, I don't think anyone can actually prove this statement without knowing what the OPs definition of "infinite" is. Sam Connell: It's not the proofs that are simple or good or bad or complicated. It's what definitions you are using and how precise they need to be. The two "obvious" reasons there are an infinite number of primes are 1) If there were a finite number thered be a largest one and you can just add 2 and 2) there's an infinite number of integers and every number can be doubled to get an even number. What matters is that is precise for your level. – fleablood Mar 13 '19 at 23:03
  • @fleablood I voted +1 because the point that we were not given the operative definition of "infinite" did make the answers more like opinion than logic. Plus your name is awesome. – Mark Fischler Mar 14 '19 at 06:04
0

To answer this question we need a definition of "finite" and "infinite".

"Not having a largest element" isn't a good definition. Take the set: $\{$ all the rational numbers that are equal or greater than $0$ and equal or less than $1\}$. It does have a largest element-- $1$-- but it is not finite.

Also $0, -1, -2, -3,.....$ has a largest element: $0$.

What the textbook is doing is something subtler. I'm not sure the exact wording, but it is probably something like this. A set is finite if there is a set of natural numbers $1$ through $n$ so that each number corresponds to precisely one element of the set. In other words you can list them in some order and there will be a first, second, and so on and there will be a last item.

And if that is impossible, then then set is infinite.

What the book is doing is subtle. It is saying: If we take a list of elements in some order so that there is a last element, I can show that the list is not completely. That means such a list can not exist. And so the set is infinite.

And that is why you can say: If the numbers were even we could list them in order from smallest to largest. The largest and last item on the list would be some even number $E$. If we add $2$ to $E$ to get $E+2$ that number is even and larger than the largest on the list. So it isn't on the list. So it is impossible make such a list. So there are an infinite number of even integers.

My only complaint would be, I'd like an explanation why $E + 2$ is even. (You could say. $E$ is even so there is some integer $N$ so that $E = 2N$ so $E +2 = 2N + 2 = 2(N+1)$. So $E+2$ is $2$ times the integer $N+1$. So $E$ is even.)

The textbook did something similar but it used the direct definition of even. It said if there were a finite number of even integers we could list them in order from smallest to largest. There'd be a largest $E$. Then $2E$ would be even. And $2E$ would be larger than the largest and not on the list. So a list is impossible.

My complaint with that is the book assumed $2E > E$. That would not be the case if $E \le 0$. The book, I think, should point out that $2$ is an even number so $E \ge 2 > 0$ so $2E > E$.

fleablood
  • 124,253