|
|
Re: Cantor's diagonal argument.
Posted:
Oct 5, 2001 12:26 PM
|
|
In article <c645a590.0110050703.2790bd1c@posting.google.com>,
Giles Redgrave <g.d.redgrave@elostirion.freeserve.co.uk> wrote:
>dseaman@seaman.cc.purdue.edu (Dave Seaman) wrote in message news:<9php6j$bkl@seaman.cc.purdue.edu>...
>> No, the correct argument is
>> 1. 1 is finite.
>> 2. For each n, if n is finite, then n+1 is finite.
>> 3. Therefore, each natural number is finite.
>> The conclusion is a statement about each natural number, not about the
>> set of all natural numbers. That is how induction works.
>Why can't you apply the same inductive argument to sets of natural
>numbers.
>1. A_1 has a finite number of elements
>2. For each n, if A_n has a finite number of elements, then A_{n+1}
>has a finite number of elements.
>3. Therefore, each set of natural numbers has finite size.
>This seems to me to be exactly the same argument.
Suppose you have a predicate P that is true or false for each set S. If
we further know that:
1. P(1) is true,
2. P(n) ==> P(n+1) for each natural number n,
then it follows that
3. P(n) is true for every natural number n (all n in N).
This is what mathematical induction means. You are trying to conclude
something quite different, namely
4. P(N) is true.
but there is nothing in point (3) that says P(N) is true, since N, the
set of natural numbers, is not itself a natural number. Substituting (4)
for (3) does not give you "exactly the same argument".
>> One definition of "finite" is "having the same size as some natural
>> number." That is, a set is finite if there is a bijection (a 1-1
>> correspondence) between its members and the set {0, 1, 2, ... n-1} for
>> some n. If you choose that definition, then we don't need an induction
>> proof to show that each natural number is finite, since it follows by
>> definition.
>If the fact that each natural number is finite is an axiom that's ok.
>But I don't see how you can prove this by induction without being able
>to use the same argument to prove that the set of natural numbers is
>finite in size.
You still need induction to show that each member of N is
Dedekind-finite, meaning that no member of N can be placed in bijection
with a proper subset of itself. The induction establishes
Dedekind-finite(n) for each n in N, but it does not show
Dedekind-finite(N). This is not a contradiction, since N is not a member
of N.
--
Dave Seaman dseaman@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
|
|
