Re: Cantor's "diagonal argument". My Objection.

On 7 Dec, 17:25, Jan Burse <janbu...@xxxxxxxxxxx> wrote:
LudovicoVan schrieb:
On 6 Dec, 17:46, Jan Burse <janbu...@xxxxxxxxxxx> wrote:

There are
many many(*) orders on the natural numbers.

Here I give you an order of type omega+omega of
the natural numbers:

    1 3 5 ... 2 4 6 ...

This is very interesting. A couple of questions if you don't mind:

1) I take it to be something like: 1,3,5,...|2,4,6,... How would you
define this sequence formally? (I am puzzled by the non-ending in
between);

In this case I can do it formally based
on the natural numbers. Let J denote
the ordering on NxN. We can define it as
follows:

    J(n,m) :<=> if odd(n) & even(m) then true
                else if even(n) & odd(m) then false
                else n<m

Thank you.

So, an ordering relation? That's cool, but I don't really get it.

Two questions:

1) Given an ordering relation such as J, how can you tell the first
element, or the next of any given element, of the sequence? Overall,
is an ordering relation enough to define a sequence? (I know a
sequence as a function from N to S, where S is the set of terms, and I
am familiar with recursive definitions of such functions.)

I'll have to understand this point before I can get into the rest
of your post!

2) BTW, why/how is the order type of J omega+omega while the domain is
NxN?

-LV

2) What is the cardinality of this sequence (should I say, of the set
of the elements of the sequence)? I guess it is still Aleph_0, but I
think I'd need the formal definition of the sequence to see exactly
how.

The cardinality of the domain of J is the same as
the one of the natural numbers, as the domain
are the natural numbers.

(*) Actually an order on the natural numbers
can be coded in a real number. Guess why?

This is just as interesting: could you please elaborate a little bit?
I can't guess how that is.

We need to show that *any* J can be coded
by a real r.

First of all we code the pairs as single natural
numbers. Thus J(n,m) becomes H(<n,m>), where <.,.>
is an injective mapping from NxN to N. There
are many such mappings available. The simplest
mapping is based on traversing the grid:

     +------------
     |0 1 3
     |2 4
     |5
     |

     <n,m> = (n+m)(n+m+1)/2 + n

Then we see that H is in P(N), i.e. the power
set of N. Now use any injective mapping from P(N)
to the reals R. This is a little bit tricky.
We basically use only the interval [0,1] and
the binary development.

So there is a binary digit 1 after the point
at position n, if H(n) holds. And there is
a binary digit 0 after the point at position
n, if H(n) does not hold. So for example
the finit H={3,5} gives the following real:

    0.00101

Also infinite H's can be coded. But we are
not yet finished. We face the following
problem. For examples the following binary
developments denote the same real:

    0.00100000...
    0.00011111...

So we will actually map to the interval
[0,2], and when ever we have an ending
1111 we add 1. So the above two would be
coded as:

    0.00100000...
    1.00100000...

Now we are done, we have an injective
mapping from any relation J to [0,2].
The orderings are a subset of all the
relations, and are thus also mapped.

Bye
.

Relevant Pages

  • Re: Cantors "diagonal argument". My Objection.
    ... of the elements of the sequence)? ... is an injective mapping from NxN to N. There ... to the reals R. This is a little bit tricky. ... So there is a binary digit 1 after the point ...
    (sci.logic)
  • Re: infinity
    ... > For simplicity, we first map the reals in into the more ... fis the set of naturals that correspond to the ... > Combining f and g gives us our mapping function, ... of the sequence A is zero. ...
    (sci.math)
  • Re: Multiple infinities - one more look
    ... continued for lager length of digit sequences without limit. ... infinite digit sequences... ... so the resulting reals have an order. ... (i.e. having a finite program to output their digits in sequence). ...
    (sci.math)
  • Re: Galileos Paradox and the Project of the Reals
    ... The way you get reals by a neverending process of generating digits ... and which thereby constructs a sequence of nested intervals whose ... It isn't *already* in the rationals you started with. ...
    (sci.math)
  • Re: Cantor Confusion
    ... least appears to totally disconnect the set of those remaining. ... sequence of reals with each term less than all terms of a strictly ... This is not the case for rationals. ...
    (sci.math)
Quantcast