Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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.

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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.

Remark that it is true that under the assumption that any set of two integers are equal, then all integers are equal. (the word "set" is a bit problematic in this context, "sequence" would be better, because sets merge equal elements).

share|cite|improve this answer

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.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.