Think of a city, say the capital of Germany, Berlin. Now I can easily come up with another city, like San Fransisco. Now with two cities in mind, I can still come up with another city (Stockholm, for example). By induction there should be infinite many cities because I can clearly come up with yet another city no matter how many cities I have thought about.
This is obviously wrong. What exactly am I doing wrong here?
For induction you need to define a rule of how to go from n to n+1. You fail to define a rule of how to go from {Germany, Berlin} to {Germany, Berlin, San Fransisco}.
The rule could be: Add San Fransisco to the set. Of course you can't use that rule to prove that there's an infinitive amount of cities.
Your rule could be: Add a city that's not already in the list. That rule presupposes that there always a city that's not on the list. Basically you would assume what you want to prove.
Your inductive step is
Given a list of cities, I can always give a new city that is not on the list.
and I would say this is false. It is just not true that one
can clearly come up with yet another city no matter how many cities I have thought about.
As this premise is false the induction does not give a the correct answer (though the argument itself is valid).
Your question is related to the widely known problem of induction. But this case is less problematic because one can actually list all cities and see that the list is indeed finite. If the task was to show that it is infinite it would be a different matter.
Your induction draws from a set of city names. However, you have failed to show a proof that there is an infinite number of city names (and that all those cities exist).
This is like saying...
Another way to look at it, your argument is circular. Your inductive proof that there is an infinite set of cities assumes there is an infinite set of cities to draw from.
The "axiom of induction" regarding numbers says that :
for every property P of numbers, if P holds for 0 and for every number n, if P holds for n, then P holds also for n+1 (the "number after n"), then P will hold for every number.
This axiom of induction exploit the "structure" of the set of natural numbers : there is a first one, and they have an "order" which, for every numbers gives us the "next one".
Per se, induction does not implies the infinity of numbers.
The infinity of them is licensed by other axiom; in detail, by the axiom which states that there is a number (usually 0) which is not the "next one" of any number and by the axiom which states that there are no two different numbers which has the same "next one".
In your case, the "collection" of all cities does not have the structure of natural numbers (a first one, and an "order" that for every numbers gives us the "next one"); thus, we have no reason to assume that there exist an infinite number of cities.
Your assumption that given a list of cities you can always find one more city, is false. In fact at some point you will have a list of cities, but you will not be able to name one more city.
This is how mathematical induction works:
You show that a statement is true for N = 1. Then you show that for every N ≥ 1: If the statement is true for N, then it is true for N + 1. It follows that the statement is true for all N.
In this case the statement is: There are at least N cities. You showed the statement for N = 1 (by quoting Berlin, Germany). You showed the induction step (if the statement is true for N, then it is true for N + 1) for N = 1 (San Francisco) and for N = 2 (Stockholm).
You didn't give the slightest bit of evidence that the induction step would be true for every N. Therefore you gave no evidence that there is an infinite number of cities.
