A reflection on a wrong proof using induction.

Here is an counterexample which explains why the base case is so important for the proof.Sometimes it's hard to catch all the base cases which is required for continuing the induction part.

Statement:
f(x) = |x|: S N, S is any set. f(x) is the cardinality of set S.
Try to prove: n N, P(n) is true.
P(n) :  S {S| f(S)=n },
x, y S f(x) = f(y).

Now is the wrong proof which causes a ridiculous conclusion:
Prove by induction:
Base case:
For n = 1, |S| =1 , S = {x}, x,y S, x = y  f(x) = f(y).
Induction:
Assume for n = k, S that |S| = k, P(k) is true,
   Then for  x, y S f(x) = f(y).
   Then fix |S| = k +1, Assume x, y, z S. Let Sx = S\{x}, Sy = S\{y},
   Then |Sx| = |Sy| = k,
   Then for Sx, y and z Sx,
   Then y = z     # According to the assumption for n = k
   Then for Sy, x and z Sy,
   Then x = z     # According to the assumption for n = k
   Then x = z = y,
   Then x = y
   Then for n = k+1, P(n) is true,
   Then P(n = k) P(n = k+1)
Then for  n N,P(n) is true.

The  proof above is wrong!
The reason is, the induction assume the k >= 3, which means the base case has to contain the case when n = 3 at least.Thus, we should include it in the base case that n = 1,2 ,3. The tricky part is starting from the case n =2, P(n) is no longer true,neither is the case n = 3. So the base case for this proof fails itself, that's the key point why the induction proof fails, and that's why we can draw such a ridiculous result that for any set of any cardinality, every element in the set is the same with any of the rest elements.

A reflection of this proof is , sometimes tricky thing may happen like the statement may be true for the induction part, but it can fail at the base case. that's why the base case and induction part are both very important.