# Fallacious Induction Proof that All Integers are Equal [duplicate]

We're currently learning about induction in my real analysis course. I came up with the following proof that is obviously false but cannot quite figure out why it fails. Here it is...

"Any set $S$ of $n \in \mathbb{N}$ integers are equal."

Proof: For $n = 1$, we only have a single integer in $S$, and thus it is equal to itself. Assume our statement is true for $n$ integers. Now consider any set of $n + 1$ integers. Without loss of generality they are integers $\left\{ 1, 2, \dots, n, n + 1\right\}$. Consider the sets $\left\{ 1, 2, \dots, n \right\}$ and $\left\{ 2, 3, \dots, n + 1\right\}$. Each of these two sets have only $n$ integers, so they are all equal. But this means $1 = 2 = 3 = \cdots = n = n + 1$, so all integers are equal.

-

## marked as duplicate by apnorton, Stefan Hamcke, Davide Giraudo, user127.0.0.1, M TurgeonJan 26 '14 at 21:54

I feel like this should be identical to the induction problem about horses with the same color... (An idea) –  apnorton Jan 26 '14 at 21:22
The induction step doesn't work for $n=2$ because there are no overlapping sets. But this question has been asked before on MSE several times, with horses of the same color as @anorton wrote. –  Stefan Hamcke Jan 26 '14 at 21:22

Your induction step only works if $n$ is at least $2$. Indeed,you have a problem when assuming the statement for sets of size $1$ and going to size $2$, because when $\{1\}$ and $\{2\}$ only take one value, you cannot conclude that $\{1,2\}$ only takes one value.
If you have two sets $A$, $B$ such that all elements of $A$ are equal and all elements of $B$ are equal, you can conclude that all elements of $A\cup B$ are equal only if you know that $A\cap B\ne\emptyset$. To complete the proof, you must show that this needed condition hold for the case $A=\{1,\ldots, n\}$, and $B=\{2,\ldots,n+1\}$ where you want to apply the conclusion. But it is not true for all $n$ that $\{1,\ldots, n\}\cap \{2,\ldots, n+1\}$ is nonempty. Therefore the proof fails.