Re: Bijections (was OM = SIGMA1)
Le 20-nov.-07, à 17:59, meekerdb a écrit :
Bruno Marchal wrote:
.
But infinite ordinals can be different, and still have the same
cardinality. I have given examples: You can put an infinity of linear
well founded order on the set N = {0, 1, 2, 3, ...}.
What is the definition of linear well founded order? I'm familiar
with well ordered, but how is linear applied to sets? Just
curious.
By linear, I was just meaning a non branching order. A tree can be well
founded too, meaning all its branches have a length given by an
ordinal.
Bruno
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 [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Le 20-nov.-07, à 17:47, David Nyman a écrit :
On 20/11/2007, Bruno Marchal [EMAIL PROTECTED] wrote:
David, are you still there? This is a key post, with respect to the
Church Thesis thread.
Sorry Bruno, do forgive me - we seem destined to be out of synch at
the moment. I'm afraid I'm too distracted this week to respond
adequately - back on-line next week at the latest.
Take it easy. It is the main advantage of electronical conversation,
unlike the phone, we can answer at the best moment. But I appreciate
you tell me.
See you next week.
Bruno
PS I'm afraid I have not the time to comment the last posts today,
except for elementary question perhaps, but I will have more time soon
(probably or hopefully tomorrow).
David
Hi,
David, are you still there? This is a key post, with respect to the
Church Thesis thread.
So let us see that indeed there is no bijection between N and 2^N =
2X2X2X2X2X2X... = {0,1}X{0,1}X{0,1}X{0,1}X... = the set of infinite
binary sequences.
Suppose that there is a bijection between N and the set of infinite
binary sequences. Well, it will look like that, where again
represents the ropes:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
My sheep are the natural numbers, and my neighbor's sheep are the
infinite binary sequences (the function from N to 2, the elements of
the infinite cartesian product 2X2X2X2X2X2X... ).
My flock of sheep is the *set* of natural numbers, and my neighbor's
flock of sheep is the *set* of all infinite binary sequences.
Now, if this:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
is really a bijection, it means that all the numbers 1 and 0 appearing
on the right are well determined (perhaps in Platonia, or in God's
mind, ...).
But then the diagonal sequence, going from the left up to right down,
and build from the list of binary sequences above:
1 0 0 1 0 0 ...
is also completely well determined (in Platonia or in the mind of a
God).
But then the complementary sequence (with the 0 and 1 permuted) is
also
well defined, in Platonia or in the mind of God(s)
0 1 1 0 1 1 ...
But this infinite sequence cannot be in the list, above. The God in
question has to ackonwledge that.
The complementary sequence is clearly different
-from the 0th sequence (1, 0, 0, 1, 1, 1, 0 ..., because it differs at
the first (better the 0th) entry.
-from the 1th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the second (better the 1th) entry.
-from the 2th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the third (better the 2th) entry.
and so one.
So, we see that as far as we consider the bijection above well
determined (by God, for example), then we can say to that God that the
bijection misses one of the neighbor sheep, indeed the sheep
constituted by the infinite binary sequence complementary to the
diagonal sequence cannot be in the list, and that sequence is also
well
determined (given that the whole table is).
But this means that this bijection fails. Now the reasoning did not
depend at all on the choice of any particular bijection-candidate.
Any
conceivable bijection will lead to a well determined infinite table of
binary numbers. And this will determine the diagonal sequence and then
the complementary diagonal sequence, and this one cannot be in the
list, because it contradicts all sequences in the list when they cross
the diagonal (do the drawing on paper).
Conclusion: 2^N, the set of infinite binary sequences, is not
enumerable.
All right?
Next I will do again that proof, but with notations instead of
drawing, and I will show more explicitly how the contradiction arise.
Exercice-training: show similarly that N^N, the set of functions from
N
to N, is not enumerable.
Bruno
http://iridia.ulb.ac.be/~marchal/
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 [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Le 20-nov.-07, à 23:39, Barry Brent wrote : You're saying that, just because you can *write down* the missing sequence (at the beginning, middle or anywhere else in the list), it follows that there *is* no missing sequence. Looks pretty wrong to me. Cantor's proof disqualifies any candidate enumeration. You respond by saying, well, here's another candidate! But Cantor's procedure disqualified *any*, repeat *any* candidate enumeration. Barry Brent Torgny, I do agree with Barry. Any bijection leads to a contradiction, even in some effective way, and that is enough (for a classical logician). But look what you write: On Nov 20, 2007, at 11:42 AM, Torgny Tholerus wrote: An ultrafinitist comment to this: == You can add this complementary sequence to the end of the list. That will make you have a list with this complementary sequence included. But then you can make a new complementary sequence, that is not inluded. But you can then add this new sequence to the end of the extended list, and then you have a bijection with this new sequence also. And if you try to make another new sequence, I will add that sequence too, and this I will do an infinite number of times. How could an ultrafinitist refute an argument by saying ... and this I will do an infinite number of times. ? So you will not be able to prove that there is no bijection... Actually no. If you do what you described omega times, you will just end up with a set which can still be put in 1-1 correspondence with N (as shown in preceding posts on bijections) To refute Cantor, here, you should do what you described a very big infinity of times, indeed an non enumerable infinity of times. But then you have to assume the existence of a non enumerable set at the start. OK? Bruno http://iridia.ulb.ac.be/~marchal/ == What is wrong with this conclusion? -- Torgny Dr. Barry Brent [EMAIL PROTECTED] http://home.earthlink.net/~barryb0/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Le 21-nov.-07, à 08:49, Torgny Tholerus a écrit :
meekerdb skrev:Torgny Tholerus wrote:
An ultrafinitist comment to this:
==
You can add this complementary sequence to the end of the list. That
will make you have a list with this complementary sequence included.
But then you can make a new complementary sequence, that is not
inluded. But you can then add this new sequence to the end of the
extended list, and then you have a bijection with this new sequence
also. And if you try to make another new sequence, I will add that
sequence too, and this I will do an infinite number of times. So you
will not be able to prove that there is no bijection...
==
What is wrong with this conclusion?
You'd have to insert the new sequence in the beginning, as there is no
end of the list.
Why can't you add something to the end of the list? In an earlier
message Bruno wrote:
Now omega+1 is the set of all ordinal strictly lesser than omega+1,
with the convention above. This gives {0, 1, 2, 3, ... omega} = {0, 1,
2, 3, 4, {0, 1, 2, 3, 4, }}.
In this sentence he added omega to the end of the list of natural
numbers...
Adding something to the end or to the middle or to the beginning of an
infinite list, does not change the cardinality of that list. And in
Cantor proof, we are interested only in the cardinality notion.
Adding something to the beginning or to the end of a infinite ORDERED
list, well, it does not change the cardinal of the set involved, but it
obviosuly produce different order on those sets, and this can give
different ordinal, which denote type of order (isomorphic order).
The ordered set {0, 1, 2, 3, ...} has the same cardinality that the
ordered set {1, 2, 3, 4, ... 0} (where by definition 0 is bigger than
all natural numbers). But they both denote different ordinal, omega,
and omega+1 respectively. Note that {1, 0, 2, 3, 4, ...} is a different
order than {0, 1, 2, 3, ...}, but both order here are isomorphic, and
correspond to the same ordinal (omega).
That is why 1+omega = omega, and omega+1 is different from omega.
Adding one object in front of a list does not change the type of the
order. Adding an element at the end of an infinite list does change the
type of the order. {0, 1, 2, 3, ...} has no bigger element, but {1, 2,
3, ... 0} has a bigger element. So, you cannot by simple relabelling of
the elements get the same type of order (and thus they correspond to
different ordinals).
OK? (this stuff will not be used for Church Thesis, unless we go very
far ...later).
Bruno
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 [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Bruno Marchal skrev:
Le 20-nov.-07, 23:39, Barry Brent wrote :
You're saying that, just because you can *write down* the missing
sequence (at the beginning, middle or anywhere else in the list), it
follows that there *is* no missing sequence. Looks pretty wrong to me.
Cantor's proof disqualifies any candidate enumeration. You respond
by saying, "well, here's another candidate!" But Cantor's procedure
disqualified *any*, repeat *any* candidate enumeration.
Barry Brent
Torgny, I do agree with Barry. Any bijection leads to a contradiction,
even in some effective way, and that is enough (for a classical
logician).
What do you think of this "proof"?:
Let us have the bijection:
0 {0,0,0,0,0,0,0,...}
1 {1,0,0,0,0,0,0,...}
2 {0,1,0,0,0,0,0,...}
3 {1,1,0,0,0,0,0,...}
4 {0,0,1,0,0,0,0,...}
5 {1,0,1,0,0,0,0,...}
6 {0,1,1,0,0,0,0,...}
7 {1,1,1,0,0,0,0,...}
8 {0,0,0,1,0,0,0,...}
...
omega --- {1,1,1,1,1,1,1,...}
What do we get if we apply Cantor's Diagonal to this?
--
Torgny
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Theory of Everything based on E8 by Garrett Lisi
A theory of everyting is sweeping the Physics community. The theory by Garrett Lisi is explained in this Wiki entry. http://en.wikipedia.org/wiki/An_Exceptionally_Simple_Theory_of_Everything A simulation of E8 can be found a the New Scientist. http://www.newscientist.com/channel/fundamentals/dn12891-is-mathematical-pattern-the-theory-of-everything.html The Wiki entry http://en.wikipedia.org/wiki/E8_%28mathematics%29 on E8 is also interesting. George --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
elaboration Re: Cantor's Diagonal
The reason it isn't a bijection (of a denumerable set with the set of
binary sequences): the pre-image (the left side of your map) isn't
a set--you've imposed an ordering. Sets, qua sets, don't have
orderings. Orderings are extra. (I'm not a specialist on this stuff
but I think Bruno, for example, will back me up.) It must be the
case that you won't let us identify the left side, for example, with
{omega, 0, 1, 2, ... }, will you? For if you did, it would fall under
Cantor's argument.
Barry
On Nov 21, 2007, at 10:33 AM, Torgny Tholerus wrote:
Bruno Marchal skrev:
Le 20-nov.-07, à 23:39, Barry Brent wrote :
You're saying that, just because you can *write down* the missing
sequence (at the beginning, middle or anywhere else in the list),
it follows that there *is* no missing sequence. Looks pretty
wrong to me. Cantor's proof disqualifies any candidate
enumeration. You respond by saying, well, here's another
candidate! But Cantor's procedure disqualified *any*, repeat
*any* candidate enumeration. Barry Brent
Torgny, I do agree with Barry. Any bijection leads to a
contradiction, even in some effective way, and that is enough (for
a classical logician).
What do you think of this proof?:
Let us have the bijection:
0 {0,0,0,0,0,0,0,...}
1 {1,0,0,0,0,0,0,...}
2 {0,1,0,0,0,0,0,...}
3 {1,1,0,0,0,0,0,...}
4 {0,0,1,0,0,0,0,...}
5 {1,0,1,0,0,0,0,...}
6 {0,1,1,0,0,0,0,...}
7 {1,1,1,0,0,0,0,...}
8 {0,0,0,1,0,0,0,...}
...
omega --- {1,1,1,1,1,1,1,...}
What do we get if we apply Cantor's Diagonal to this?
--
Torgny
Dr. Barry Brent
[EMAIL PROTECTED]
http://home.earthlink.net/~barryb0/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
