Prove that the set of odd natural numbers is infinite by the Pigeonhole Principle.

Question

Only natural numbers can be used, meaning 0 cannot be used. Subtraction also can't be used. Proving that $f(n)=2n-1$ is bijective would work, only that it would require 0 and subtraction. These restrictions are difficult but I want to see a Pigeonhole proof to this. Thanks in advance.

Answer 1

You could prove that the map $n\mapsto 2n+3$ defined on odd natural numbers is injective but not surjective.

According to the Pigeonhole Principle injective functions $f:S\to S$ are surjective if $S$ is finite.

Answer 2

Suppose the odd integers are finite in number - say there are $N$ of them. If we have pigeonholes $1,2, \dots N$ and put the odd number $2r-1$ in the $r^{th}$ pigeonhole, then the odd number $2N+1$ hasn't got a place to go.

But this is not really a pigeonhole problem, in that the argument has to be contrived, rather than arguing straightforwardly.

Answer 3

=======

Redo.

1) There are an infinite number of natural numbers.

Pf: Assume there were a finite number. Let the number $k$ be a "pigeon" and let $k+1$ be a "hole". There is no $k + 1 = 1; k \in \mathbb N$ so we have more pigeons than holes. So two or more pigeons occupy the same hole. i.e. there exist $j \ne k$ but $j + 1 = k+1$. This is a wrong. So we have a contradiction.

A) All natural number are either even or odd. Those are mutually exclusive and exhaustive. That's simply a definition. $\mathbb N = \mathbb O \cup \mathbb E$.

2) The union of two finite sets is finite.

Pf: Well, okay... pair up each element of set $A$ with an element of set $B$ and call that pair a "hole", and take two elements of some infinite set $U$ and call those two elements a "pigeon". Eventually we will run out of elements of either set $A$ or set $B$ as they are finite but we won't run out of pairs of elements of $U$ because $U$ is infinite. If one of the sets $A$ or $B$ is larger continue taking "holes" from the larger and match them to a single element ("pigeon") of $U$. We'll eventually run out of "holes" but not pigeons. So $A \cup B$ can not be injected into $U$ so $A \cup B$ is not infinite.

B) So there either there are an infinite number of evens or an infinite number of odds or both.

3) For any natural number $k$ the numbers $k$ and $k+1$ are different parities.

If $k$ is even then $k = 2m$ where $m$ is an integer, so $k + 1 = 2m + 1 = 2(m + \frac 12)$ and $m + \frac 12$ is not an integer so $k + 1$ is not even, hence odd.

If $k$ is $1$ then $k+1 = 2$ is even.

If $k$ is odd and $k > 1$ then $k \ge 2$ but as $2$ is even $k \ne 2$ so $k > 2$. Let $2m$ be the largest even number so that $2m < k$. Then $k = 2m + j$ and $k = 2(m + \frac j2)$ and none of $m + \frac 12,.... m + \frac j2$ are integers. But $m + \frac 22$ is an integer so $0 < j < 2$. So $j = 1$. So $k = 2m + 1$. And $k + 1 = 2m + 2 = 2(m + 1)$ is even.

So

C) If we assign the evens to be "holes" every "hole", $k $ will have an odd "pigeon", $k+1$, so there are least as many odd pigeons as there are even holes. So either there are finitely many evens and therefore infinitely many odds. Or there are infinitely many evens and at least infinitely many odds.

So... either way there are infinitely many odds.

And that was a really .... odd ... proof.

==== old answer below ======

Use the injection $2n+1$ to prove there are infinite number of odds equal to $3$ or more. If there are an infinite number of odds with a restriction, there will be an infinite number of odds without the restriction (as there can't be fewer without the restriction).

Pigeon hole seems a weird way of putting it but.... For every even number $k$ then $k + 2$ is the next even number. So there is no last even number so there are an infinite number of them. For every even number $k$, the very next even number will be $k + 2$. But between every $k$ and $k+2$ there is an intermediary number $k+1$. This number can not be even. So by the pigeon hole principal it is odd.

But I don't like that. It's inefficient and unnecessary and, probably, somewhat circular.

==== in response to a comment =====

If the purpose of this is to provide a simple proof and not to hone our theoretical chops the easiest must straightforward and sensible proof is to simply prove:

$f: \mathbb N \to \mathbb O$ via $f(n) = 2n-1 $ is an injection.

You can use subtraction as long so $a - b \ge 1$. That will be the case and is part of the proof of $\mathbb O$ being the image of $f(\mathbb N)$.

Pf:

1) $f(\mathbb N) \subset \mathbb O$. Pf: $n \in N \implies n \ge 1 \implies 2n - 1 \ge 1; 2n - 1 \in \mathbb Z$ so $f(\mathbb N) \subset \mathbb N$. $f(n) = 2n-1 = 2(n-\frac 12)$. $n - \frac 12$ is not an integer so $f(n)$ is not evven. SO $f(n)$ is an odd natural number. So $f(\mathbb N) \subset \mathbb O$.

2) $f$ is injective. $f(n) = f(m) \iff 2n - 1 = 2m - 1\iff n=m$

3) $f$ is surjective. $m \in \mathbb 0$ means $m \ne 2k$ for any integer $k$. $m < 2m$ so there exists an even number larger than $m$. Let $m < 2j$ where $j$ is the smallest even number larger than $m$. $2j - 2$ is even (or non-exisitent and $2j = 2$) so $2j -2 < m < 2j$ (or $m < 2$). So $m = 2j -1=f(j)$ (or $m = 1 = 2*1 -1=f(1)$).

Answer 4

A set $A$ is infinite if and only there exists a bijection $f : A \rightarrow B$, where $B$ is a proper subset of $A$.

The function

$$f(n) = 2n + 1$$

is such a bijection, where $A$ is the set of odd numbers and $B = \{ 2n + 1 \mid n \in \mathbb{N}, n\; \text{odd} \}$.

Clearly $B \subsetneq A$, and we immediately see that $f$ is a bijection since $f$ is strictly increasing.