3 ms·

I am amused by the proof that all natural numbers are interesting. Sort the numbers into two lists, one of interesting numbers and the other of uninteresting n

I am amused by the proof that all natural numbers are interesting. Sort the numbers into two lists, one of interesting numbers and the other of uninteresting numbers. If there is a smallest uninteresting number, that number would be interesting and it would not be on the list. Therefore the list of unintersting numbers is empty.

pmiller2 17y ago
It's similar to the proof that all horses are the same color. Suppose we have $n$ horses. It suffices to show they are all the same color. We do so by induction on $n$. If $n=0$ or $n=1$, then, certainly all $n$ horses are the same color, so the base case holds. For the inductive hypothesis, assume we've shown that all the horses in any group of $n-1$ or fewer horses are the same color, and suppose we are faced with a group of $n$ horses. Choose some horse arbitrarily and remove it, leaving a group of $n-1$ horses for our consideration. By the induction hypothesis, these horses are all the same color. Replace the horse we removed and then remove a different horse from the group. Likewise, these horses are all the same color. This then implies that all $n$ horses are the same color. Since $n$ is arbitrary, this shows that all horses are the same color.
- Fizzley 17y ago
  Cute. I know it's a joke, but the inductive step fails for n = 2. Each of the two groups of 1 horses being the same colour does not imply that all the horses are the same colour. :)
  - pmiller2 17y ago
    Yeah, but it's still hella fun to throw at a class of undergrads on a Friday afternoon. :-)
Fizzley 17y ago
This is similar to the following question: Is there a positive integer that does not have an accurate semantic definition in english of less than 100 characters? (i.e. "The first number", "The first prime", "The third perfect square", etc.) Proof that there is no such number: Suppose there were. Construct a list of all the numbers that don't have an accurate english semantic definition in less than 100 characters. The first of these can be accurately defined as "The first number that does not have an accurate english semantic definition in less than 100 characters", a contradiction. :-P

pmiller2 17y ago

It's similar to the proof that all horses are the same color. Suppose we have $n$ horses. It suffices to show they are all the same color. We do so by induction on $n$. If $n=0$ or $n=1$, then, certainly all $n$ horses are the same color, so the base case holds. For the inductive hypothesis, assume we've shown that all the horses in any group of $n-1$ or fewer horses are the same color, and suppose we are faced with a group of $n$ horses. Choose some horse arbitrarily and remove it, leaving a group of $n-1$ horses for our consideration. By the induction hypothesis, these horses are all the same color. Replace the horse we removed and then remove a different horse from the group. Likewise, these horses are all the same color. This then implies that all $n$ horses are the same color. Since $n$ is arbitrary, this shows that all horses are the same color.

Fizzley 17y ago
Cute. I know it's a joke, but the inductive step fails for n = 2. Each of the two groups of 1 horses being the same colour does not imply that all the horses are the same colour. :)
- pmiller2 17y ago
  Yeah, but it's still hella fun to throw at a class of undergrads on a Friday afternoon. :-)

Fizzley 17y ago

This is similar to the following question: Is there a positive integer that does not have an accurate semantic definition in english of less than 100 characters? (i.e. "The first number", "The first prime", "The third perfect square", etc.) Proof that there is no such number: Suppose there were. Construct a list of all the numbers that don't have an accurate english semantic definition in less than 100 characters. The first of these can be accurately defined as "The first number that does not have an accurate english semantic definition in less than 100 characters", a contradiction. :-P