0
$\begingroup$

Is this a valid proof of infinitely many odd integers?

Assume, to the contrary, that there are finitely many odd integers.

Let $S$ be the set of all positive odd integers and let $x=\sum_{n\in S} n$.

Then, $|S|$ is even or $|S|$ is odd.

Let $|S|$ be odd.

Then, $x$ is an odd integer. Let $y=x+2$. Then, $y$ is a positive odd integer not contained in $S$, which is a contradiction.

Let $|S|$ be even.

Then, $x$ is an even integer. Let $y=x+1$. Then, $y$ is a positive odd integer not contained in $S$, which is a contradiction.

$\endgroup$
10
  • $\begingroup$ Sorry, it's not correct. The cardinality of $S$ has nothing to do with this. There's no need for anything elaborate. Just let $x$ be the largest odd integer. $\endgroup$
    – saulspatz
    Jan 17, 2020 at 14:57
  • 5
    $\begingroup$ It is not wrong per se, but it seems horribly unnecessary. You could have just said, "Suppose to the contrary that $S$ were finite. We know that any finite set has a maximum element, so just let $x$ be the maximum of $S$ rather than the sum of $S$. Then looking at $x+2$ you have yourself an odd number larger than any other element of $S$..." $\endgroup$
    – JMoravitz
    Jan 17, 2020 at 14:58
  • 1
    $\begingroup$ Is it not easier to provide the bijection $\phi(n)=2n+1$ between $\mathbb{Z}$ and the odd integers? $\endgroup$ Jan 17, 2020 at 14:58
  • $\begingroup$ Why not using that $2n+1$ is odd for every integer $n$ ? $\endgroup$
    – Peter
    Jan 17, 2020 at 14:58
  • 1
    $\begingroup$ @user601846 If you want something resembling Euclid's proof you could have used the product of the elements of $S$ and added $2$ which always produces a new odd number. $\endgroup$ Jan 17, 2020 at 15:06

1 Answer 1

2
$\begingroup$

Yes, it is a valid proof but I think it is over complicated.

If $S$ is finite then $S$ has a largest member $z$ such that $z \ge x \space \forall x \in S$. Since $z$ is odd then $z' = z+2$ is also odd. But $z \not \ge z' \Rightarrow z' \not \in S$. So we have found a positive odd integer that is not in S. This contradicts the assertion that $S$ is the set of all positive odd integers.

Edit: This is the same as the proof that @JMoravitz outlined in comments above.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .