Why are all Canadians the same age?

Question

Canada is full of Canadians—about 34 million of them at present. What you may not have known is that all Canadians are the same age.

Don't believe me? I'll prove it to you.

Suppose there are exactly $n$ people in Canada, where $n$ is a whole number. An inductive proof of my claim is simple: we assume that any set of $n-1$ Canadians all have the same age, and prove that this implies any set of $n$ Canadians all have the same age.

To do this, we choose an arbitrary set of $n-1$ Canadians, and call this set $A$. Out of set $A$ we pick any two Canadians, which we label $C_1$ and $C_2$. It is understood that $C_1$ is not the same person as $C_2$.

Now we choose a second, different set of $n-1$ Canadians and call this set $B$.

Since set $A$ can only have one Canadian that set $B$ does not, we know that at least one of the following two conditions must hold:

1. $C_1$ is in both $A$ and $B$
2. $C_2$ is in both $A$ and $B$

Hence there is always at least one Canadian in both sets. Let us call this Canadian $C$.

By assumption, we know that everyone in set $A$ has the same age, which we will denote $a$. Because $C$ is in $A$, we know that $C$'s age is also $a$. We also know that (by assumption) everyone in set $B$ has the same age. And since $C$ is in set $B$, the age of everyone in set $B$ must be $a$.

Since everyone in our complete set of $n$ Canadians is contained in either $A$ or $B$, we conclude that everyone in the complete set has the same age, $a$.

Thus we've proved that if any set of $n-1$ Canadians have the same age, any set of $n$ Canadians have the same age.

Naturally, we can work backwards inductively from $n = {\rm 34\ million}$ all the way to $n = 1$. Start by assuming that every set of $33,999,999$ Canadians have the same age, and use our proof to show that all $34,000,000$ Canadians therefore have the same age. To prove that every set of $33,999,999$ Canadians have the same age, we assume that every set of $33,999,998$ Canadians have the same age and use our proof again, etc., etc., all the way back to $n = 1$.

For $n = 1$, a set of one Canadian is just one person. Hence, trivially we see that everyone in the set has the same age.

Thus we have proved by induction that every Canadian is the same age! :)

Now... you might be skeptical of my result.

But the brainteaser is: Where is the fallacy in my proof? Where is the error?

Puzzlers are politely encouraged to place answers in spoiler blocks to avoid inadvertently spoiling the fun for other readers. :)

Answer 1

This is the:

Horses Paradox

See here.

The problem is we make an implicit assumption that the two subsets of Canadians to which the induction assumption is applied have a common element. This is not true when the original set (prior to either removal) only contains two Canadians.

Answer 2

The fallacy is here:

Out of set A we pick any two Canadians, which we label C1 and C2. It is understood that C1 is not the same person as C2.. We cannot pick two elements out of set containing only one.

Answer 3

"Thus we've proved that if any set of $n−1$ Canadians have the same age, any set of $n$ Canadians have the same age." No, you've actually proven the opposite: if a set of $n$ Canadians have the same age, then any subset of $n−1$ Canadians have the same age. More precisely, you've proven that any $n-1$ subset is comprised of members the same age as members of any other $n-1$ subset. You've restricted yourself to subsets of size $n-1$, but it should be possible to extend the logic for subsets of any size.

My first thought was that you can't work backwards to size $n=1$, because your logic depends on having two sets of at least two people. However, you can work backwards to $n=2$ or $n=3$, and I'm pretty sure you can find a set of $2$ or $3$ people in Canada who do, in fact, have the same age.