Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Cantor's diagonal argument.
Replies: 24   Last Post: Oct 12, 2001 5:16 PM

 Messages: [ Previous | Next ]
 Dave Seaman Posts: 555 Registered: 12/6/04
Re: Cantor's diagonal argument.
Posted: Oct 5, 2001 12:26 PM

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

Date Subject Author
10/3/01 Giles Redgrave
10/3/01 Jan Kristian Haugland
10/3/01 Robin Chapman
10/3/01 Clive Tooth
10/3/01 Christian Bau
10/3/01 briggs@encompasserve.org
10/3/01 Randy Poe
10/4/01 Giles Redgrave
10/5/01 Giles Redgrave
10/5/01 Jan Kristian Haugland
10/5/01 Dave Seaman
10/5/01 Christian Bau
10/5/01 Daryl McCullough
10/5/01 Steven Taschuk
10/5/01 Virgil
10/5/01 Tralfaz
10/5/01 Virgil
10/5/01 John Savard
10/12/01 Steve Brian
10/12/01 Virgil
10/4/01 Nico Benschop
10/3/01 Steven Taschuk
10/3/01 Andy Averill
10/3/01 Virgil
10/5/01 John Savard