0

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.

user601846
  • 111
  • 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. – saulspatz Jan 17 '20 at 14:57
  • 5
    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$..." – JMoravitz Jan 17 '20 at 14:58
  • 1
    Is it not easier to provide the bijection $\phi(n)=2n+1$ between $\mathbb{Z}$ and the odd integers? – Peter Foreman Jan 17 '20 at 14:58
  • Why not using that $2n+1$ is odd for every integer $n$ ? – Peter Jan 17 '20 at 14:58
  • @Peter, I second this. – Mourad Jan 17 '20 at 15:00
  • @saulspatz it glossed over the fact that we know that the sum of an odd number of positive odd numbers is an odd number larger at least as large as any element in the set, and the sum of an even number of positive odd numbers is an even number at least as large as any number in the set, so I could agree that it is not well worded or detailed enough, but I don't see it as being totally incorrect... just unnecessary. The parity of $|S|$ is relevant to the OP's proof as it determines the parity of the sum of elements of $S$. – JMoravitz Jan 17 '20 at 15:00
  • @JMoravitz I thought the same thing at first, but it doesn't say "positive" in the problem statement, so I think an explicit argument would be necessary. – saulspatz Jan 17 '20 at 15:02
  • By proving that the set of positive odd integers is infinite, and recognizing that the set of positive odd integers is a subset of the set of all odd integers, that directly implies the set of all odd integers is also infinite. Again, glossed over details, but not explicitly wrong... – JMoravitz Jan 17 '20 at 15:03
  • Thanks all, I just learned of Euclid's proof of infinitely many prime numbers and was thinking of results that could be obtained using a similar method. You're definitely right that it's overly complex. – user601846 Jan 17 '20 at 15:03
  • 1
    @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. – Peter Foreman Jan 17 '20 at 15:06

1 Answers1

2

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.

gandalf61
  • 15,326