# Re: Infinities, cardinality, diagonalisation

Hi Quentin, Tom and List,

Of course, N is the set of finite positive integers:

N = {0, 1, 2, 3, ...}.

An infinite set A is countable or enumerable if there is a computable bijection between A and N.

Forgetting temporarily the number zero, all finite number can be put in the shapes:

|
||
|||
||||
|||||
||||||
|||||||
||||||||
...

This raises already an infinitely difficult problem: how to define those finite numbers to someone who does not already have some intuition about them. The answer is: IMPOSSIBLE. This is part of the failure of logicism, the doctrine that math can be reduced to logic. technically this can be explained through mathematical logic either invoking the incompleteness phenomenon, or some result in model theory (for example Lowenheim-Skolem results).

But it is possible to experience somehow that impossibility by oneself without technics by trying to define those finite sequence of strokes without invoking the notion of finiteness.

Imagine that you have to explain the notion of positive integer, or natural number greater than zero to some extraterrestrials A and B. A is very stubborn, and B is already too clever (as you will see).

So, when you present the sequence:

| || ||| ...

A replies that he has understood. Numbers are the object "|",and the object "||", and the object "|||", and the object "...”. So A conclude there are four numbers. You try to correct A by saying that "..." does not represent a number, but does represent some possibility of getting other numbers by adding a stroke "|" at their end. From this A concludes again that there is four numbers: |, ||, |||, and ||||. You try to explain A that "..." really mean to can continue to add the "|"; so A concludes that there are five numbers now. So you will try to explain to A that "..." means you can continue to add the "I" as many times as you want. From this A will understand that the set of numbers is indefinite: it is

{|, ||, |||, ||||, |||||} or {|, ||, |||, ||||, |||||, ïïïïïï} or some huge one but similarly ... finite.

Apparently A just doesn't grasp the idea of the infinite.

B is more clever. After some time he seems to grasp the idea of "...", and apparently he does understand the set {|, ||, |||, ||||, |||||, ...}. But then, like in Tom's post, having accepted the very idea of
infinity through the use of "...", B, in some exercise, can accept the infinite object

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||...

itself as a number. How will you explain him that he has not the right to take this as a finite number. He should add that the rule, consisting in adding a stroke "|" at the end of a number (like "|||||||"), can only be applied a finite number of times. OK, but the problem was just that: how to define "a finite number" ....

The modern answer is that this is just impossible. The set of positive integers N cannot be defined univocally in any finite way.

This can take the form of some theorem in mathematical logic. For example: it is not possible to define the term "finite" in first order classical logic. There is not first order logic theory having finite model for each n, but no infinite models.
You can define "finite" in second order logic, but second order logic are defined through the intuition of finiteness/non-finiteness, so this does not solve the problem.

This can be used to show that comp will make the number some absolute mystery.

Now, note that B, somehow, can consider the generalized number:

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||...

as a number. Obviously, this corresponds to our friend the *ordinal omega*. From the axiom that you get a number by adding a stroke at its end: you will get

omega+1, as

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||...|

omega+2, as

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||...||

omega+3

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||...|||

...

omega+omega

||||||||||||||||||||||||||||||...||||||||||||||||||||||||||||||...

...

omega+omega+omega

||||||||||||||||||||||||||||||...||||||||||||||||||||||||||||||...||||||||||||||||||||||||||||||...

...

omega*omega

|||...|||...|||...|||...|||...|||...|||...|||...|||...|||...|||...|||...|||...|||...|||...|||...|||...|||... ...

... and this generate a part of the constructive countable ordinals.

And we stay in the domain of the countable structure, unless you decide to go up to the least non countable ordinals and beyond. For doing this properly you need some amount of (formal) set theory. In all case, what "..." expressed is unavoidably ambiguous.

Bruno

Le 13-juil.-06, à 15:29, Quentin Anciaux a écrit :

But then I have another question, N is usually said to contains positive integer number from 0 to +infinity... but then it seems it should contains infinite length integer number... but then you enter the problem I've shown, so N shouldn't contains infinite length positive integer number. But if they aren't natural number then as the set seems uncountable they are in fact real number, but real number have a decimal point no ? so how N is restricted to only finite length number (the set is also infinite) without infinite length number ?

Thanks,
Quentin

On 7/13/06, Tom Caylor <[EMAIL PROTECTED]> wrote:
I think my easy answer is to say that infinite numbers are not in N.  I
like to think of it with a decimal point in front, to form a number
between 0 and 1.  Yes you have the rational numbers which eventually
have a repeating pattern (or stop).  But you also have in among them
the irrational numbers which are uncountable. (Hey this reminds me of
the fi among the Fi.)

To ask what is the next number after an infinite number, like
11111...11111... is similar asking what is the next real number after
0.11111...11111...

Tom

http://iridia.ulb.ac.be/~marchal/

--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---