cardinality of the power set of the integers
Russell Easterly
creating a bijection between the real numbers
and the power set of the integers.
I, probably incorrectly, thought that
such a bijection couldn't exist.
(Several people gave such bijections,
but they were over my head).
My thoughts go like this:
It is generally taught that every real number
has a decimal representation.
I assume that it is fairly straight forward to show
that the set of decimal numbers has the same
cardinality as the power set of the integers.
The problem is that some real numbers have
two different decimal representations.
Doesn't this mean that there are fewer real
numbers than there are decimal representations?
I know that the number of reals with dual representations
is countably infinite and has measure zero.
(You learn this stuff on sci.math even if you
don't understand it.)
Even so, I don't see how a bijection is possible.
How can a function map one real number
to two different decimal representations?
It seems to me that the power set of the
integers is larger than the set of reals.
Russell
-2 many 2 count
Virgil
<logi...@wolfenet.com> wrote:
There is a theorem, whose name I forget, which says that given
injections f:A -> B and g:B -> A, there is a bijection h:A -> B.
There is no need to construct the bijection explicitly.
--
Virgil
vm...@frii.com
Clive Tooth
The representation of the reals by decimals is a complete red herring.
The decimal representation of some real is simply a way of defining that
real. There are many ways of defining a real. If some method was devised
of representing the reals in which each real had 17 distinct
representations, and 18 on every alternate Wednesday, this would not
matter one jot. There would _still_ exist a bijection between the reals
and the power set of the integers.
--
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document
Dave Seaman
Actually, you have that backwards. The power set of the integers is
obviously "smaller" than the set of reals.
Proof. I will demonstrate that there is an injection f: P(N) -> [0,1]
that leaves almost all members of [0,1] unpaired. By your argument, this
will conclusively prove that P(N) is much smaller than [0,1].
It is convenient here to assume that the natural numbers N begin with 1.
Suppose S is a member of P(N). Then f(S) will be the real number whose
base 3 representation has its n-th digit equal to
2, if n is a member of S,
0, otherwise.
For example, if S = the set of even numbers, then f(S) =
(0.02020202...)_3 = (1/4)_10.
A little thought shows that this mapping is indeed an injection f: P(N)
-> [0,1]. However, it leaves unpaired all the reals in [0,1] whose
base-3 representations contains any 1's, which is almost all of them.
Actually, I have to be a bit more careful than that, because there are
some numbers in [0,1] that have two base-3 representations, of which one
contains a 1 and one does not. For example,
x = (0.20210000...)_3
= (0.20202222...)_3.
The correct statement is that if x is any number in [0,1] that cannot be
expressed in base 3 without using any 1's, then x is not in the range of
f.
The range of f is called the Cantor set. It obviously has the same
cardinality as P(N), and yet it is a measure-zero subset of R. Doesn't
this prove that P(N) is *much* smaller than R? (Why, or why not?)
--
Dave Seaman dse...@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://mojo.calyx.net/~refuse/mumia/021700amnesty.html>
Sandy Hodges
infinity doesn't get larger. If you add a countable infinity to an
uncountable one, the uncountable one doesn't get larger. If we start
with the uncountable infinity of the real numbers, and add the countable
infinity of the dual representations, the sum is not larger (in the
sense of more numerous) than the than the set of real numbers. - Sandy
Virgil
(Dave Seaman) wrote:
>The range of f is called the Cantor set. It obviously has the same
>cardinality as P(N), and yet it is a measure-zero subset of R. Doesn't
>this prove that P(N) is *much* smaller than R? (Why, or why not?)
It only proves that the cardinal of P(N) is >= the cardinality of R.
A similar mapping can be made from the reals to the reals, mapping
binary representations onto trinary representations, in which the image
of R has measure zero in R, the codomain of the function.
Would this prove that the cardinality of R is less than the cardinality
of R? Then we would really have problems!
--
Virgil
vm...@frii.com
Russell Easterly
Dave Seaman <a...@seaman.cc.purdue.edu> wrote in message
news:8ijf3g$3...@seaman.cc.purdue.edu...
> In article <8ijbha$ob$1...@sparky.wolfe.net>,
> Russell Easterly <logi...@wolfenet.com> wrote:
> The range of f is called the Cantor set. It obviously has the same
> cardinality as P(N), and yet it is a measure-zero subset of R. Doesn't
> this prove that P(N) is *much* smaller than R? (Why, or why not?)
Its one of those infinity things, right?
Like proving there are just as many
even integers as there are integers.
An injection is not a bijection.
So, is there a bijection between
the reals and P(N)?
Russell
-Dave will teach me something yet
Dennis Paul Himes
Other people have responded to other parts of your post. I would just
like to comment on:
> The problem is that some real numbers have
> two different decimal representations.
> Doesn't this mean that there are fewer real
> numbers than there are decimal representations?
No. It's not too hard to construct a bijection between the reals and
their decimal representations.
Let R = the set of all reals. Let N = the set of all naturals (starting
with zero). Let D = set of all decimal representations. Let S = the set of
all reals which have two different representations. (So S is a subset of
R). You noted, correctly, in your post that:
> the number of reals with dual representations
> is countably infinite ...
Since S is countable let's count it. Let f:N->S be a bijection from the
naturals to the reals. Since this is bijection there exists an inverse
function g:S->N. For any s in S let s_0 be one decimal representation and
let s_1 be the other. (It doesn't matter how you sort them, just so you
do.)
The following is a bijection d:R->D from the reals to the set of the reals'
decimal representations.
For a real r:
if r is not in S, then d(r) is the unique decimal representation of r.
if r is in S and g(r) is even then d(r) = f(g(r)/2)_0.
if r is in S and g(r) is odd then d(r) = f((g(r)-1)/2)_1.
I.e. the first decimal representation of the k'th member of S is
associated with the 2k'th member of S, and the second decimal representation
of the k'th member of S is associated with the (2k+1)'th member of S.
============================================================================
Dennis Paul Himes <> den...@sculptware.com
http://www.connix.com/~dennis/dennis.htm
Disclaimer: "True, I talk of dreams; which are the children of an idle
brain, begot of nothing but vain fantasy; which is as thin of substance as
the air." - Romeo & Juliet, Act I Scene iv Verse 96-99
Dave Seaman
Russell Easterly <logi...@wolfenet.com> wrote:
>Dave Seaman <a...@seaman.cc.purdue.edu> wrote in message
>news:8ijf3g$3...@seaman.cc.purdue.edu...
>> In article <8ijbha$ob$1...@sparky.wolfe.net>,
>> Russell Easterly <logi...@wolfenet.com> wrote:
>> The range of f is called the Cantor set. It obviously has the same
>> cardinality as P(N), and yet it is a measure-zero subset of R. Doesn't
>> this prove that P(N) is *much* smaller than R? (Why, or why not?)
>Its one of those infinity things, right?
>Like proving there are just as many
>even integers as there are integers.
>An injection is not a bijection.
>So, is there a bijection between
>the reals and P(N)?
Yes. In fact, one has been described fairly recently in this newsgroup.
The map that you originally described is close enough to a bijection that
it can be easily fixed.
Another way is to use the Cantor-Bernstein theorem, which says that if
you have an injection f: A -> B and also an injection g: B -> A, then
there is a bijection h: A <-> B.
--
Chuck Cadman
naturals and the rationals. We know they are bijective because there are
injections in both directions, but has anyone ever found an explicit
bijection?
Dafydd y garreg wen
We can see this quite intuitively:- imagine the rationals laid out on an
infinite 2D lattice, with the value at each vertex of the lattice being
(y-coordinate)/(x-coordinate). So we have the undefined value 0/0 at the
origin, indeed the undefined values n/0 at n points above the origin
(where n can be negative also), and the rather more defined values {a/b |
b not equal to 0, a,b in N} elsewhere. Now start mapping N to the vertices
by the following process:-
Starting at (1,0) (with the value 0/1), proceed around the origin in a
square (either way; we'll use anticlockwise), ignoring any values that are
either undefined as above or that are identical to a previous value
(e.g. 4/2 = 2/1, so move on). So, calling our function f, we get
f(1)=0/1 = 0, f(2)=1/1 = 1, skip the impossible value 1/0 to get f(3)=1/-1
= -1, skip the repeated value 0/-1=0/1=0 and the repeated value -1/-1=1/1
and the impossible value -1/0 and the repeated value -1/1=1/-1. Now the
square is complete; move out one vertex along the origin and
continue. Obviously the first value of this square (0/2) is a repeat (as
for any subsequent square by this recipe), but the second value yields
f(4)=1/2. Continuing, f(5)=2, f(6)=-2, f(7)=-1/2, and then we need to
start the third square.
f is clearly injective (as repeats are discarded), and surjective, as the
lattice contains every rational by definition of the rationals.
So f is a bijection between N and Q.
Not pretty, but I don't think that it gets much nicer. Sorry.
Dave Taylor
Torkel Franzen
> This is related to an interesting problem. Find a bijection between the
> naturals and the rationals. We know they are bijective because there are
> injections in both directions, but has anyone ever found an explicit
> bijection?
Yes, Cantor did.
Tony Thomas
eg 1/2 = 2/4 = 3/6 = ... n/2n ...
and the rationals are supposed to have the same cardinality as the natural
numbers.
Although n->f(n), so that they both have the same cardinality, what of
n->EXP(2,n)?
The relevance of this is that there are EXP(2,n) binary representations for
every n integers and so there are EXP(2,n) representations when n tends to
infinity. However,
this is just the number of reals in binary form at infinity. This shows that
the cardinality of the reals is the same as the cardinality of the natural
numbers. If this is false, then the reductio points the finger at one of the
assumptions in this argument. The false assumption is that n->f(n) in the
infinite case.
Russell Easterly <logi...@wolfenet.com> wrote in message
news:8ijbha$ob$1...@sparky.wolfe.net...
> I was recently in an argument about
> creating a bijection between the real numbers
> and the power set of the integers.
> I, probably incorrectly, thought that
> such a bijection couldn't exist.
> (Several people gave such bijections,
> but they were over my head).
>
> My thoughts go like this:
>
> It is generally taught that every real number
> has a decimal representation.
>
> I assume that it is fairly straight forward to show
> that the set of decimal numbers has the same
> cardinality as the power set of the integers.
>
> The problem is that some real numbers have
> two different decimal representations.
> Doesn't this mean that there are fewer real
> numbers than there are decimal representations?
>
Virgil
<cdc26SP...@columbia.edu> wrote:
>This is related to an interesting problem. Find a bijection between the
>naturals and the rationals. We know they are bijective because there are
>injections in both directions, but has anyone ever found an explicit
>bijection?
>
>
Yes, there are numerous publilshed bijections between the naturals and
the rationals.
For example:
Let a/b, where a is an integer and b is a strictly positive integer and
a and b are relatively prime, be the representation of a rational (a/1
is the representation of integer a as a rational).
Group the rationals with equal values of n = |a| + |b| together and list
these groups in order of increasing n. Note that each such group is
finite. Within each group list the rationals in normal rational number
order. We now have a countable number of finite groupings.
This constitutes an ordering of the rationals in which the rationals can
be counted, so is the requisite bijection.
--
Virgil
vm...@frii.com
Dave Seaman
Chuck Cadman <cdc26SP...@columbia.edu> wrote:
>This is related to an interesting problem. Find a bijection between the
>naturals and the rationals. We know they are bijective because there are
>injections in both directions, but has anyone ever found an explicit
>bijection?
An elegant mapping is described in "Recounting the Rationals" by N.
Calkin and H. S. Wilf, _American Mathematical Monthly_, Vol. 107, No. 4
(April, 2000), p. 360. Their sequence begins
1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...
In which the denominator of each fraction is the numerator of the next
one. The successive values are:
{1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,...}
Consecutive values in this sequence are always relatively prime, and
therefore all fractions appear in lowest terms. Each positive rational
appears exactly once in the resulting list.
You can think of the fractions as appearing in a tree:
1/1
1/2 2/1
1/3 3/2 2/3 3/1
1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
. . .
Notice that each node in the tree has two descendants, a left son and a
right son. If the parent node is the fraction i/j, then its left son is
i/(i+j) and its right son is (i+j)/j.
[Now, let's see how long it takes for someone to object that the tree has
2^aleph0 nodes in it, and therefore is uncountable.]
Russell Easterly
Chuck Cadman <cdc26SP...@columbia.edu> wrote in message
news:8ikbr9$ivk$1...@newsmaster.cc.columbia.edu...
> This is related to an interesting problem. Find a bijection between the
> naturals and the rationals. We know they are bijective because there are
> injections in both directions, but has anyone ever found an explicit
> bijection?
>
>
I thought of this one on the way home from work.
It should get every rational between 0 and 1 (exclusive).
Let N be the denominator.
Start with N=2.
Let M be the numerator.
M can range from 1 to N-1.
We only consider an M if it is relatively prime to N.
The resulting series is:
1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, ...
Dik T. Winter
> You can think of the fractions as appearing in a tree:
>
> 1/1
> 1/2 2/1
> 1/3 3/2 2/3 3/1
> 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
> . . .
and Games.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Taneli Huuskonen
Hash: SHA1
In <8ili4o$4...@seaman.cc.purdue.edu> a...@seaman.cc.purdue.edu
(Dave Seaman) writes:
[a beautiful construction snipped]
>[Now, let's see how long it takes for someone to object that the tree has
>2^aleph0 nodes in it, and therefore is uncountable.]
ROTFLMAO! Considering the usual audience of sci.logic, I was mildly
surprised to find that nobody had followed up on you saying "but it does
have 2^aleph0 nodes in it!"
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBOU9LXl+t0CYLfLaVEQKIWACgoNsAkdrVNsggEZzbdGHI/F0z+RgAoK2A
bMsZsUbir2/9YtutlXipb4h6
=1RCF
-----END PGP SIGNATURE-----
--
I don't | All messages will be PGP signed, | Fight for your right to
speak for | encrypted mail preferred. Keys: | use sealed envelopes.
the Uni. | http://www.helsinki.fi/~huuskone/ | http://www.gilc.org/
John Savard
<logi...@wolfenet.com> wrote, in part:
>I was recently in an argument about
>creating a bijection between the real numbers
>and the power set of the integers.
>I, probably incorrectly, thought that
>such a bijection couldn't exist.
>(Several people gave such bijections,
>but they were over my head).
Oh, yes, the two sets have the same cardinality.
Basically, the real numbers in [0,1) biject nicely to the power set of
the integers...just represent them in binary notation, and the digits
after the radix point tell you if each of the integers in order is in
the set which is an element of the power set of the integers.
To tidy up for the .01111... = .1 problem, to include the negative
integers, to include all the real numbers, all just require adding a
few complicated details.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
Lars Henrik Mathiesen
>In article <8ikbr9$ivk$1...@newsmaster.cc.columbia.edu>,
>Chuck Cadman <cdc26SP...@columbia.edu> wrote:
>>This is related to an interesting problem. Find a bijection between the
>>naturals and the rationals. We know they are bijective because there are
>>injections in both directions, but has anyone ever found an explicit
>>bijection?
>An elegant mapping is described in "Recounting the Rationals" by N.
>Calkin and H. S. Wilf, _American Mathematical Monthly_, Vol. 107, No. 4
>(April, 2000), p. 360. Their sequence begins
> 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...
>In which the denominator of each fraction is the numerator of the next
>one. The successive values are:
> {1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,...}
>Consecutive values in this sequence are always relatively prime, and
>therefore all fractions appear in lowest terms. Each positive rational
>appears exactly once in the resulting list.
>You can think of the fractions as appearing in a tree:
> 1/1
> 1/2 2/1
> 1/3 3/2 2/3 3/1
> 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
> . . .
>Notice that each node in the tree has two descendants, a left son and a
>right son. If the parent node is the fraction i/j, then its left son is
>i/(i+j) and its right son is (i+j)/j.
What I find interesting is that this mapping allows an 'efficient'
algorithm to from a positive rational to its position in this sequence
(as a positive integer, i.e., 1/1 <+> 1, ...) and back. (Extending to
Z <-> Q is easy, map 0 to 0 and negatives to negatives).
(Of course all the other suggestions generate algorithms too, but they
seem to be of the type "generate the sequence from the start, counting
non-repeats, until you get to the rational you're looking for").
For instance, to get from 4/7 to the top of the tree, we come from the
left to 4/3, from the right to 1/3, from the left to 1/2, from the
left to 1/1.
Put 0 for left, 1 for right, starting at the least significant
position, and finish with a 1: 10010, which is binary for 18. And 4/7
is number 18 in the sequence.
In other words, the binary representation of the integers is taken as
a trace of the 'simple' GCD algorithm applied to the least-terms form
of the rational. ('Simple' means using subtraction, not remainder).
=============================
In Contrete Mathematics, Knuth et al. also treat a enumeration of the
rationals. It extends the set of positive rationals with two pseudo-
elements (0/1 1/0), which form the base sequence. This is successively
refined by inserting (a+c)/(b+d) between each pair a/b and c/d:
(0/1) (1/0)
(0/1) 1/1 (1/0)
(0/1) 1/2 1/1 2/1 (1/0)
(0/1) 1/3 1/2 2/3 1/1 3/2 2/1 3/1 (1/0)
(0/1) 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 (1/0)
The enumeration is arrived at by counting the new entries in each row.
(Puzzle: This can be mapped to Calkin and Wilf's sequence by reversing
the bits after the leading one in the binary representation. Why?)
====================
I just thought of another 'direct' mapping (but I can't imagine it's
original). This one does not have to throw out repeats either --- in
fact it's not even based on putting all the rationals in a sequence.
It goes like this: Positive integers are uniquely represented by a
sequence of non-negative prime number exponents.
Likewise, positive rationals are uniquely represented by a sequence of
signed prime number exponents. (Since the same prime number can't
factor in both numerator and denominator of the least-terms form).
In both cases the sequences are indexed by the naturals, but only
finitely many elements are non-zero.
Thus, there's an easy bijection between the two representations: apply
a bijection N_0 <--> Z, like the one carrying (0, 1, 2, 3, 4, ...) to
(0, 1, -1, 2, -2, ...), at each index of the sequences.
When all that is put together, the integers 1, 2,..., 30 map with
1/1 2/1 3/1 1/2 5/1 6/1 7/1 4/1 1/3 10/1 11/1 3/2 13/1 14/1 15/1
1/4 17/1 2/3 19/1 5/2 21/1 22/1 23/1 12/1 1/5 26/1 9/1 7/2 29/1 30/1
It looks weird, but it seems to work.
Lars Mathiesen (U of Copenhagen CS Dep) <tho...@diku.dk> (Humour NOT marked)
Pam Taylor
Virgil wrote:
> <snip>
> There is a theorem, whose name I forget, which says that given
> injections f:A -> B and g:B -> A, there is a bijection h:A -> B.
>
> There is no need to construct the bijection explicitly.
The Cantor-Schroeder-Bernstein Theorem.
Larry Taylor
David Libert
Yes, I always thought this is the best way to handle P(integers) and
reals instead of mucking about with coding to handle the non-unique
representation. It is much easier to define explicit injections each
way.
The proof of the C-S-B theorem is constructive, so if you feed into it
explicit definitions of each one way injection, you get a definition of
the bijection. It is quite a messy definition though.
For what it is worth I have just thought of a direct bijection of this
form, with a fairly simple definition. I seem to recall having read a
coment to this effect last year in sci.math or sci.logic.
I will describe a bijection from the powerset of the positive integers
to the real interval (0, 1], that is all reals r s.t. r > 0 and
r <= 1.
Given a subset A of the positive integers, enumerate it in increasing
order by a finite or infinite 1-1 sequence: a1, a2, a3, ... . The
empty set will correspond to the empty sequence.
Define a0 = 0, so stick a new element to the front of the sequence.
Define a new sequence of positive integers, of length = the
cardinality of A: for n > 0 and an defined :
let bn = an - a(n-1) .
Since I defined a0 = 0 , b1 is defined if a1 is. Also since A is a
subset of the positive integers, if b1 is defined then b1 > 0.
Similarly all bn which are defined are > 0.
If A = {} then all bn 's are undefined: the bn sequence is the
empty sequence.
To the set A we associate the unique real number in (0, 1] given by
the continued fraction for the b sequence. In particular, for A = {}
the empty b sequence will be considered to give the "continued fraction"
1, ie the real number 1. If b1 is defined the continued fraction will
be one of the forms: 1/b1, 1/(b1 + 1/(b2 )), depending on whether b2
is defined.
{} corresponds to 1. Finite sets correspond to rationals in (0, 1],
infinite sets to irrationals in (0, 1]. (Ie finite or infinite
continued fractions).
This is a bijection, by the theory of continued fractions.
With this explicit bijection of P(positive integers) to (0, 1] it is
not hard to get other related simple definitions of bijections of other
related sets, ie all reals instead of (0, 1] etc, or variations on
positive integers: nonegative integers or all integers.
--
David Libert (ah...@freenet.carleton.ca)
1. I used to be conceited but now I am perfect.
2. "So self-quoting doesn't seem so bad." -- David Libert
3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig
the_grea...@my-deja.com
huus...@cc.helsinki.fi (Taneli Huuskonen) wrote:
> In <8ili4o$4...@seaman.cc.purdue.edu> a...@seaman.cc.purdue.edu
> (Dave Seaman) writes:
>
> 1/2 2/1
> 1/3 3/2 2/3 3/1
> 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
>
> >the tree has 2^aleph0 nodes in it, and therefore is uncountable.]
>
> ROTFLMAO! Considering the usual audience of sci.logic, I was mildly
> surprised to find that nobody had followed up on you saying "but it
> does have 2^aleph0 nodes in it!"
>
> Taneli Huuskonen
Very funny. You're such a Smart-ass, I bet you could
sit on a carton of ice cream and tell what flavor it is.
Ok, I'll bite.
How is Dave's construction (oo binary tree) different
from the following construction of P(N)?
Nathan's oo binary decision tree P(N)
================================ ============
{all N}
_4_ {1,2,3}
_3_ y/
/ n\_4_ {1,2}
_2_ y/ {primes}
/ n\ _4_ {1,3}
/ \_3_ y/ {odds}
/ n\_4_ {1}
_1_ y/
n\ _4_ {2,3}
\ _3_ y/ {evens}
\ / n\_4_ {2}
\_2_ y/
n\ _4_ {3}
\_3_ y/
n\_4_ {}
n= 1 2 3 4 5 6 78...oo
This tree, just like Dave's, extends infinitely, with
two descendants per node. The numbers inside this tree
are elements of N (natural numbers). The decision, of
whether to include a number in a subset of P(N), takes
place at each node. Every subset of P(N) can be found
at the oo far right, by following its set composition
decision path. The path is not determined (fully) until
all decisions, regarding its membership, are finalized.
That means, accepting P(N) requires the simultaneous
acceptance of the oo decision paths (nodes) leading to
each of its subsets.
I will make this quick and painless. :-)
Evil Cantorians, choose your poison:
(1) The nodes of Nathan's tree are countable.
Hense, P(N), which is the sum total of all
the nodes, is countable.
(2) The nodes of Nathan's tree are uncountable.
Now, since the two trees are isomorphic, the
nodes in Dave's tree are uncountable too.
Hense, the rationals are uncountable.
[Now, let's see how long it takes the fruitcakes to die.]
Remember, we are talking about the "number" of nodes, not
what they repressent. So, basically, this whole discussion
boils down to determining the "number" of nodes that an
infinite binary tree has. End of story.
Notes:
Dave's tree must be "completed" to repressent all of Set Q.
My tree must be "completed" to repressent all of Set P(N).
I can see them protesting...
"Nathan, you snot-nosed brat! The tree is countable, yes,
but that doesn't imply P(N) is countable. Don't you realize
there are more subsets of P(N) than there are paths (nodes)
leading to those subsets. Besides, subsets can be unique
eventhough they share the same path."
Yep, that sounds like a Cantorian.
Nathan the Great
Age: 12 yr
Height: 1.33 m
Weight: 39 kg
Sent via Deja.com http://www.deja.com/
Before you buy.
David Libert
>
> I will describe a bijection from the powerset of the positive integers
>to the real interval (0, 1], that is all reals r s.t. r > 0 and
>r <= 1.
Above I didn't handle the degenerate case A1 = {} right. This case
gives rise to the empty b sequence, I said this should yield the
"continued fraction" 1, and hence the real number 1.
But for A2 = {1}, the b sequence is <1>, ie b1 = 1, giving continued
fraction 1/1, hence real number 1, so {} and {1} both go to 1, contra
injective.
One solution is to just work directly with the non-empty powerset of
positive integers. So last post could define a bijection from the
non-empty subsets of the positive integers to (0, 1] .
This "non-empty powerset" is easily bijective with the full powerset
by sending {} to {1} and doing a "Hilbert Hotel" shift on the
singletons: {n} |-> {n+1}.
Or another solution could be to declare {} goes to 0, and so extend
the bijection of non-empty powerset to (0, 1] to a bijection of full
powerset to [0, 1] .
In fact this last version has a rationale as a more reasonable reading
of "empty continued fraction" then the "1" I used last time.
Namely consider the continued fraction 1/(b1 + 1/b2)). Compare this
to a continued fraction arising when b2 is undefined: 1/b1. When the
b2 disappears, it takes its numerator with it to oblivion.
So given the continued fraction 1/b1, how should that change when b1
is instead undefined, ie A = {} case ? The b1 going zaps the 1 above
it and we are left with: nothing. A more reasonable implimentation of
"the empty continued fraction". And the summation of no terms? 0 .
I rest my case.
Anyway, if this last is too mystical, just send {} by fiat to 0 to get
a simply definable bijection of P(positive integers) to [0, 1] .
There is another way to get a different simply definable bijection.
This next version can't handle A = {} as an exceptional case elegantly,
so we are back to the non-empty powerset of positive integers. We
biject this with the non-negative reals.
Namely in the previous definition, set a0 = 1 instead of a0 = 0.
Form the b sequence as before, except now b1 = 0 is possible, in fact in
general b1 is non-negative integer.
From a b sequence, form the continued fractions with leading integer
term: if b2 undefined form b1 as "continued fraction",
if b2 defined form b1 + 1/(b1 + ...) etc. Note A nonempty, so
b1 is always defined.
This bijects non-empty powerset (positive integers) to [0, infinity)
in the reals, a closed set, so there is no end point to match to {}, so
there is no extension as the previous of (0, 1] to [0, 1]. We can
still handle {} with the Hilbert shift on singletons.
Another nice feature of this basic bijection: the non-negaitve
integers (as a subset of the non-negative reals) are exactly bijective
with the singletons.
the_grea...@my-deja.com
Pam Taylor <tayl...@lightspeed.net> wrote:
>
>
> Virgil wrote:
>
> > <snip>
>
> > There is a theorem, whose name I forget, which says that given
> > injections f:A -> B and g:B -> A, there is a bijection h:A -> B.
> >
> > There is no need to construct the bijection explicitly.
>
> The Cantor-Schroeder-Bernstein Theorem.
>
> Larry Taylor
>
>
Cantor's argument starts out as follows (according to the well-known
Jourdain's translation):
"We have seen that, of the three relations a = b, a < b, b < a, each
one exclude the two others..."
Thats about as inconspicuous as a Tarantula on Angle Food cake. Cantor,
in his infinite wisdom, assumes what he sets out to prove.
This should be called the Cantor-Bernstein ASSUMPTION, not THEORY.
Nathan the Great
Age 12
Torkel Franzen
> This should be called the Cantor-Bernstein ASSUMPTION, not THEORY.
What sort of toadying comment is this? It's not an ASSUMPTION but
a WILD RANT. You're getting to be an old softie, aren't you?
Dave Seaman
As you have pointed out yourself, the numbers inside the tree are
elements of N, not of P(N). There is no way to assign all the members of
P(N) to the nodes of the tree, because there are not enough nodes.
Instead, you have identified each member of P(N) with an infinite path
from the root of your tree. Although the tree has only countably many
nodes, there are uncountably many ways of choosing an infinite path from
the root. Therefore, there is no contradiction.
>I will make this quick and painless. :-)
>Evil Cantorians, choose your poison:
> (1) The nodes of Nathan's tree are countable.
> Hense, P(N), which is the sum total of all
> the nodes, is countable.
Right premise, wrong conclusion. The members of P(N) are not stored in
the nodes.
> (2) The nodes of Nathan's tree are uncountable.
Wrong. It's the number of paths, not the number of nodes, that is
uncountable.
> Now, since the two trees are isomorphic, the
> nodes in Dave's tree are uncountable too.
> Hense, the rationals are uncountable.
>[Now, let's see how long it takes the fruitcakes to die.]
>Remember, we are talking about the "number" of nodes, not
>what they repressent. So, basically, this whole discussion
>boils down to determining the "number" of nodes that an
>infinite binary tree has. End of story.
>Notes:
> Dave's tree must be "completed" to repressent all of Set Q.
> My tree must be "completed" to repressent all of Set P(N).
Correct. But the representations are fundamentally different. I can
easily represent all the members of the Cantor set by associating one
with each branch of my tree. That doesn't make the Cantor set countable.
>I can see them protesting...
> "Nathan, you snot-nosed brat! The tree is countable, yes,
> but that doesn't imply P(N) is countable. Don't you realize
> there are more subsets of P(N) than there are paths (nodes)
> leading to those subsets. Besides, subsets can be unique
> eventhough they share the same path."
When you talk about "subsets of P(N)", I suspect you are really talking
about subsets of N, which are *members* of P(N). A subset of P(N) would
be a member of P(P(N)), a set with cardinality 2^(2^aleph0)) = 2^c.
There are exactly as many members of P(N) (subsets of N) as there are
paths leading to those subsets. The number of paths is greater than the
number of nodes, which is merely countable.
>Yep, that sounds like a Cantorian.
>Nathan the Great
>Age: 12 yr
>Height: 1.33 m
>Weight: 39 kg
--
Herman Rubin
John Savard <jsa...@tenMAPSONeerf.edmonton.ab.ca> wrote:
>On Sun, 18 Jun 2000 13:32:19 -0700, "Russell Easterly"
><logi...@wolfenet.com> wrote, in part:
>>I was recently in an argument about
>>creating a bijection between the real numbers
>>and the power set of the integers.
>>I, probably incorrectly, thought that
>>such a bijection couldn't exist.
>>(Several people gave such bijections,
>>but they were over my head).
>Oh, yes, the two sets have the same cardinality.
There are many simple arguments to do this. There IS
a "natural" bijection between the sets of non-negative
integers and the set of all real numbers. One way of
doing it is as follows.
1. The empty set maps into 0.
2. Otherwise, let the set be ordered as <a_i, i=1, ..., k>,
where k can be infinite. Define sign as + if a_1 is even,
- if a_1 is odd, and define b_1 to be the integer part of
a_1/2. Define b_i, 2 <= i <= k, as a_i - a_{i-1}. Now
define the sequence c_i to be b_i if i < k, and set
c_k = b_k + 1; this includes k=1.
Then the real number mapped into is
sign c_1 + 1/(c_2 + 1/c_3 + ... ),
the magnitude being the "standard" continued fraction.
It is easy to see that the rationals correspond to finite
sets, and the irrationals to infinite sets, and the process
can be reversed to get the set of integers from the real
number by forming the continued fraction, reducing the
last term by 1 if the fraction is finite, incorporating
the sign to get a_1, and using the differences to get the
remaining elements of the set.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
Dave Seaman
<the_grea...@my-deja.com> wrote:
>Cantor's argument starts out as follows (according to the well-known
>Jourdain's translation):
> "We have seen that, of the three relations a = b, a < b, b < a, each
> one exclude the two others..."
>Thats about as inconspicuous as a Tarantula on Angle Food cake. Cantor,
>in his infinite wisdom, assumes what he sets out to prove.
Wrong. What is to be proved is that for every A, |A| < |P(A)|. That
statement does not appear anywhere in the statement you have quoted.
>This should be called the Cantor-Bernstein ASSUMPTION, not THEORY.
>Nathan the Great
>Age 12
Given two sets A and B, there are four _a priori_ possibilities:
1) There is an injection from A to B, but none from B to A.
2) There is an injection from B to A, but none from A to B.
3) There are injections in both directions.
4) There is no injection in either direction.
In case 1) we say that |A| < |B|.
In case 2) we say that |A| > |B|.
In case 3) we can apply the Cantor-Bernstein theorem to conclude that
there is a bijection between A and B, which means that |A| = |B|.
In case 4) we say that A and B are incomparable (there is no relation
between |A| and |B|). Case 4) cannot arise if we accept the axiom of
choice.
Therefore, whether AC holds or not, we can certainly say that 1), 2) and
3) are mutually exclusive possiblities for the existence or nonexistence
of injections between A and B, which is the starting point of Cantor's
argument.
The conclusion of Cantor's argument is that for any A, there is an
injection from A to P(A), but no injection in the reverse direction,
which means that |A| < |P(A)|. This statement does not appear anywhere
in the previous paragraph, and therefore is not the part of any
assumption. The proof comes from the diagonal argument, not from any
assumption.
Dennis Paul Himes
> huus...@cc.helsinki.fi (Taneli Huuskonen) wrote:
> > In <8ili4o$4...@seaman.cc.purdue.edu> a...@seaman.cc.purdue.edu
> > (Dave Seaman) writes:
> >
> > 1/1
> > 1/2 2/1
> > 1/3 3/2 2/3 3/1
> > 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
> >
> > >[Now, let's see how long it takes for someone to object that
> > >the tree has 2^aleph0 nodes in it, and therefore is uncountable.]
> >
> > ROTFLMAO! Considering the usual audience of sci.logic, I was mildly
> > surprised to find that nobody had followed up on you saying "but it
> > does have 2^aleph0 nodes in it!"
>
>
> How is Dave's construction (oo binary tree) different
> from the following construction of P(N)?
>
> Nathan's oo binary decision tree P(N)
> ================================ ============
> {all N}
> _4_ {1,2,3}
> _3_ y/
> / n\_4_ {1,2}
> _2_ y/ {primes}
> / n\ _4_ {1,3}
> / \_3_ y/ {odds}
> / n\_4_ {1}
> _1_ y/
> n\ _4_ {2,3}
> \ _3_ y/ {evens}
> \ / n\_4_ {2}
> \_2_ y/
> n\ _4_ {3}
> \_3_ y/
> n\_4_ {}
>
> n= 1 2 3 4 5 6 78...oo
The difference is that the rationals are represented in Dave's tree by
the nodes of the tree, and the members of P(N) are represented in your tree
by the paths on the tree. Both trees have a countable number of nodes.
Both trees have an uncountable number of paths.
> Evil Cantorians, choose your poison:
>
> (1) The nodes of Nathan's tree are countable.
This is true.
> Hense, P(N), which is the sum total of all
> the nodes, is countable.
This is false. P(N) is represented by paths, not nodes.
David Libert
Pam Taylor (tayl...@lightspeed.net) writes:
> Virgil wrote:
>
>> <snip>
>
>> There is a theorem, whose name I forget, which says that given
>> injections f:A -> B and g:B -> A, there is a bijection h:A -> B.
>>
>> There is no need to construct the bijection explicitly.
>
> The Cantor-Schroeder-Bernstein Theorem.
>
> Larry Taylor
Yes, I always thought this is the best way to handle P(integers) and
reals instead of mucking about with coding to handle the non-unique
representation. It is much easier to define explicit injections each
way.
The proof of the C-S-B theorem is constructive, so if you feed into it
explicit definitions of each one way injection, you get a definition of
the bijection. It is quite a messy definition though.
For what it is worth I have just thought of some direct bijections of
related forms, with a fairly simple definitions. I seem to recall
having read a comment to this effect last year in sci.math or sci.logic
for some of these.
I will start with bijections defined using continued fractions, ie
those of forms like b1+1/(b2+1/(b3+...)) .
I will take finite continued fractions to have final denominator of
the form bn + 1 . With this version there is existence and uniqueness
of continued fraction representation of rationals in (0, 1) using
finite continued fractions with at least one coefficient and all
coefficients positive integers, continued fractions of form 1/(b1+...)
with leading coefficient in the first denominator.
Also all irrationals in (0, 1) are uniquely represented by infinite
continued fractions with all coefficients positive integers, continued
fractions of form 1/(b1+...) with leading coefficient in denominator.
So using at least one coefficient and all coefficients positive
integers with leading coefficient in denominator, we have existence and
uniqueness of contiued fraction representation for all reals in (0, 1).
Here is another way to describe the finite continued fractions just
mentioned. Define the convergence of continued fractions by taking
finite approximations of form as above, that is with last denominator of
the form bn +1. With this definition of convergence, continued
fractions including 0 coefficients converge.
Given a finite continued fraction, we can form an infinite continued
fraction by appending infinitely many 0 coefficients. Using the above
definition, this infinite continued fraction converges to the same value
as the original finite continued fraction. So we can think of finite
continued fractions as infinite continued fractions with a tail of 0
coefficients.
For the coming definitions, I want to have a notion of "empty
continued fraction", that is the "continued fraction" made from the
empty sequence of coefficients. In fact I will have two incompatable
definitions of this, each helpful toward defining its own bijection.
The first of these definitions will use the last characterization as
motivation.
So for the first definition, the continued fraction induced by the
empty sequence of coefficients is just the infinite all 0 continued
fraction, 1/(0+1/(0+1/(0+...))). Each of the finite approxiamations to
this is 1 : 1/1, 1/(1/1), 1/(1/(1/1)) etc. So in this version
the empty continued fraction is 1.
Previously we had existence and uniqueness of non-empty positive
integer sequence continued fractions to (0, 1). With this new
definition we can extend this to all positive integer sequence
(including empty sequence) continued fractions representation
existence and uniqueness for (0, 1] .
This leads to the first definable bijection, namely from P(positive
integers), the powerset of the postive integers. Given A a subset of
the positive intgers, form a finite or infinite sequence enumerating A
1-1 in increasing order: a1, a2, ... . (A = {} corresponds to the
empty a-sequence).
Define a0 = 0, ie stick 0 at the front of the sequence.
Define a new b-sequence, for an defined let bn = an - a(n-1).
If a1 is defined there is no problem defining bn since we stipulated
a0.
The b-sequence is a sequence of positive integers (since a-sequence
increasing 1-1 and since a0 = 0 and a1 if defined is positive). For
A = {} the b-sequence is the empty sequence.
We biject P(positive integers) to (0, 1] by sending A to the
continued fraction of the b-sequence.
That is the first bijection. We turn now to a second bijection.
Operate as above, but use instead continued fractions of the form
b1+1/(b2+...), ie leading coefficient outside the denominator. For
this version define empty continued fraction again by the 0-padding as
above.
This bijects P(positive integers) to [1, infinity) , with {} going
to 1. This is easy to see from first principles, since this version of
continued fractions is just the respective reciprocals of the previous
1/(b1+...) version, so we are composing the old bijection with
resiprocal, and reciprocal bijects (0, 1] to [1, infinity), matching
1 to 1 so both bijections send {} to 1.
That last view makes this bijection seem a trivial variant on the
first, but it is still of interest since it has a concise direct closed
form description (other form of continued fractions).
So we come to a third bijection. We want to translate the
[1, infinity) domain to [0, infinity), ie the positive reals.
This can be done by redefining a0 = 1 instead of a0 = 0. Then define
the b-sequence accordingly, and repeating everything else we get
non-empty sets bijecting to (0, infinity).
If we retain the earlier definition of empty continued fraction, {}
would still go to 1, same as {1}, ruining injectivity. So for this
version we make a new definition of empty continued fraction.
Consider the continued fractions b1 + 1 vs b1 + 1/(b2 + 1), that
is continued fractions of 1 or respectively 2 coefficients. The
previous pattern generalized toward defining empty continued fraction
was to consider the first as arising from the second by setting b2 = 0.
Instead now consider the first as arising from the second by deleting
the denominator: /(b2 + 1). When the b2 coefficient is dropped, it
takes with it the extra terms associated to it: /(_ + 1).
So the empty continued fraction should be obtained from b1 + 1 by
deleting the b1 and associated terms: ie deleting b1 + 1, leaving
the empty expression. What number does the empty expression denote? 0
of course!
Ie: +5 = 0 +5. Note you might be tempted to similarly use
multiplication to show the empty expression is 1: *5 = 1 *5. But there
is no unary * operation!
Anyway, if this last part is too Zen, just stipulate now the coming
bijection sends {} to 0.
So this bijection: given A subset positive integers, use a0=1 to
define the b-sequence, and take continued fraction (leading coefficient
outside denominator), with empty continued fraction = 0. This bijects
P(positive integers) to [0, infinity) = positive reals.
This bijection has the nice properties: {} |-> 0, {n} |-> n,
finite sets biject exactly to rationals.
So these three continued fraction bijections have bijected
P(positive integers) to each of (0, 1], [1, infinity),
[0, infinity).
Now I will describe a fourth bijection, bijecting P(positive integers)
to [0, 1). This will be based on binary digits and not on continued
fractions.
Consider P(postive integers) as infinite binary sequences,
enumerating the characteristic function. Consider [0, 1) as binary
representations, where 0 repeated tails are always used instead of 1
repeated tails. So we will consider the problem as bijecting all
infinite binary sequences to those infinite binary sequences not
eventually constantly 1.
So I describe how to bijectively associate an infinite binary sequence
to an infinite binary sequence not eventually constantly 1. If the
starting sequence is not eventually constant, leave it unchanged.
If the starting sequence is eventually constant, start the associated
sequence with one bit: the value from the constant tail, then append a
copy of the starting sequence where each bit has been added mod 2 to the
constant tail value. In other words, eventually constantly 0 sequences
are appended unchanged, but eventually constantly 1 sequences have their
flipped version appended: change all digits.
Either way, the output is eventually constantly 0.
Given such an output sequence you can recover the original: take the
subsequence deleting first entry, with each digit added mod 2 to the
first entry. So this last procedure is 1-1 on the domain of eventually
constant sequences.
The range of this procedure on its domain is disjoint from the special
case procedure range on its domain: identity function on sequences not
eventually constant. So the total function is the union of two 1-1
functions with disjoint ranges, so is 1-1.
Now to see this total function is surjective onto all binary sequences
not eventually contantly 1. Such sequences not eventually constant are
hit by the identity part. So consider a sequence eventually constantly
0. Apply the recovery method I wrote earlier: add the first entry
elementwise mod 2 to the subsequence deleting the first entry. This
hits the target under the procedure.
So this fourth procedure is indeed a bijection.
Paul Hines has in an earlier article described a bijection of powerset
to reals: as above use characteristic functions and binary
representations, having a countable set where the obvious mapping is 2
to 1. Use re-indexing corresponding to omega + omega = omega on this
countable part to fix that problem.
Paul's function, and the one obtained by Cantor-Schroeder-Berstein from
the obvious easily defined injections each way, have definitions
quantifying over other powerset elements than the argument being
evaluated. Each of my four solutions above has a simpler definition, in
that the only data being manipulated to evaluate the bijection on a
starting set A is A itself.
My definitions involved various ranges, each choosen to simplify the
definition. From these definitions, further easily definable bijections
to for example all reals could be arranged by compositions with
bijections of my ranges to all reals. Such bijections from my ranges to
all reals can be easily defined.
the_grea...@my-deja.com
Ok, let me put members of P(N) inside the tree, so
we can make a propper comparison.
_{1,2,3}_
_{1,2}_/ P
/ \_{1,2}___ O
_{1}_/ W
/ \ _{1,3}___ E
/ \_{1}___/ R
/ \_{1}_____ S
{}/ E
\ _{2,3}___ T
\ _{2}___/
\ / \_{2}_____ O
\_{}__/ F
\ _{3}_____
\_{}____/ N
\_{}______
In the tree above, each node repressents a set of
natural numbers. Each node has two children, one
child matches the parent, the other includes one
extra member (equal to the depth in the tree).
The way things are drawn, the tree goes off the edge
of the screen. I'll fix this open-ended problem by
closing the tree from the other side. In the
following diagram, N = {1,2,3,...} the set of all
natural numbers and, "\" stands for Set subtraction.
_________N_
P \_N_______
O _____N\{3}_/ \
W \_N_____
E _____N\{2}_ / \
R \_N\{2}___/ \
S ___N\{2,3}_/ \
E \_N_
T _____N\{1}_ /
\_N\{1}___ /
O ___N\{1,3}_/ \ /
F \_N\{1}_/
___N\{1,2}_ /
N \_N\{1,2}_/
_N\{1,2,3}_/
Now, connect these trees, like this:
{1,2,3,4,...} connects to N
{} connects to N\{1,2,3,4,...}
{2,4,6,8,...} connects to N\{1,3,5,7,...}
{1,4,9,16...} connects to N\{2,3,5,6,...}
At this point, I suspect you'll object, "eventhough
the PATHS connect, the NODES do not."
Is that your only objection? If so, please explain
the logic behind that statement.
Nathan the Great
Age 12
the_grea...@my-deja.com
a...@seaman.cc.purdue.edu (Dave Seaman) wrote:
> In article <8iqcoi$21n$1...@nnrp1.deja.com>,
> <the_grea...@my-deja.com> wrote:
> >Cantor's argument starts out as follows
> >(according to the well-known Jourdain's
> >translation):
> >
> > "We have seen that, of the three
> > relations a = b, a < b, b < a,
> > each one exclude the two others..."
> >
> >Thats about as inconspicuous as a Tarantula
> >on Angle Food cake.
> >
> >Cantor, in his infinite wisdom, assumes
> >what he sets out to prove.
[snip]
> In case 3) we can apply the Cantor-Bernstein theorem to conclude that
> there is a bijection between A and B, which means that |A| = |B|.
Dave, you just used the Cantor-Bernstein theorem.
Did you forget what you're trying to prove?
Aren't you putting the cart ahead of the horse?
> Therefore, whether AC holds or not, we can certainly say that 1),
> 2) and 3) are mutually exclusive possiblities for the existence or
> nonexistence of injections between A and B, which is the starting
> point of Cantor's argument.
You say, "which is the starting point of Cantor's argument".
Nice example of "lifting yourself up by the bootstraps."
Dave Seaman
<the_grea...@my-deja.com> wrote:
>> In case 3) we can apply the Cantor-Bernstein theorem to conclude that
>> there is a bijection between A and B, which means that |A| = |B|.
>Dave, you just used the Cantor-Bernstein theorem.
>Did you forget what you're trying to prove?
>Aren't you putting the cart ahead of the horse?
Not at all. I used the Cantor-Bernstein theorem as part of my
explanation of why the proof of Cantor's theorem makes sense. The mere
fact that both theorems have "Cantor" in their name does not mean the
argument is circular. The Cantor-Bernstein theorem is also sometimes
called the Schroeder-Bernstein theorem. Will it make you happier if I
use the Schroeder-Bernstein theorem to explain Cantor's theorem?
>> Therefore, whether AC holds or not, we can certainly say that 1),
>> 2) and 3) are mutually exclusive possiblities for the existence or
>> nonexistence of injections between A and B, which is the starting
>> point of Cantor's argument.
>You say, "which is the starting point of Cantor's argument".
>Nice example of "lifting yourself up by the bootstraps."
Cantor-Schroeder-Bernstein theorem (simplified): If |A| <= |B| and also
|B| <= |A|, then |A| = |B|.
Cantor's theorem: |A| < |P(A)| for all A.
--
Dave Seaman dse...@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
Dave Seaman
> {1,2,3,4,...} connects to N
> {} connects to N\{1,2,3,4,...}
> {2,4,6,8,...} connects to N\{1,3,5,7,...}
> {1,4,9,16...} connects to N\{2,3,5,6,...}
>At this point, I suspect you'll object, "eventhough
>the PATHS connect, the NODES do not."
I don't care how you connect things. Your two trees contain only a
countable subset of P(N) -- namely, the set of all finite subsets of N
(first tree) and the set of all co-finite subsets of N (second tree).
Neither tree contains the set of all even numbers or the set of all
primes, for example.
Lars Henrik Mathiesen
>The way things are drawn, the tree goes off the edge
>of the screen. I'll fix this open-ended problem by
>closing the tree from the other side. In the
>following diagram, N = {1,2,3,...} the set of all
>natural numbers and, "\" stands for Set subtraction.
> _________N_
> P \_N_______
> O _____N\{3}_/ \
> W \_N_____
> E _____N\{2}_ / \
> R \_N\{2}___/ \
> S ___N\{2,3}_/ \
> E \_N_
> T _____N\{1}_ /
> \_N\{1}___ /
> O ___N\{1,3}_/ \ /
> F \_N\{1}_/
> ___N\{1,2}_ /
> N \_N\{1,2}_/
> _N\{1,2,3}_/
Nathan, please tell us on which level of the tree you find these
nodes. (Start at the left and count the root as level zero).
The reason why the set of nodes in the original tree is countable is
that it only contains nodes that correspond to finite subsets of N.
If you disagree with the statement "the original tree only contains
nodes that correspond to finite subsets of N," please tell us how to
locate a node that corresponds to an infinite subset.
(Any way, I'm not sure that your 'completed' tree (not strictly a tree
any more) does what you want. You may want the last level to add the
_last_ element in N, not the first --- and as far as I can see, by
that time there should be about 2^{\omega} branches, not 2).
James Hunter
the_grea...@my-deja.com wrote:
> In article <8iqp1o$7...@seaman.cc.purdue.edu>,
> a...@seaman.cc.purdue.edu (Dave Seaman) wrote:
> > In article <8iqcoi$21n$1...@nnrp1.deja.com>,
> > <the_grea...@my-deja.com> wrote:
> > >Cantor's argument starts out as follows
> > >(according to the well-known Jourdain's
> > >translation):
> > >
> > > "We have seen that, of the three
> > > relations a = b, a < b, b < a,
> > > each one exclude the two others..."
> > >
> > >Thats about as inconspicuous as a Tarantula
> > >on Angle Food cake.
> > >
> > >Cantor, in his infinite wisdom, assumes
> > >what he sets out to prove.
> > >This should be called the Cantor-Bernstein
> > >ASSUMPTION, not THEOREM.
>
> [snip]
>
> > In case 3) we can apply the Cantor-Bernstein theorem to conclude that
> > there is a bijection between A and B, which means that |A| = |B|.
>
> Dave, you just used the Cantor-Bernstein theorem.
> Did you forget what you're trying to prove?
> Aren't you putting the cart ahead of the horse?
>
> > Therefore, whether AC holds or not, we can certainly say that 1),
> > 2) and 3) are mutually exclusive possiblities for the existence or
> > nonexistence of injections between A and B, which is the starting
> > point of Cantor's argument.
>
> You say, "which is the starting point of Cantor's argument".
> Nice example of "lifting yourself up by the bootstraps."
>
> Nathan the Great
> Age 12
That's a recurring problem in logic.
The main difference is that Cantor did lift himself up, and you didn't.
Daryl McCullough
>Ok, let me put members of P(N) inside the tree, so
>we can make a propper comparison.
>
> _{1,2,3}_
> _{1,2}_/ P
> / \_{1,2}___ O
> _{1}_/ W
> / \ _{1,3}___ E
> / \_{1}___/ R
> / \_{1}_____ S
> {}/ E
> \ _{2,3}___ T
> \ _{2}___/
> \ / \_{2}_____ O
> \_{}__/ F
> \ _{3}_____
> \_{}____/ N
> \_{}______
This construction only lists the *finite* subsets of N. The
power set of N includes *all* subsets, whether finite or
infinite. I think it is clear that no infinite set will
appear anywhere in your tree. For example, N is a subset
of itself. Where does N = {0,1,2,...} appear in your tree?
What you have shown is that the set of rationals can
be put into a one-to-one correspondence with the set
of *finite* subsets of N.
Daryl McCullough
CoGenTex, Inc.
Ithaca, NY
George Greene
: <logi...@wolfenet.com> wrote:
:
: >I was recently in an argument about
: >creating a bijection between the real numbers
: >and the power set of the integers.
: >I, probably incorrectly, thought that
: >such a bijection couldn't exist.
: >(Several people gave such bijections,
: >but they were over my head).
Not at all surprising; that's not your
fault; they are not natural if your paradigm
is decimal representations.
: >My thoughts go like this:
: >
: >It is generally taught that every real number
: >has a decimal representation.
: >
: >I assume that it is fairly straight forward to show
: >that the set of decimal numbers has the same
: >cardinality as the power set of the integers.
: >
: >The problem is that some real numbers have
: >two different decimal representations.
: >Doesn't this mean that there are fewer real
: >numbers than there are decimal representations?
No, it doesn't.
The reason why you are confused is that you are thinking
about finite sets. When both sets are finite, YES, it IS
the case that (if every A has at least 1 B, and)
if some A's have two different B's,
then there must be fewer A's than B's.
But in the case of infinite sets, this is sort of obviously
Not True. So obviously that it sort of can't be proved and therefore
gets to be stipulated as a *definition* of "infinite set"
in some treatments: a set is [Dedekind-]infinite iff there is a bijection
between it and a proper subset of itself (i.e., if it is simultaneously
both the same-size-as AND "smaller" than itself; this definition
declares the same-size appearance to be reality and the smaller-than
appearance to be illusory).
Here are two simple examples:
consider the set of all natural numbers (0,1,2,...)
(non-negative integers; these are all finite, but the set of all
of them is infinite). Now, consider the "smaller" set starting
with 1 (it is smaller by 1 element; 0 has been left out).
This set (call it N1) is not actually smaller; there is a bijection
between it and N0 (the original set):
f(n0)=n0+1 takes any member of N0 to a corresponding member of N1;
and its inverse g(n1)=n1-1 takes any member of N1 to a corresponding
member of N0.
For the second example, which addresses your 2-for-1 question more
directly: Let h(n)= (n+1)/2, rounding up. So h(0)=h(1)=1, h(2)=h(3)=2,
h(4)=h(5)=3,h(6)=h(7)=4, etc. Here, clearly, h maps two
elements of N0 to each element of N1. But the existence of this
2-for-1 mapping doesn't mean N0 is twice as big; as the PREVIOUS
example shows, there is ALSO a 1-1 bijection between N0 and N1,
so DESPITE the fact that some N0s have 2 N1s under h, N0 and N1
are STILL the same size.
--
---
"There are too many men and too many computer people."
--- Regis Philbin, profiling his contestants on
"Who Wants To Be A Millionaire?"
the_grea...@my-deja.com
a...@seaman.cc.purdue.edu (Dave Seaman) wrote:
> >Dave, you just used the Cantor-Bernstein theorem.
> >Did you forget what you're trying to prove?
> >Aren't you putting the cart ahead of the horse?
>
> part of my explanation of why the proof of Cantor's
> theorem makes sense. The mere fact that both theorems
> have "Cantor" in their name does not mean the argument
> is circular. The Cantor-Bernstein theorem is also
> sometimes called the Schroeder-Bernstein theorem.
> Will it make you happier if I use the
> Schroeder-Bernstein theorem to explain Cantor's
> theorem?
Very clever, Dave. You almost completely conceal your
previous blunder, and make me look like a fool who doesn't
know the difference between those two theories. But you
forgot one thing - you can't change the record. And the
record shows it was YOU, not I, that was confused. Below
is the thread history, which proves it:
[Virgil]
> There is a theorem, whose name I forget, which says that given
> injections f:A -> B and g:B -> A, there is a bijection h:A -> B.
[Larry Taylor]
> The Cantor-Schroeder-Bernstein Theorem.
[Nathan the Great]
> Cantor's argument starts out as follows
> (according to the well-known Jourdain's translation):
>
> "We have seen that, of the three relations a = b,
> a < b, b < a, each one exclude the two others..."
[Dave Seaman]
>Wrong. What is to be proved is that for every A, |A| < |P(A)|.
>That statement does not appear anywhere in the statement you have
>quoted.
Gotcha! Thats not the Schroeder-Bernstein theorem - its Cantor's
theorem about power sets.
Q.E.D.
Come on Dave, I'm only a kid. You shouldn't have to use
underhanded tactics to win arguments against me.
Nathan the Great
Age 12
Torkel Franzen
> Come on Dave, I'm only a kid.
Yes, and you only weigh four pounds. Nevertheless, the story is that
you are a quite a bully in the schoolyard, forcing kids only half your
size to recite Cantor while standing on their heads. Is this true?
the_grea...@my-deja.com
Torkel Franzen <tor...@sm.luth.se> wrote:
> the_grea...@my-deja.com writes:
> >Cantor's argument starts out as follows
> >(according to the well-known Jourdain's translation):
> >
> > "We have seen that, of the three relations a = b,
> > a < b, b < a, each one exclude the two others..."
> >
> >Cantor, in his infinite wisdom, assumes what he sets out to prove.
>
> a WILD RANT. You're getting to be an old softie, aren't you?
>
I was trying to draw your attention to Cantor's assumption that
infinite sets can be compared |a| = |b|, |a| < |b|, |b| > |a|,
just like finite sets, with each relation excluding the other two.
Cantor uses unsound logic when he treats this assumption as if
it were a theorem. Let me remind you, proofs are derived from
axioms and theorems, not from assumptions.
Also, infinite sets can be put in bijection with subsets of
themselves. To me, this implies they are simultaneously
cardinally bigger and smaller then themselves. So I don't
see the necessity of those relations excluding each other.
Torkel Franzen
> Cantor uses unsound logic when he treats this assumption as if
> it were a theorem. Let me remind you, proofs are derived from
> axioms and theorems, not from assumptions.
What sort of brownnosing is this? Are you again suggesting that
Cantor uses assumptions? Cantor doesn't use assumptions, he uses
FLAT OUT WANKING. You're obviously just another Cantor stooge.
I think you're a two-year-old trained by Cantorians.
Lee Rudolph
Wait. I thought it was the seed of Abraham that was uncountable,
and now you're telling me it's the seed of Cantor?
Mathematics is so confusing.
Lee Rudolph, refraining from mentioning the sporadic simple group
of O'Nan
Dik T. Winter
> Very clever, Dave. You almost completely conceal your
> previous blunder, and make me look like a fool who doesn't
> know the difference between those two theories.
Very clever, accusing somebody of doing something you do yourself.
> [Nathan the Great]
> > Cantor's argument starts out as follows
> > (according to the well-known Jourdain's translation):
> >
> > "We have seen that, of the three relations a = b,
> > a < b, b < a, each one exclude the two others..."
You snipped something important here:
> > Thats about as inconspicuous as a Tarantula on Angle Food cake. Cantor,
> > in his infinite wisdom, assumes what he sets out to prove.
Now, where does he assume what he sets out to prove? As Dave wrote:
> > Wrong. What is to be proved is that for every A, |A| < |P(A)|.
> > That statement does not appear anywhere in the statement you have
> > quoted.
...
> Come on Dave, I'm only a kid. You shouldn't have to use
> underhanded tactics to win arguments against me.
Even kids should not have to use underhanded tactics to win arguments.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Dik T. Winter
> Also, infinite sets can be put in bijection with subsets of
> themselves. To me, this implies they are simultaneously
> cardinally bigger and smaller then themselves. So I don't
> see the necessity of those relations excluding each other.
When you use terminology you should also use the definitions.
As Dave Seaman has put it:
> 1) There is an injection from A to B, but none from B to A.
> 2) There is an injection from B to A, but none from A to B.
> 3) There are injections in both directions.
> 4) There is no injection in either direction.
> In case 1) we say that |A| < |B|.
> In case 2) we say that |A| > |B|.
> In case 3) we can apply the Cantor-Bernstein theorem to conclude that
> there is a bijection between A and B, which means that |A| = |B|.
These are the definitions used by mathematicians, and with these
definitions the exclusion holds. Or can you give an example where
simultaneously (2) and (3) hold?
Dave Seaman
<the_grea...@my-deja.com> wrote:
>Very clever, Dave. You almost completely conceal your
>previous blunder, and make me look like a fool who doesn't
>forgot one thing - you can't change the record. And the
>record shows it was YOU, not I, that was confused. Below
>is the thread history, which proves it:
I will admit to being confused by the thread title and by your
long-standing obsession with Cantor's diagonal proof into thinking that
that was what you were discussing.
>[Virgil]
>> There is a theorem, whose name I forget, which says that given
>> injections f:A -> B and g:B -> A, there is a bijection h:A -> B.
>[Larry Taylor]
>> The Cantor-Schroeder-Bernstein Theorem.
>[Nathan the Great]
>> Cantor's argument starts out as follows
>> (according to the well-known Jourdain's translation):
>> "We have seen that, of the three relations a = b,
>> a < b, b < a, each one exclude the two others..."
Taken out of context, it's hard to tell whether this is an introduction
to Cantor's theorem or an introduction to the C-S-B theorem.
>Come on Dave, I'm only a kid. You shouldn't have to use
>underhanded tactics to win arguments against me.
I apologize. Now, back to the argument. My earlier comments still
apply, even if you ignore the part about power sets. If you like, we can
enumerate the possibilities this way. Here A and B are arbitrary sets.
1) There is an injection from A to B, but no injection from B to A.
2) There is an injection from B to A, but no injection from A to B.
3) There is a bijection from A to B, and therefore there are injections
in both directions.
3a) There are injections in both directions, but no bijection.
4) There are no injections in either direction.
The C-S-B theorem says case 3a) never happens, but we don't need to know
that right now. The axiom of choice implies that 4) doesn't happen, but
we don't need that, either. All that matters is that cases 1), 2), and
3) are mutually exclusive, and we don't need any theorem to prove that.
Given two sets, either an injection exists, or it doesn't.
Now look again at the statement you objected to.
>> "We have seen that, of the three relations a = b,
>> a < b, b < a, each one exclude the two others..."
Did you check out the "we have seen that" part of that statement? If you
did, you should have found an explanation similar to the one I gave. In
case 1) we say (by definition) that |A| < |B|. In case 2) we say that
|B| < |A|. In case 3) we say that |A| = |B|. In cases 3a) and 4) we
would not be able to say anything about the comparison of sizes -- the
sets would be incomparable.
Nowhere did Cantor say that 1), 2) and 3) are the *only* three
possibilities. He merely said that they are mutually exclusive. If you
throw a die, the event that it comes up 1 and the event that it comes up
2 are mutually exclusive, even though other possibilities exist. That is
all he said in the statement you quoted. It is not an assumption; it is
a simple fact of logic.
david_...@my-deja.com
the_grea...@my-deja.com wrote:
> In article <vcbaegf...@beta13.sm.luth.se>,
> Torkel Franzen <tor...@sm.luth.se> wrote:
> > the_grea...@my-deja.com writes:
> > >(according to the well-known Jourdain's translation):
> > >
> > > "We have seen that, of the three relations a = b,
> > > a < b, b < a, each one exclude the two others..."
> > >
> > >Cantor, in his infinite wisdom, assumes what he sets out to prove.
> >
> > a WILD RANT. You're getting to be an old softie, aren't you?
> >
>
> I was trying to draw your attention to Cantor's assumption that
> infinite sets can be compared |a| = |b|, |a| < |b|, |b| > |a|,
> just like finite sets, with each relation excluding the other two.
A few suggestions: (i) download a better sarcasm detector
somewhere, (ii) learn what the words "we have seen that" mean.
> Cantor uses unsound logic when he treats this assumption as if
> it were a theorem. Let me remind you, proofs are derived from
> axioms and theorems, not from assumptions.
>
> Also, infinite sets can be put in bijection with subsets of
> themselves. To me, this implies they are simultaneously
> cardinally bigger and smaller then themselves. So I don't
> see the necessity of those relations excluding each other.
Oh yeah: also you should bone up on what a "definition"
is. What something _actually_ implies depends on the relevant
definitions - your "To me, this implies" is ignoring the
definitions.
the_grea...@my-deja.com
a...@seaman.cc.purdue.edu (Dave Seaman) wrote:
> In article <8isu72$sot$1...@nnrp1.deja.com>,
> <the_grea...@my-deja.com> wrote:
> >Now, connect these trees, like this:
>
> > {1,2,3,4,...} connects to N
> > {} connects to N\{1,2,3,4,...}
> > {2,4,6,8,...} connects to N\{1,3,5,7,...}
> > {1,4,9,16...} connects to N\{2,3,5,6,...}
>
> >At this point, I suspect you'll object, "eventhough
> >the PATHS connect, the NODES do not."
>
> I don't care how you connect things.
Dave, why should I continue trying to teach you?
Learning takes effort. Pay attention!
> Your two trees contain only a countable subset
> of P(N) -- namely, the set of all finite subsets
> of N (first tree) and the set of all co-finite
> subsets of N (second tree). Neither tree
> contains the set of all even numbers or the set
> of all primes, for example.
So, you think my tree doesn't contain the set of all
even numbers. Thats a silly thing to say, considering
that my tree contains all the members of P(N). Did you
(blinded by Cantor) even bother to look for it? Let
me remind you, my tree is infinitely (countable) deep.
And it branches, without exception, for its entire
infinite depth. Do you understand?
...
The entire tree can be mapped to an infinitely dimensioned
array. First, each level (depth in the decision tree)
gets paired with its corresponding dimension. Next, for
each path through the tree, assign binary digits
(0 or 1) corresponding to the branches (up/down) that
were taken, at every depth. Using this approach, the path
to any subset of N (member of P(N)) can be converted
directly into a infinite binary series, and that series
can be used to index an infinite dimension array.
Example:
{} = Tree(0,0,0,0,0,0,0,...)
{1,2,3,4,...} = Tree(1,1,1,1,1,1,1,...)
{1,3,5,7,...} = Tree(1,0,1,0,1,0,1,...)
Now you'll tell me, "infinite dimensions are laughable."
This objection is easily swept aside. Just interpret
the infinite dimension series as a fractional binary number.
Using your example, the Set of all even numbers {2,4,6,8...}
becomes "0101010..." which is 0 + 1/4 + 0 + 1/16 + 0 + 1/64
+ ... = 1/3. Finally, by using Cantors zig-zag bijection
(see below), of N to Q, in reverse, we arrive at the
natural number 6.
Examples:
Even numbers = Tree(0,1,0,1,0,1,0,...) = 1/3 = 6
Odd numbers = Tree(1,0,1,0,1,0,1,...) = 2/3 = 8
{2} = Tree(0,1,0,0,0,0,0,...) = 1/4 = 7
So, in the examples above, instead of infinite dimensions,
just one is required.
Cantor's zig-zag bijection
--------------------------
1/1 2/1 3/1 4/1 5/1
1/2 2/2 3/2 4/2
1/3 2/3 3/3
1/4 2/4
1/5
N: 1, 2, 3, 4, 5, 6, 7, 8, 9 ...
Q: 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2 ...
[Now, how long before someone makes irrational objections?]
Nathan the Great
Age
the_grea...@my-deja.com
tho...@diku.dk (Lars Henrik Mathiesen) wrote:
> the_grea...@my-deja.com writes:
>
> >The way things are drawn, the tree goes off the edge
> >of the screen. I'll fix this open-ended problem by
> >closing the tree from the other side. In the
> >following diagram, N = {1,2,3,...} the set of all
> >natural numbers and, "\" stands for Set subtraction.
>
> > _________N_
> > P \_N_______
> > O _____N\{3}_/ \
> > W \_N_____
> > E _____N\{2}_ / \
> > R \_N\{2}___/ \
> > S ___N\{2,3}_/ \
> > E \_N_
> > T _____N\{1}_ /
> > \_N\{1}___ /
> > O ___N\{1,3}_/ \ /
> > F \_N\{1}_/
> > ___N\{1,2}_ /
> > N \_N\{1,2}_/
> > _N\{1,2,3}_/
>
> Nathan, please tell us on which level of the tree you find these
> nodes. (Start at the left and count the root as level zero).
Start at the first level, from the right. To count the nodes
of both trees, take turns hopping back and forth between them.
Example:
Node: {}, N, {1}, N, {}, N\{1}, {1,2}, N, {1}, N\{2}, ...
N: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
> The reason why the set of nodes in the original tree is countable is
> that it only contains nodes that correspond to finite subsets of N.
No, see my reply to Dave Seaman.
It shows specific examples using infinite subsets of N.
> If you disagree with the statement "the original tree only contains
> nodes that correspond to finite subsets of N," please tell us how to
> locate a node that corresponds to an infinite subset.
Again, see my post to Dave.
> (Any way, I'm not sure that your 'completed' tree (not strictly a tree
> any more) does what you want. You may want the last level to add the
> _last_ element in N, not the first --- and as far as I can see, by
> that time there should be about 2^{\omega} branches, not 2).
Look at the tree again. N appears on more than just the 'last' level,
N appears on every level. And why do you say, "last element to add",
when it is the "first element to remove?" Did you notice that {1},
{2}, {1,2}, {4,7,19}, etc. appear not once, but infinitely often in
my tree? This suggests that my tree contains infinitely more nodes
than there are finite subsets of N.
Nathan the Great
Age 12
the_grea...@my-deja.com
da...@cogentex.com (Daryl McCullough) wrote:
> Nathan says...
>
> >Ok, let me put members of P(N) inside the tree, so
> >we can make a propper comparison.
> >
> > _{1,2,3}_
> > _{1,2}_/ P
> > / \_{1,2}___ O
> > _{1}_/ W
> > / \ _{1,3}___ E
> > / \_{1}___/ R
> > / \_{1}_____ S
> > {}/ E
> > \ _{2,3}___ T
> > \ _{2}___/
> > \ / \_{2}_____ O
> > \_{}__/ F
> > \ _{3}_____
> > \_{}____/ N
> > \_{}______
>
> This construction only lists the *finite* subsets of N.
See my post to Dave.
> The power set of N includes *all* subsets, whether finite or
> infinite. I think it is clear that no infinite set will
> appear anywhere in your tree. For example, N is a subset
> of itself. Where does N = {0,1,2,...} appear in your tree?
Pay attention! There are TWO trees. N is the first node in
the second tree. But N is also the 2nd, 4th, 8th, etc. node
As a matter of fact, every set that appears in either of these
trees, appears infinitely often. Therefore, these trees MUST
have infinitely more nodes than there are finite subsets of N.
Pertti Lounesto
> Learning takes effort. Pay attention!
Nathan, while you know all about infinity, let me
benefit the opportunity, and ask you the following.
We know that a set is genuinly smaller than the set
of its subset, so for instance R < P(R). Denote the
set of finite sets of real numbers by F(R) and the
set of countable sets of real numbers by C(R).
Is R < F(R) < C(R) < P(R)? Why? Why not?
the_grea...@my-deja.com
Pertti Lounesto <plou...@pp.htv.fi> wrote:
> the_grea...@my-deja.com wrote:
>
> > Learning takes effort. Pay attention!
>
> Nathan, while you know all about infinity, let me
> benefit the opportunity, and ask you the following.
>
> We know that a set is genuinly smaller than the set
> of its subset, so for instance R < P(R).
Hogwash! Close your trap, penis breath! Time to suck
your loverboy, the supreme evil, Dr. Ullrich. You make
me puke, Cantorian scum.
Nathan the Greatly annoyed
James Hunter
Pertti Lounesto wrote:
> the_grea...@my-deja.com wrote:
>
> > Learning takes effort. Pay attention!
>
> Nathan, while you know all about infinity, let me
> benefit the opportunity, and ask you the following.
>
> We know that a set is genuinly smaller than the set
> of its subset, so for instance R < P(R). Denote the
> set of finite sets of real numbers by F(R) and the
> set of countable sets of real numbers by C(R).
> Is R < F(R) < C(R) < P(R)? Why? Why not?
Why? Just because.
Why not, because set inclusion has nothing to do with inequalities,
unless we speaking of how many morons are included in the
set of Earth philosophers.
Dave Seaman
>In article <8it6n5$8...@seaman.cc.purdue.edu>,
>Dave, why should I continue trying to teach you?
Your patience is admirable.
>> Your two trees contain only a countable subset
>> of P(N) -- namely, the set of all finite subsets
>> of N (first tree) and the set of all co-finite
>> subsets of N (second tree). Neither tree
>> contains the set of all even numbers or the set
>> of all primes, for example.
>So, you think my tree doesn't contain the set of all
>even numbers. Thats a silly thing to say, considering
>that my tree contains all the members of P(N). Did you
>(blinded by Cantor) even bother to look for it? Let
>me remind you, my tree is infinitely (countable) deep.
>And it branches, without exception, for its entire
>infinite depth. Do you understand?
Yes. I understand that your tree has countably many levels, each at a
finite depth. Each level contains a finite number of nodes, and
therefore the total number of nodes in the tree is countable.
>The entire tree can be mapped to an infinitely dimensioned
>array. First, each level (depth in the decision tree)
>gets paired with its corresponding dimension. Next, for
>each path through the tree, assign binary digits
>(0 or 1) corresponding to the branches (up/down) that
>were taken, at every depth. Using this approach, the path
>to any subset of N (member of P(N)) can be converted
>directly into a infinite binary series, and that series
>can be used to index an infinite dimension array.
By your description, the path to any given node is finite in length.
Therefore, each node is associated with a *finite* binary series, not an
infinite one.
It's true that a path from the root is infinitely long, but there is no
node lying at the end of it. If you stop at a node somewhere in the
tree, then you have taken the path to only a finite depth.
>Example:
> {} = Tree(0,0,0,0,0,0,0,...)
> {1,2,3,4,...} = Tree(1,1,1,1,1,1,1,...)
> {1,3,5,7,...} = Tree(1,0,1,0,1,0,1,...)
Those are infinitely long paths. There is no node at the end of such a
path. For which natural number n can you find the set of all odd numbers
in a node at depth n?
>Now you'll tell me, "infinite dimensions are laughable."
Why would I tell you that? We are dealing with infinite sets, after all.
It's just that you don't understand the definition of countability.
Mapping every member of P(N) to some member of a tree-like structure
having uncountably many levels is perfectly possible, but it does not
demonstrate that P(N) is countable. To do that, you need to restrict
your tree to countably many levels.
Daryl McCullough
It doesn't matter whether there is only one tree, or two, or a million.
Any countable number of trees can be combined into a single tree. And there
is no finitely branching tree such that the nodes are labelled with
all the subsets of N.
You need to keep straight the difference between the *nodes*
of a tree and the *paths* through the tree. In a binary branching
tree, there are only countably many nodes, but there are uncountably
many paths. There is only a node for each *finite* path.
Erik Max Francis
> Hogwash! Close your trap, penis breath! Time to suck
> your loverboy, the supreme evil, Dr. Ullrich. You make
> me puke, Cantorian scum.
>
> Nathan the Greatly annoyed
> Age 12
Yeah, that sounds about age twelve, all right.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/ \ I won't pretend / That I intend to stop living
\__/ Sade
Physics reference / http://www.alcyone.com/max/reference/physics/
A physics reference.
Ross A. Finlayson
Pertti Lounesto wrote:
> the_grea...@my-deja.com wrote:
>
> > Learning takes effort. Pay attention!
>
> Nathan, while you know all about infinity, let me
> benefit the opportunity, and ask you the following.
>
> We know that a set is genuinly smaller than the set
> of its subset, so for instance R < P(R). Denote the
> set of finite sets of real numbers by F(R) and the
> set of countable sets of real numbers by C(R).
> Is R < F(R) < C(R) < P(R)? Why? Why not?
By the same token, is not the set of reals in base 10 containing 10^10 -
2^10 more numbers for a ten digit number than the set in base 2? Is
there not a sufficently large number n in N that n^p - 2 ^p is greater
than 2^2^p for any positive n and p greater than 1?
We can prove that any finite set R has a powerset (in binary predicate
classical logic using Zermelo-Fraenkel axioms) with a cardinality that
is 2 exponentaited to the power of the cardinality of R, presumably
using von Neumann binary ordinals. Yet, when any two infinite sets are
compared, this relation does not apply. Why? Because there are always
more elements, so any diagonal argument is invalid.
Well, I can say this, yet how do I prove it? The place to start would
be the axiom of infinity. It says that there exists an infinite set,
more or less. The power set axiom says that for any set X there exists
P(X). Null is included in the powerset else it would be a 2^n-1.
Cantor's theorem says |P(X)| > |X| for any set X. While it might be
that the size of a binary predicate von Neumann ordinal set is log 2
|P(X)|, or log b |P(X)| for predicate base b, that theorem can't prove
it because the applies the diagonal method while there is a surjection
from any infinite set onto any other infinite set.
This gets us into the embeddings of R* on R, with some "numbers"
normally not called "real."
So anyways, the size of each of a set of integers shows that the
powerset of its powerset has a size of 2^n. If you think about it in
terms of scalar infinity, 2^n > n for any integer n when the set
elements are in base 2, (id est, b^p). Agreeably, any integer number
can be represented in base 2. Then there are the reals, a somewhat
different set. Getting a finite set of reals in the first place is
somewhat of an issue, heh heh heh.
It is almost certain that those looking to find the count of the reals
started listing as many as they could and by simple observation saw that
for any given number of contiguous digits in a given base, that they
could get b^p.
Here's one for you, ZF says that there is no set of all sets, thus no
set of all elements, thus for any set, there exists at least one set
with a cardinality between that of the set and its powerset, in fact an
infinite amount of them, by simply adding some element not in the set.
So what is left from that? Here is something, consider [0,1] on R. So,
is this supposed to have 2^|N| reals? Well, any one of us can start a
list of the reals in any higher base that would be larger. Is [0,2]
described as having 2 * 2^|N| reals? Well, no. Does it have twice as
many reals as [0,1]? Yes it does.
So, basically, the set of the reals from zero to one has greater than
2^|N| members, with its cardinality being less than nothing.
Alternately, |R[0, 1]|>2^|N|.
By this reasoning, there are many, many rationals between zero and one
inclusive of each, and many, many irrationals, and many, many
transcendentals. Also, between zero and two inclusive of each , there
are twice as many of each. Diagonalize that.
Ross
Dennis Paul Himes
>
> We know that a set is genuinly smaller than the set
> of its subset, so for instance R < P(R).
I assume you mean |R| < |P(R)|. (I.e. the relation is between the
cardinalities rather than between the sets.)
> Denote the
> set of finite sets of real numbers by F(R) and the
> set of countable sets of real numbers by C(R).
> Is R < F(R) < C(R) < P(R)? Why? Why not?
It's not too hard to see that |R| <= |F(R)| <= |C(R)| <= |P(R)|. Since
|R| < |P(R)|, at least one of those inequalities has to be strict. However,
if all three of them were strict, or even two of them, then you would have a
refutation of the Generalized Continuum Hypothesis.
============================================================================
Dennis Paul Himes <> den...@sculptware.com
http://www.connix.com/~dennis/dennis.htm
Disclaimer: "True, I talk of dreams; which are the children of an idle
brain, begot of nothing but vain fantasy; which is as thin of substance as
the air." - Romeo & Juliet, Act I Scene iv Verse 96-99
Lars Henrik Mathiesen
That an answer to a slightly different question than the one I asked,
but never mind.
>> The reason why the set of nodes in the original tree is countable is
>> that it only contains nodes that correspond to finite subsets of N.
>No, see my reply to Dave Seaman.
>It shows specific examples using infinite subsets of N.
OK. Then see Dave's reply to your reply. I want to try another tack.
I will assume the existence of your graph (reserving the word tree for
the usual definition).
By your own words, there is a unique path P from the node labelled {}
on the left to the node labelled N on the right, corresponding to the
set {2, 4, 6, ...} (all even integers).
Let the set of nodes on P be V. Partition V like this: V_f contains
the nodes labelled with finite subset of N; V_c contains the nodes
labelled with the complement of a finite subset of N; and V_i contains
nodes labelled with infinite subsets of N whose complements are also
infinite. The node labelled {2, 4, 6, ...}, if it exists, is in V_i.
You can esily see that adding an element to the label of a node in V_c
or V_i can never get the label of a node in V_f. --- so when traversing
P from the left, once we see a node that's not in V_f, we never see
another node from that partition.
Likewise, removing an element from the label of a node in V_f or V_i
can never give the label of a node in V_c --- so when traversing P
from the right, once we see a node that's not in V_c, we never see
another node from that partition.
This proves that going from left to right, we see all the V_f nodes,
then all V_i nodes (if any), and lastly all the V_c nodes, without any
mixing.
Now here's some questions that I can't answer, because I seem to be
unable to have the same insights as you:
When traversing P from the left, what is the label of the last node of
V_f that we encounter? What is the label of the node after that? Is it
in V_i or V_c?
Symmetrically, what is the label of the first node on P that is in
V_c, and what is the label of the node before that? Is it in V_i or
V_f?
Don't waffle on this. These questions are very like the question 'what
is the last integer'. If you find them difficult to answer, that
should perhaps suggest to you that the construction of your graph
isn't as well-defined as you may have thought.
>Did you notice that {1}, {2}, {1,2}, {4,7,19}, etc. appear not once,
>but infinitely often in my tree? This suggests that my tree contains
>infinitely more nodes than there are finite subsets of N.
I did. The original tree has the same property: Each finite subset
occurs as a label countably many times. Since there are countably many
finite subsets, that still leaves a countable set of nodes.
Richard Carr
:Date: Sat, 24 Jun 2000 20:02:36 +0200
:From: Pertti Lounesto <plou...@pp.htv.fi>
:Newsgroups: sci.logic, sci.math
:Subject: Re: cardinality of the power set of the integers
:
:the_grea...@my-deja.com wrote:
:
:> Learning takes effort. Pay attention!
:
:Nathan, while you know all about infinity, let me
:benefit the opportunity, and ask you the following.
:
:We know that a set is genuinly smaller than the set
:of its subset, so for instance R < P(R). Denote the
:set of finite sets of real numbers by F(R) and the
:set of countable sets of real numbers by C(R).
:Is R < F(R) < C(R) < P(R)? Why? Why not?
:
This is a good question for Nathan (and for Ross)- a bonus is that the
answers (yes or no) to each inequality are independent of the axiom of
choice.
Mike Oliver
Richard Carr wrote:
> :We know that a set is genuinly smaller than the set
> :of its subset, so for instance R < P(R). Denote the
> :set of finite sets of real numbers by F(R) and the
> :set of countable sets of real numbers by C(R).
> :Is R < F(R) < C(R) < P(R)? Why? Why not?
>
> This is a good question for Nathan (and for Ross)- a bonus is that the
> answers (yes or no) to each inequality are independent of the axiom of
> choice.
Not quite. In models of ZF+AD, there are more countable sets
of reals than there are reals.
Virgil
>the_grea...@my-deja.com wrote:
>
[snip]
Dear Pertti,
You may not have been active when Nathan, then claiming to be 11, burst
upon the scene.
Before you waste your time trying to educate him, I advise you to read
some of his old postings.
--
Virgil
vm...@frii.com
Richard Carr
:Date: Sat, 24 Jun 2000 16:31:26 -0700
:From: Mike Oliver <oli...@math.ucla.edu>
:Newsgroups: sci.logic, sci.math
:Subject: Re: cardinality of the power set of the integers
:
:
:
:
Ah, I guess I was assuming countable choice in fact (although not full AC).
Apollo Hogan
Mike Oliver <oli...@math.ucla.edu> wrote:
>
>
>Richard Carr wrote:
>> :We know that a set is genuinly smaller than the set
>> :of its subset, so for instance R < P(R). Denote the
>> :set of finite sets of real numbers by F(R) and the
>> :set of countable sets of real numbers by C(R).
>> :Is R < F(R) < C(R) < P(R)? Why? Why not?
>>
>> This is a good question for Nathan (and for Ross)- a bonus is that the
>> answers (yes or no) to each inequality are independent of the axiom of
>> choice.
>
>Not quite. In models of ZF+AD, there are more countable sets
>of reals than there are reals.
Wait, isn't it true that ZF+AD implies dependent choice, allowing us to
code up any countable set of reals into a single real, this giving
an embedding of C(R) into R?
--Apollo Hogan
student, UC Berkeley
Ross A. Finlayson
Richard Carr wrote:
> On Sat, 24 Jun 2000, Pertti Lounesto wrote:
>
> :Date: Sat, 24 Jun 2000 20:02:36 +0200
> :From: Pertti Lounesto <plou...@pp.htv.fi>
> :Newsgroups: sci.logic, sci.math
> :Subject: Re: cardinality of the power set of the integers
> :
> :the_grea...@my-deja.com wrote:
> :
> :> Learning takes effort. Pay attention!
> :
> :Nathan, while you know all about infinity, let me
> :benefit the opportunity, and ask you the following.
> :
> :We know that a set is genuinly smaller than the set
> :of its subset, so for instance R < P(R). Denote the
> :set of finite sets of real numbers by F(R) and the
> :set of countable sets of real numbers by C(R).
> :Is R < F(R) < C(R) < P(R)? Why? Why not?
> :
>
> This is a good question for Nathan (and for Ross)- a bonus is that the
> answers (yes or no) to each inequality are independent of the axiom of
> choice.
Hi,
You mention my name, thus I will write on this thread.
If the set of finite sets of real numbers is made, that means each each
set in F(R) has a set of real numbers, where each real number is somehow
constructed from a von Neumann ordinal, because you can't make anything
else with them, that is to say, it's difficult to make many a real number
because some infinite quantity of the irrationals have constructing
sequences of digits or through von Neumann ordinals, where as usual 0={},
1={{}}, etcetera.
So first, it is required that there be a set with one real number as an
element. If the real number is also on N, that is not a problem, as any
number on N can be represented in a variety of bases in von Neumann
ordinal-like representation as was shown in the thread about Base, which
is an ongoing development, where also was explored multivalent powersets
for bases other than two. So, I will say F(R)=F(N), because everything
else on R is infinite, that is I(R) != I(N).
See:
http://forum.swarthmore.edu/epigone/sci.math/lultwelflol
In particular:
http://forum.swarthmore.edu/epigone/sci.math/lultwelflol/3yfn7n...@forum.mathforum.com
Also, see:
http://forum.swarthmore.edu/epigone/sci.math/whandbayzen
So then you talk about the infinite set of real numbers, C(R), which I
above called I(R). R and N are subsets of C(R).
"Is R < F(R) < C(R) < P(R)? Why? Why not?"
R is greater than F(R). R = C(R). P(R) is greater than R, but in that
diagonal context, so is R+1, or anything that is not bijective on R, which
means having a functional relationship with one value for each element of
the domain yielding each element of the codomain, but you don't have to
say which one.
So, I would say F(R) < R = I(R).
Now, about this whole issue of what is infinity and whatnot, let me tell
you, I don't know a single functional result from calling a set countable
or uncountable except to know whether to store it as an integer or a float
when it is stored in the database. Supposedly, Banach proved that a given
sphere can upon be operated thus two equal spheres, or rather, balls, are
made from the points of it, a conundrum for those that say that
|P(X)|=2^|X| implies anything about the reals, some even call it
paradoxical, but not me, as I have proved before that there are no
paradoxes and that they imply inconsistency.
So, I suggest you read also the alternate opinion, those sharp minds that
would find novelty are sharp enough to have read the status quo.
One other thing, if don't have the talent or admission of time to post
actual mathematics to sci.math, then are not worthy. Noone cares to read
tripe.
Anyways, my opinion is simple enough: I state that each infinite set is
equivalent according to the diagonal method, but, if you read the third
link above about assigning an infinite quantity to a variable, you will
see that it is obvious and intuitive that infinital quantities are used
all the time.
Now, like I was saying, between zero and one, the integers, inclusive of
zero and not one, there are more than (>1)^oo reals. What that new
notation means is if you use non-integer base in numeric representation,
for example, base 1.5, then the number of reals in that interval is
greater than the quantity infinitesimally larger than one exponentiated to
the scalar infinity power.
So, I am going to think about this math more, as I do, and I am going to
post it on my own threads and others besides this one and those like it
where is posted legitimate and perhaps even rational cogent thought,
about, that's right, mathematics.
Here's a hint: empty set, negative.
Always remember, in this context, you are what you write or denote.
Ross
Mike Oliver
Richard Carr wrote:
> :Not quite. In models of ZF+AD, there are more countable sets
> :of reals than there are reals.
> :
>
> Ah, I guess I was assuming countable choice in fact (although not full AC).
You need a bit more than that. ZF+DC+AD is consistent provided
ZF+AD is, and DC is stronger than countable choice.
The direct proof you probably have in mind gets an injection
from "countable sets of reals" into reals by coding a countable
set of reals as a real. But the coding depends on the map
verifying that the set of reals is countable, and for any given
countable set of reals, there are continuum-many such maps. So
I don't know how to make this proof go through with less than
"the reals may be wellordered".
I'm almost sure, though, that you can't recover a wellordering
of the reals from an injection from P_w1(R) into R. So probably
there is some weaker form of choice that would work. I don't
know what it would be. Maybe one of the results about ultrafilters
or prime ideals.
Richard Carr
I was using (2^aleph_0)^aleph_0=2^aleph_0 since aleph_0xaleph_0=aleph_0.
Mike Oliver
> I was using (2^aleph_0)^aleph_0=2^aleph_0 since aleph_0xaleph_0=aleph_0.
But how do you get that the cardinality of the set of countable
sets of reals is (2^aleph_0)^aleph_0 ? The latter is certainly
the number of countable *sequences* of reals; to get countable *sets*
(or multisets, but this is a minor point) you have to forget the
order -- that is, you mod out by the equivalence relation induced
by reordering the sequence.
In models of ~AC, quotients by an equivalence relation can
be larger than the underlying set. This is a fairly strong
intuitive argument for the truth of AC (though I'm not sure
that ~AC actually *implies* that you have this strange situation).
Lee Rudolph
>In models of ~AC, quotients by an equivalence relation can
>be larger than the underlying set. This is a fairly strong
>intuitive argument for the truth of AC (though I'm not sure
>that ~AC actually *implies* that you have this strange situation).
I'm not sure how strong an intuitive argument that is, for me
(a humble topologist, to be sure, and no set theorist nor logician).
Certainly when one considers different notions of "larger",
there are situations in workaday mathematics in which "quotients
by an equivalence relation can be larger than the underlying"
object which is being quotiented. (1) There's a closed subset
of R^3 which has as its topological quotient by an appropriate
equivalence relation the Hilbert cube (product of countably
many closed intervals). (2) There probably *isn't* (says the
intuition of people who have intuition on this sort of thing;
not me!) a free action of a non-trivial p-adic group on any
topological manifold--but if there *is* such a thing, then
the quotient space will have dimension greater than the
manifold.
Lee Rudolph
Robert J. Kolker
Virgil wrote:
>
> There is a theorem, whose name I forget, which says that given
> injections f:A -> B and g:B -> A, there is a bijection h:A -> B.
The Berstein Equivalence Theorem.
Bob Kolker
Mike Oliver
Lee Rudolph wrote:
>
> Mike Oliver <oli...@math.ucla.edu> writes:
>
>> In models of ~AC, quotients by an equivalence relation can
>> be larger than the underlying set. This is a fairly strong
>> intuitive argument for the truth of AC (though I'm not sure
>> that ~AC actually *implies* that you have this strange situation).
>
> I'm not sure how strong an intuitive argument that is, for me
> (a humble topologist, to be sure, and no set theorist nor logician).
> Certainly when one considers different notions of "larger",
> there are situations in workaday mathematics in which "quotients
> by an equivalence relation can be larger than the underlying"
> object which is being quotiented.
Oh, I don't doubt it, if the notion of size is taken to mean
something like topological dimension, as in your examples.
But we were talking cardinality, just the number of *things*
around, with no structure among those things being considered.
And in that context, the result says: "If you clump certain
of these things together and ignore the distinction between
them, then you wind up with more clumps than you originally
had things to clump.". To me at least, that seems passing strange,
and I've worked with these gadgets a little bit, enough
that the sense of strangeness is probably not mere unfamiliarity.
Richard Carr
:Date: Sun, 25 Jun 2000 00:37:09 -0700
:From: Mike Oliver <oli...@math.ucla.edu>
:To: Richard Carr <ca...@cpw.math.columbia.edu>
:Newsgroups: sci.logic, sci.math
:Subject: Re: cardinality of the power set of the integers
:
:
:
:
I was thinking more on the lines of bijecting R to 2^{aleph_0} and then
using (2^{aleph_0})^{aleph_0}=2^{aleph_0} etc.
the_grea...@my-deja.com
"Dik T. Winter" <Dik.W...@cwi.nl> wrote:
> the_grea...@my-deja.com writes:
> > Also, infinite sets can be put in bijection with subsets of
> > themselves. To me, this implies they are simultaneously
> > cardinally bigger and smaller then themselves. So I don't
> > see the necessity of those relations excluding each other.
>
> When you use terminology you should also use the definitions.
> As Dave Seaman has put it:
>
> > 1) There is an injection from A to B, but none from B to A.
> > 2) There is an injection from B to A, but none from A to B.
> > 3) There are injections in both directions.
> > 4) There is no injection in either direction.
> >
> > In case 1) we say that |A| < |B|.
> > In case 2) we say that |A| > |B|.
> > In case 3) we can apply the Cantor-Bernstein theorem to
> > conclude that there is a bijection between
> > A and B, which means that |A| = |B|.
>
> These are the definitions used by mathematicians, and with these
> definitions the exclusion holds.
Consider G, the Set of all even numbers not expressable
as the sum of two prime numbers. What is G's Cardinal
number? How does |G| compair to |{1,2,3}|? Which of
those exclusive cases 1, 2, 3 or 4 handles it?
Are some sets too illogical to be exclusivly classified?
Example:
"Eventhough N (the set of all numbers) contains
more members than E (even numbers only), a
member-to-member pairing of N to E, which leaves
no member unpaired or paired more than once, exists."
Nathan the Great
Anonymous
>> > > "We have seen that, of the three relations a = b,
>> > > a < b, b < a, each one exclude the two others..."
>> > >
>> > >Thats about as inconspicuous as a Tarantula on Angle Food cake.
>> > >Cantor, in his infinite wisdom, assumes what he sets out to prove.
>> >
>> > What sort of toadying comment is this? It's not an ASSUMPTION but
>> > a WILD RANT. You're getting to be an old softie, aren't you?
>>
>> I was trying to draw your attention to Cantor's assumption that
>> infinite sets can be compared |a| = |b|, |a| < |b|, |b| > |a|,
>> just like finite sets, with each relation excluding the other two.
>
> A few suggestions:
> (i) download a better sarcasm detector somewhere,
> (ii) learn what the words "we have seen that" mean.
What justifies your conclusion (i) that Nathan missed the sarcasm?
The way I interpretted Nathan's post, (ii) means "let us assume."
Cantor never proves the trichotomy of order for the Cardinal numbers.
Cantor implies that a proof exists but never gives one.
Bob Hope
--------== Posted Anonymously via Newsfeeds.Com ==-------
Featuring the worlds only Anonymous Usenet Server
-----------== http://www.newsfeeds.com ==----------
Dik T. Winter
We do not know. So with our current state of knowledge these two sets
are uncomparable and G's cardinal number is unknown. Your question is
similar to the following discourse:
A: Coins either do have a hole or do not have a hole, this is exclusive.
B: Which of those two exclusive cases handles the Belgian 10 centimes
coin of 1938?
> Are some sets too illogical to be exclusivly classified?
> "Eventhough N (the set of all numbers) contains
> more members than E (even numbers only), a
> member-to-member pairing of N to E, which leaves
> no member unpaired or paired more than once, exists."
So there is an injection from N to E and there is an injection from E to N.
Hence by definition: |N| = |E|. If you assert that |N| > |E| you must
show that there is an injection from E to N, but there does not exist an
injection from N to E, because that is the definition of |N| > |E|. You
must remember that these mathematical notations and definitions have nothing
to do with your feeling that N is larger than E.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
david_...@my-deja.com
Anonymous <nob...@newsfeeds.com> wrote:
> On Fri, 23 Jun 2000 17:45:45 GMT, david_...@my-deja.com wrote:
>
> >> > > "We have seen that, of the three relations a = b,
> >> > > a < b, b < a, each one exclude the two others..."
> >> > >
> >> > >Thats about as inconspicuous as a Tarantula on Angle Food cake.
> >> > >Cantor, in his infinite wisdom, assumes what he sets out to
prove.
> >> >
> >> > What sort of toadying comment is this? It's not an ASSUMPTION but
> >> > a WILD RANT. You're getting to be an old softie, aren't you?
> >>
> >> I was trying to draw your attention to Cantor's assumption that
> >> infinite sets can be compared |a| = |b|, |a| < |b|, |b| > |a|,
> >> just like finite sets, with each relation excluding the other two.
> >
> > A few suggestions:
> > (i) download a better sarcasm detector somewhere,
> > (ii) learn what the words "we have seen that" mean.
>
> What justifies your conclusion (i) that Nathan missed the sarcasm?
Good question. I was making an unwarranted generalization from
the obvious fact that he misses the point to every definition and
proof that he reads.
> The way I interpretted Nathan's post, (ii) means "let us assume."
Um, right. Hard to see why you'd assume that - it's not
what he _wrote_.
> Cantor never proves the trichotomy of order for the Cardinal numbers.
> Cantor implies that a proof exists but never gives one.
I wouldn't know about that. If you're taking what Nathan
says about this as evidence for anything you're making a huge
mistake. But if you know for other reasons that this is
something that Cantor never proved then fine, it's something
Cantor never proved. Of what _possible_ significance is this
fact, if fact it is? What difference does it make to _anything_
what Cantor proved and what he didn't?
What Cantor did and did not prove may be of historical
interest, but it has no bearing whatever on any of the
mathematics.
> Bob Hope
Why am I talking to people who don't even exist?
> --------== Posted Anonymously via Newsfeeds.Com ==-------
> Featuring the worlds only Anonymous Usenet Server
> -----------== http://www.newsfeeds.com ==----------
>
Dave Seaman
Anonymous <nob...@newsfeeds.com> wrote:
>What justifies your conclusion (i) that Nathan missed the sarcasm?
>The way I interpretted Nathan's post, (ii) means "let us assume."
>Cantor never proves the trichotomy of order for the Cardinal numbers.
>Cantor implies that a proof exists but never gives one.
>Bob Hope
The way I interpret your post, your signature means "let us troll."
Cantor didn't claim the trichotomy of order for the Cardinal numbers, at
least not in the context that was quoted. Trichotomy means that exactly
one of the three possibilities holds (as is the case for the real
numbers, for example). Cantor merely asserted that at most one of the
three cases could hold for cardinals, which follows directly from the
definition.
Daryl McCullough
>In models of ~AC, quotients by an equivalence relation can
>be larger than the underlying set. This is a fairly strong
>intuitive argument for the truth of AC (though I'm not sure
>that ~AC actually *implies* that you have this strange situation).
It seems that there are two different notions of one set, A,
being larger than another set, B: (1) There is a function from
A onto B, and (2) There is a one-one function from B into A.
It seems to me that (1) should be the definition of "larger
than" in the absence of choice. By that definition, A is always
larger than A mod an equivalence relation. Just use the map
f(x) = { y | y is equivalent to x }.
the_grea...@my-deja.com
"Dik T. Winter" <Dik.W...@cwi.nl> wrote:
> > Are some sets too illogical to be exclusivly classified?
> >
> > "Eventhough N (the set of all numbers) contains
> > more members than E (even numbers only), a
> > member-to-member pairing of N to E, which leaves
> > no member unpaired or paired more than once, exists."
>
> So there is an injection from N to E and there is an
> injection from E to N. Hence by definition: |N| = |E|.
> If you assert that |N| > |E| you must show that there is
> an injection from E to N, but there does not exist an
> injection from N to E, because that is the definition
> of |N| > |E|.
I said, "N has more members than E", not "|N| > |E|".
N contains more than just the even numbers, N contains
odd numbers too.
With that in mind, reread this:
"Eventhough N (the set of all numbers) contains more
members than E (even numbers only), a member-to-member
pairing of N to E, which leaves no member unpaired or
paired more than once, exists."
Its nonsense, so why do Cantorians believe it?
> You must remember that these mathematical notations and
> definitions have nothing to do with your feeling that N
> is larger than E.
The simple fact remains, N *IS* larger than E, because, in
addition to all of E, N contains the odd numbers too. You
must remember that this simple fact has nothing to do with
unsound mathematical manipulations or illogical definitions.
Nathan the Great
Age 12
Jim Heckman
the_grea...@my-deja.com wrote:
>
> I said, "N has more members than E", not "|N| > |E|".
> N contains more than just the even numbers, N contains
> odd numbers too.
You seem to be trying to say that E is a proper subset of N, which is
true.
> With that in mind, reread this:
>
> "Even though N (the set of all numbers) contains more
> members than E (even numbers only), a member-to-member
> pairing of N to E, which leaves no member unpaired or
> paired more than once, exists."
You must mean "which leaves no member _of_N_or_E_ unpaired ...";
otherwise I would read this as "which leaves no member _of_N_
unpaired ...", which describes an *injection* from N into E, not a
*bijection*, which is a stronger condition: all bijections are
injections, but not vice versa -- and bijections are what's relevant to
comparing cardinalities.
> Its nonsense, so why do Cantorians believe it?
What part of the bijection n <-> 2n fails to satisfy your criteria?
Please demonstrate any of: an integer which fails to have another
integer twice as big as it; two *different* integers m and n such that
2m = 2n; an even integer which fails to have an integer half as big as
it; two *different* even integers e and f such that e/2 = f/2. In fact,
you can easily prove that such integers and even integers do *not*
exist, so "it's nonsense" is false.
> > You must remember that these mathematical notations and
> > definitions have nothing to do with your feeling that N
> > is larger than E.
>
> The simple fact remains, N *IS* larger than E, because, in
> addition to all of E, N contains the odd numbers too. You
> must remember that this simple fact has nothing to do with
> unsound mathematical manipulations or illogical definitions.
>
> Nathan the Great
> Age 12
You're off to a "Great" start, kid.
--
~~ Jim Heckman ~~
-- "As I understand it, your actions have ensured that you will never
see Daniel again." -- Larissa, a witch-woman of the Lowlands.
-- "*Everything* is mutable." -- Destruction of the Endless
David Libert
Mike Oliver (oli...@math.ucla.edu) writes:
> Richard Carr wrote:
>
>> I was using (2^aleph_0)^aleph_0=2^aleph_0 since aleph_0xaleph_0=aleph_0.
>
> But how do you get that the cardinality of the set of countable
> sets of reals is (2^aleph_0)^aleph_0 ? The latter is certainly
> the number of countable *sequences* of reals; to get countable *sets*
> (or multisets, but this is a minor point) you have to forget the
> order -- that is, you mod out by the equivalence relation induced
> by reordering the sequence.
>
> be larger than the underlying set. This is a fairly strong
> intuitive argument for the truth of AC (though I'm not sure
> that ~AC actually *implies* that you have this strange situation).
Consider adjoining with finite support over ground model M, Cohen reals
a_i,j where i and j range over I = the set of integers: that is
negative, 0 and positive integers.
I will define a group in M acting on {a_i,j | i,j in I}.
For pi a ground model permutation of I and s a ground model function
s: I -> I, define P_pi,s to be a permutation on {a_i,j | i,j in I}:
P_pi,s (a_i,j) = a_pi(i),s(i)+j .
(Ie: P_pi,s shifts the i-th slice by s(i) and then permutes the
slices by pi).
Let G be the group in the ground model of composition on the
underlying set {P_pi,s | pi permutation on I, s:I->I} .
Form N the finite support symmetric Cohen model for G.
For each i in I {a_i,j | j in I} has support {a_i,0} and so
{a_i,j | j in I} is a member of N. Call this set A_i:
A_i = {a_i,j | j in I} .
In fact for each i in I the function
{<j, a_i,j> | j in I} : I -> Ai also has support {a_i,0}. Ie G
shifted each slice as a unit, so fixing one element fixes the slice.
So each of these functions is in N, so for each i in I
N |= A_i is countable .
Let A = {A_i | i in I}. A has {} support, so A in N.
Suppose N |= S subset of A. S has s a finite support subset of
{a_i,j | i,j in I}. Suppose i1 and i2 are distinct in I and
A_i1 and A_i2 are each disjoint from s.
Suppose for contradiction A_i1 and A_i2 have differing membership in
S, w.l.o.g. suppose A_i1 in A and A_i2 not in A.
So in the generic filter adjoing the Cohen reals there are forcing
conditions p1 and p2, p1 ||- A_i1 in S and p2 ||- A_i2 not in S.
Let pi be the permuation of I interchanging i1 and i2, otherwise
identity. Let s:I->I be the identity off i1 and i2, and
let s(i1) be a shift rendering the "domain" of p1 in A_i1
disjoint from the "domain" of p2 in A_i2. Ie I am reindexing the
respective slices as having domain on I.
More formally: let s(i1) be s.t. for all j in I if <i1, j> is in
the domain of p1 then <i2, s(i1)+j> is not in the domain of p2.
There are infinitely many choices of s(i1) that would work for this,
since p1 and p2 each have finite domain: ie finite support adjunction
of Cohen reals.
Similarly, let s(i2) be s.t. for all j in I if <i2, j> is in
the domain of p1 then <i1, s(i2)+j> is not in the domain of p2.
Let p3 = P_pi,s (p1), lifting the action of P_pi,s from
{a_i,j | i,j in I} to forcing conditions.
p1 ||- A_i1 in S, by choice of p1. P_pi,s is only non-identity on
the slices at i1 and i2, and these were chosen outside of s the support
of S. So P_pi,s (S) = S, lifting P_pi,s to terms for N.
P_pi,s (A_i1) = A_i2, since pi interchanged i1 and i2.
So p3 ||- A_i2 in S. (Ie applying P_pi,s to p1 ||- A_i1 on S).
p3 is compatible with p2. Namely we picked s(i1) and s(i2) to shift
p1 on the i1 and i2 slices to be disjoint from p2 on the interchanged
i2 and i1 slices.
But p2 ||- A_i2 not in S, so this is a contradiction that p2 and p3
are compatible conditions forcing incompatible facts.
We obtained this contradiction from assuming that S had differing
memebership of A_i1 and A_i2, for slices disjoint from s the support
of S.
We conclude for S in N, S subset of A, apart from finitely many A_i
meeting s nontrivially S is uniform membership:
S ^ {A_i1 | A_i1 ^ s = {} } = {} or
S ^ {A_i1 | A_i1 ^ s = {} } = {A_i1 | A_i1 ^ s = {} } .
Call a subset T of A cofinite in A iff A - T is finite.
We have shown: if N |= S subset of A
then S is finite or cofinite in A .
This property of sets A is called amorphous: define a set B is
amorphous iff B is infinite and for all S subset of B S is finite
or S is cofinite in B .
So we have shown: N |= A is amorphous .
Claim: ZF |- For all sets B, if B is amorphous then B cannot be
linearly ordered.
Proof of claim:
Suppose B is amorphous. Let L be the "lower" set:
L = {b in B | there are only finitely many b1 in B s.t. b1 < b} .
If L is infinite, then infinitely many integers are the cardinalities
of initial segments of B, ie distinct L members have distinct
cardinalities of smaller B elements. The set of such integers is closed
downward (initial segment of initial segment is initial segment). So
every non-negative integer is the cardinality of the b1's below some b.
Each integer can correspond this way to at most one b. So under the
hypothesis that L is infinite we get the non-negative integers can be
mapped 1-1 into L.
So the range of the even integers through this embedding is an
infinite non-cofinite-in-B subset of B, contra B assumed amorphous.
We conclude L is finite.
Now consider
U = {b in B | there are only finitely many b1 in b s.t. b1 > b} .
As above, if U is infinite, the positive integers map order reversing
into U, and the even integers through this map refute B amorphous.
We conclude U is finite.
Since L and U are both finite and B is infinite,
pick b in B - (L union U) . If B could be linearly ordered, consider
the cuts of b under such an ordering. So the lower and upper cuts
of b are each infinite (by definition of L and U), so the lower cut of
b is infinite and not cofinite in B, contra B amorphous.
So B cannot be linearly ordered.
QED claim.
So in N, we have A an amorphous set of countable sets of reals, so A
cannot be linearly ordered.
If there were a bijection in N of {C subset reals | C countable},
then pulling back the linear ordering on the reals through the
bijection, we would get a linear ordering on A, contra above.
Similarly, in N if there were any injection of the set of countable
sets of reals to reals, such injection could pull the linear ordering
back to A.
The reals inject into the set of countable sets of reals. By
singleton if countable includes finite. If we want denumerable sets of
reals, ie countably infinite, the injection can be arranged by fixing C
a countable set of reals and sending real number r to the symmetric
difference of C and {r}.
So this injects reals to countable or denumrable sets of reals in all
ZF models. In N our set A above shows neither version of reverse
injection occurs. So in N the cardinal inequality is strict.
This all started asking for more information about the chain of
ineqalities:
|R| <= |F(R)| <= |C(R)| <= |P(R)|.
In ZFC those first three are provably equal. In fact
ZF |- |R| = |F(R)|. So I have been discussing N a ZF model where
the third |C(R)| is strictly greater than the common value of the
first two.
What about the last one: |C(R)| <= |P(R)| ? In ZFC |C(R)| = |R|,
and so by Cantor's theorem (assuming it survives the recent round of
critical analysis here in sci.math hahaha) |C(R)| < |P(R)| .
N shows this last argument breaks down in ZF. So |C(R)| = |P(R)| is
at this moment to my knowledge an unresolved possibility over ZF.
--
David Libert (ah...@freenet.carleton.ca)
1. I used to be conceited but now I am perfect.
2. "So self-quoting doesn't seem so bad." -- David Libert
3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig
Robert J. Kolker
the_grea...@my-deja.com wrote:
>
> Nathan the Great
> Age 12
Look here, Not So Great. The cardinal number of set A
is equal to the cardinal number of set B if and only if there
is a one to one onto mapping between A and B. It matters
not one whit, where A is a proper subset of B.
In fact one definition of infinite is this: A is infinite if and
only if it has the same cardinality as a proper subset of
itself.
You are a snotty child who should learn some math
before spouting off.
Bob Kolker
Jonathan Hoyle
Nathan, you have not defined what you mean by "A has more members than
B". I could take it to mean any of the following (or even others):
1. |A| > |B|
2. B is a proper subset of A
3. There exists a 1-1 mapping between B and a proper subset of A.
Obviously all three are equivelent if A and B are finite. If they are
infinite, then they have different meanings. #1 is what I would first
guess you meant, but you later say that it isn't. #2 is my second guess
but then you can't say the rationals has more elements than the set { pi
}. #3 will indeed allow you to compare sets which are disjoint, but
then "has more members than" is no longer an anti-symmetric relation.
If we look at N and Q (the set of naturals and the set of rationals) for
each of these definitions, we can say:
1. N does not have more members than Q.
Q does not have more members than N.
2. N does not have more members than Q.
Q has more members than N.
3. N has more members than Q.
Q has more members than N.
So if you clarify what you mean by "more members", we can proceed.
Jonathan Hoyle
Eastman Kodak
Mike Oliver
David Libert wrote:
>
> So in N, we have A an amorphous set of countable sets of reals, so A
> cannot be linearly ordered.
>
> If there were a bijection in N of {C subset reals | C countable},
> then pulling back the linear ordering on the reals through the
> bijection, we would get a linear ordering on A, contra above.
> [...]
> So this injects reals to countable or denumrable sets of reals in all
> ZF models. In N our set A above shows neither version of reverse
> injection occurs. So in N the cardinal inequality is strict.
Nice! However I already remarked, earlier in the thread, that
it follows from AD that the inequality is strict. So that already
settles the fact that ZF can't prove the inequality is *not* strict,
unless of course you think AD might be refuted.
> What about the last one: |C(R)| <= |P(R)| ? In ZFC |C(R)| = |R|,
> and so by Cantor's theorem (assuming it survives the recent round of
> critical analysis here in sci.math hahaha) |C(R)| < |P(R)| .
>
> N shows this last argument breaks down in ZF. So |C(R)| = |P(R)| is
> at this moment to my knowledge an unresolved possibility over ZF.
No, the argument's fine if you do it carefully. There is a
*surjection* from R to C(R) ; this is provable in ZF. If there
were an injection from P(R) to C(R), we would get a surjection
from R to P(R), which is precisely the gadget that Cantor's
proof shows can't exist.
Jonathan Hoyle
Oops, that's not even true. Sorry, Nathan, I can't even give you that
much.
Jonathan Hoyle
Eastman Kodak
--------------------------------------------------------
Q: What is purple and misunderstands Mathematics?
A: Nathan the Grape!
Jonathan Hoyle
respond, Nathan abandons mathematics and is left with nothing but
insults. It's tantamount to his admitting defeat.
So, congratulations Pertti for defeating him. Nathan, feel free to
confirm what I am saying by avoiding Mathematics and insulting me.
Jonathan Hoyle
Robert J. Kolker
Jonathan Hoyle wrote:
> When Nathan's point is disproven so completely that even he can't
> respond, Nathan abandons mathematics and is left with nothing but
> insults. It's tantamount to his admitting defeat.
Softly now. Nathan is but a child. He knows not what he does.
Bob Kolker
Flavio Borges Botelho
> > You must remember that these mathematical notations and
> > definitions have nothing to do with your feeling that N
> > is larger than E.
>
> The simple fact remains, N *IS* larger than E, because, in
> addition to all of E, N contains the odd numbers too. You
> must remember that this simple fact has nothing to do with
> unsound mathematical manipulations or illogical definitions.
I have similar conceptions to yours, but the point here is that
the infinite set N has the same 'kind' of infinity of E. So that a set
that you cannot map to N would have a 'bigger' infinity...
If N is twice as large as E does not matter, in fact even if the
set of Rationals is infinity times larger than N does not matter.
The 'bigger' infinity is analogous to a exponentially larger
infinity.
That's why the Real numbers are considered the power set of the
naturals...
I know the sci.math regulars are going to kill me for saying this,
but the situation is
analogous to:
Taking 'a' as a variable, making additions, multiplication,
exponantiations with it. In this case consider a = 10:
2+10 = 12
2*10 = 20
10^2 = 100
2^10 = 1024
See how the last one is much bigger? Now take that 'a' to infinity and
the difference becomes incomprehensively large...
Cantor's point is that all infinite sets can be mapped one on one unless
the the second one has an infinity of the last kind.... So the last kind
of infinity is a 'bigger' one, in the meaning of having a bigger
infinity than the other set can ever match...
> Nathan the Great
> Age 12
Are you really 12?
Regards,
Flavio Botelho
Virgil
> "Eventhough N (the set of all numbers) contains more
> members than E (even numbers only), a member-to-member
> pairing of N to E, which leaves no member unpaired or
> paired more than once, exists."
>
>Its nonsense, so why do Cantorians believe it?
You are confusing properties of finite sets with properties of infinite
sets. This would be nonsense if anyone were claiming that N is a finite
set.
Cantorians believe that N is an infinite set, and, therefore, may quite
properly be in one-to-one correspondence with a proper subset.
If you think it is nonsense, you must believe that taking one element
out of a finite set makes it finite. Now that IS nonsense.
--
Virgil
vm...@frii.com
David Libert
Mike Oliver (oli...@math.ucla.edu) writes:
> David Libert wrote:
>
>>
>> So in N, we have A an amorphous set of countable sets of reals, so A
>> cannot be linearly ordered.
>>
>> If there were a bijection in N of {C subset reals | C countable},
>> then pulling back the linear ordering on the reals through the
>> bijection, we would get a linear ordering on A, contra above.
>> So this injects reals to countable or denumrable sets of reals in all
>> ZF models. In N our set A above shows neither version of reverse
>> injection occurs. So in N the cardinal inequality is strict.
>
> it follows from AD that the inequality is strict. So that already
> settles the fact that ZF can't prove the inequality is *not* strict,
> unless of course you think AD might be refuted.
I think I missed this part of the thread. I had noticed that your
articles I had read seemed to be jumping a gap in what arrived at my
site.
Each style of solution is of interest in its own way. I like to see a
version getting a close upper bound on consistency strength. On the
other hand, my example is more of a made up example, and getting it in
all AD (+ some choice ? ) is more canonical.
As to expecting AD to be refuted, my expectations this way were never
high, and much less so after Woodin's and related upper bounds on AD
consistency strength. For me AC style large cardinals have more
naturalness than AD.
I had not realized that AD -> the inequality is strict. What I had
picked up from your posts that I did see was the general phenomenon of
AD making quotients become bigger. I thought the application of this
theme to the particular case at hand (ie for example sets as quotients
of sequences) was speculative.
This is an interesting consequence of AD. Maybe you had posted about
this but I had missed it.
When you wrote about quotient blowups I thought of Turing degrees
versus reals. I recall something along these lines but can't
reconstruct it. Does full AD or Turing determinacy with some amount of
choice (countable choice or DC ?) imply the Turing degrees don't inject
into the reals? Also what do these theories say about injections the
other way: reals to Turing degrees?
What I seem to recall was some result to the effect that there are
"more" Turing degrees than reals: I don't know if this was
incomparability or strict > .
I was trying to guess how this may have gone. Turing determinacy
gives the Turing cone non-principal ultrafilter on Turing degrees. Does
that help?
One result I thought of in considering this is
ZF + countable choice |- if there is a non-principal ultrafilter on
omega then there is a non-Lebesgue measurable set of reals.
But the ultrafilter is at the wrong level. If there were a similar
result that a non-principal ultrafilter on the reals -> a non-Lebesgue
measurable set, then from AD and a bijection of Turing degrees to
reals, pull over the Turing cone ultrafilter to reals, apply that
result, get non-Lebesgue measurable set, contra AD's other consequence
that every set is Lebesgue measurable.
Anyway the Turing degree quotient blowup is a mystery, plus the one
you mentioned of sequences to sets.
>> What about the last one: |C(R)| <= |P(R)| ? In ZFC |C(R)| = |R|,
>> and so by Cantor's theorem (assuming it survives the recent round of
>> critical analysis here in sci.math hahaha) |C(R)| < |P(R)| .
>>
>> N shows this last argument breaks down in ZF. So |C(R)| = |P(R)| is
>> at this moment to my knowledge an unresolved possibility over ZF.
>
> No, the argument's fine if you do it carefully. There is a
> *surjection* from R to C(R) ; this is provable in ZF. If there
> were an injection from P(R) to C(R), we would get a surjection
> from R to P(R), which is precisely the gadget that Cantor's
> proof shows can't exist.
Yes, that is nice to see. It is interesting to see all the care
needed over ZF on subjects we would just blast by with AC.
tor...@sm.luth.se
Flavio Borges Botelho writes:
>Are you really 12?
Nathan is a 43-year old troll, and a very successful one.
Jonathan Hoyle
<snip>
There are no such things as "Cantorians" and "non-Cantorians". There
are only cranks and mathematicians, respectively.
Jonathan Hoyle
Eastman Kodak
Jonathan Hoyle
Duh.
James Hunter
the_grea...@my-deja.com wrote:
> In article <FwrL0...@cwi.nl>,
> "Dik T. Winter" <Dik.W...@cwi.nl> wrote:
> > > Are some sets too illogical to be exclusivly classified?
> > >
> > > "Eventhough N (the set of all numbers) contains
> > > more members than E (even numbers only), a
> > > member-to-member pairing of N to E, which leaves
> > > no member unpaired or paired more than once, exists."
> >
>
>
> Its nonsense, so why do Cantorians believe it?
>
> > You must remember that these mathematical notations and
> > definitions have nothing to do with your feeling that N
> > is larger than E.
>
> The simple fact remains, N *IS* larger than E, because, in
> addition to all of E, N contains the odd numbers too. You
> must remember that this simple fact has nothing to do with
> unsound mathematical manipulations or illogical definitions.
>
> Nathan the Great
> Age 12
It has something to do with idiot logic though.
The main purpose of set theory is to separate
the idiots from the math.
Dave Seaman
Dave Seaman <a...@seaman.cc.purdue.edu> wrote:
>In article <8ivjus$rjv$1...@nnrp1.deja.com>,
> <the_grea...@my-deja.com> wrote:
>>> Cantor's argument starts out as follows
>>> (according to the well-known Jourdain's translation):
>
>>> "We have seen that, of the three relations a = b,
>>> a < b, b < a, each one exclude the two others..."
For what it's worth, I just got around to looking this up. Nathan's
quote is accurate (except that it should read "excludes" rather than
"exclude"), but Cantor goes on to say, in the very next sentence:
On the other hand, the theorem that, with any two cardinal
numbers a and b, one of those three relations must necessarily
be realized, is by no means self-evident and can hardly be
proved at this stage.
Cantor does go on to mention in passing what we now know as the
Cantor-Bernstein theorem, but he says the result will follow as an easy
consequence of the theorem alluded to above, whose proof will come later
(as a result of the axiom of choice). The proof without AC was given
independently by Schroeder and Bernstein.
Mike Oliver
> Does full AD or Turing determinacy with some amount of
> choice (countable choice or DC ?) imply the Turing degrees don't inject
> into the reals?
I'm almost certain the answer is "yes" (i.e. no injection) but I
don't have a full proof (not being experienced enough with the degrees).
> Also what do these theories say about injections the
> other way: reals to Turing degrees?
I'm almost certain the reals *do* embed in the degrees.
> Anyway the Turing degree quotient blowup is a mystery, plus the one
> you mentioned of sequences to sets.
Brief sketch of the technology used for these questions: Given
two equivalence relations E and F on the reals, we say
E <= F ("E is reducible to F) just in case there's a function f : R --> R
such that for all reals x,y, xEy <==> f(x) F f(y). You'll quickly
verify that this implies |R/E| <= |R/F| , and that in the
case F is the identity, the converse holds as well. The converse
holds also whenever you have Uniformization.
Now let E be the Vitali equivalence relation: xEy iff x-y is rational.
Assuming AD, I claim E is *not* reducible to identity on the reals.
Suppose otherwise and let f be the witnessing function. There is
a comeager set C \subseteq R such that f restricted to C is continuous.
(To see this, look at the pullbacks under f of the basic open nbhds.
Each has the property of Baire by AD, so it differs from an open
set by a meager set. Take away these countably-many meager sets.)
Moreover, without loss of generality, C is *invariant* under E -- that
is, if x \in C and xEy, then y \in C. That's because, otherwise, we
can just take the intersection of all sets C+q for rational q; this
is a countable intersection of comeager sets, therefore comeager.
Now pick some x0, y0 \in C which are in different E-equivalence classes
(these must exist because each E-equivalence class is meager; indeed, in
this case, countable). The entire equivalence class of x is contained
in C (by invariance), and for any x1 which is E-related to x0, we must
have f(x1)=f(x0). But this equivalence class is dense in the reals, and
therefore in C, so it follows by continuity that for *any* y \in C, f(y)=f(x0).
In particular, f(y0) = f(x0). But y0 is not E-related to x0, so this
is a contradiction. The claim is proved.
Now let's consider countable sets of reals. To avoid an annoying technicality
we'll actually work with countable *multi*sets of reals. That is, consider
the action of S_oo on the collection of all countable sequences of reals,
where the action permutes the indices of the sequence. The orbit equivalence
classes correspond naturally to countable multisets of reals. Now pull
the equivalence relation back along some natural surjection h: R-->R^omega
(this isn't really necessary; it's just to keep the terminology I've been using).
Let F be this equivalence relation.
Note that the Vitali equivalence relation is easily reducible to F, because
its equivalence classes *are* countable sets of reals. I'll leave the details
to you.
Now F cannot be reducible to identity on the reals, because if it were, the
Vitali relation would be as well.
Therefore AD (or just "every set of reals has the property of Baire") implies
that there are more countable multisets of reals than there are reals. It's
not very hard to change "multiset" to "set" here. For Turing degrees, I'm
almost sure that the Vitali equivalence relation is reducible to Turing equivalence,
but I don't have a specific construction in mind. If you want to work on
it, you might find it easier to work with the equivalence relation E_0,
which is bireducible with the Vitali relation. For two elements of
Baire space x,y, we say "x E_0 y" if and only if x(n)=y(n) for all but
finitely many n.
Posted and mailed.
the_grea...@my-deja.com
a...@seaman.cc.purdue.edu (Dave Seaman) wrote:
> Yes. I understand that your tree has countably many levels, each at a
> finite depth. Each level contains a finite number of nodes, and
> therefore the total number of nodes in the tree is countable.
--------------------------------------------------
Does someone know the name of the following theory?
"Every set of natural numbers has a least number"
--------------------------------------------------
Contrary to Cantorian dogma, Nathan's tree is uncountable.
_{1,2,3}_
_{1,2}_/ P
/ \_{1,2}___ O
_{1}_/ W
/ \ _{1,3}___ E
/ \_{1}___/ F R
/ \_{1}_____ I S
{}/ N E
\ _{2,3}___ I T
\ _{2}___/ T
\ / \_{2}_____ E O
\_{}__/ F
\ _{3}_____
\_{}____/ N
\_{}______
L = { 1, 2, 3, 4, 5, ... }
S = { {}, {1}, {1,2}, {2}, {1,2,3}, {1,3}, {2,3}, {3}, ... }
Recall, two sets are the same size (cardinality), if
they can form a "one-to-one match-up" between their
elements, with none left over in either set. If two
sets can never form such a "one-to-one match-up", they
are cardinally different.
I will now demonstrate, that, no "one-to-one match-up"
can be constructed between L (the Levels) and S (the Sets)
of my infinite binary tree (aka finite power set of N).
The following is based upon Cantor's famous "diagonalization
argument," which is a proof by contradiction. It begins
with the assumption that both sets are Cardinally equal.
Then, a contradiction is produced. Thus, proving the
assumption untenable.
Since these sets are Cardinally equal (the assumption), we
must be able to form a one-to-one match-up between the
elements of L and the elements of S, with none left over on
either side. This type of match-up is called a bijection,
and it looks something like this:
L S
=== ===
1 <-> {3,42}
2 <-> {11}
3 <-> {1,2,3,7}
4 <-> {2,5}
5 <-> {2,3,5}
6 <-> {1}
7 <-> {93,2000}
8 <-> {1,2}
... etc. ...
Notice that some numbers (elements of L) are matched to
sets (elements of S) containing them. ie: 3 <-> {1,2,3,7}.
Other numbers are matched to sets that do not contain
them. ie: 4 <-> {2,5}. Consider X, the set of all numbers
(elements of L) not matched to sets (elements of S) containing
those numbers. There are three cases to consider:
(i) X contains no elements.
(ii) X has a finite number of elements.
(iii) X has an infinite number of elements.
Disproving (i) is easy. Simply notice that (because X
is empty) all elements of L must be paired to sets of S
that contain those elements as members. With that in
mind, it is easy to see that {1} <-> 1 and {2} <-> 2
must be paired together in the bijection. Pairing either
of those sets, to any other numbers, would violate the
assumption that X was empty. But now, what does {1,2} get
paired to? It must be either a '1' or '2', lest the
assumption (X is empty) be violated. But pairing {1,2} to
'1' or '2' means pairing to the same element twice, a
contradiction. Therefore, either X is non-empty, or the
assumed bijection is invalid.
Disproving (ii) is a little tricky. Here we assume X has
a finite number of elements. Hence, set X is equivalent
to some member of set S. What number (element of L) pairs
to X? It cannot be a member of X, since X was specially
constructed to contain only those elements of L that do
not match sets containing them. On the other hand, if the
element of L that matches with X is not contained in X
then... well, then it must be contained in X, again by the
definition of X! This is a contradiction. The existence
of this contradiction shows that no element of L can be
matched with this subset of S. Our match-up cannot be
complete. Therefore, either X is non-finite, or the
assumed bijection is invalid.
At this point, notice that it is not necessary to disprove
(iii) directly. If (iii) can be _validly_ reduced to (i),
without, in the process, destroying the status of the
assumed bijection, then it (iii) must be considered
untenable. I will now show how (i) can be _validly_ derived
from (iii).
The bijection below pairs each element of L to a set in
S containing it (the equivalent element of L) as one of
its members.
L S
=== ===
1 <-> {1}
2 <-> {1,2}
3 <-> {1,2,3}
4 <-> {1,2,3,4}
5 <-> {1,2,3,4,5}
... etc. ...
I will reach the bijection above, by using valid Cantorian
manipulations, performed on an assumed valid starting bijection.
Thus, any inconsistency (contradiction) derived, from the
bijection above, invalidates the starting bijection.
Note, set X, for the bijection above, has to be empty.
To convert the original bijection into the one above,
a simple step-by-step process, guaranteed not to corrupt
the bijection status, is used:
Starting with 1 and counting 1,2,3, etc. find the first
element of L that is not correctly (as shown above) paired
to a set in S. Call this the nth element of L. It should
be paired to an n-dimensional subset in S, having 1 as its
1st element and n as its n-th element. Once the correct
set is located (it has to be somewhere in S), swap the
incorrectly paired set, with the correct one. And continue...
Now, every member of L can be paired, as shown above, to a set
in S containing it (the equivalent element of L) as one of
its (the set in S) members. When this pairing is 'complete',
set X will be empty. But X={} is a contradiction. And, this
contradiction proves (iii) untenable.
Therefore, set X can't be empty, finite or infinite.
End of proof.
Nathan the Great
Age: 12 yrs
the_grea...@my-deja.com
the_grea...@my-deja.com wrote:
> The existence
> of this contradiction shows that no element of L can be
> matched with this subset of S. Our match-up cannot be
--------------------^^^^^^---(should be "set" not "subset")
> complete. Therefore, either X is non-finite, or the
> assumed bijection is invalid.
[snip]
>
> Therefore, set X can't be empty, finite or infinite.
>
Conclusion: S (the finite power set of N) is uncountable.
Nathan the Great
Age 1
Dave Seaman
> Does someone know the name of the following theory?
> "Every set of natural numbers has a least number"
>--------------------------------------------------
It's called the well-ordering principle.
>Contrary to Cantorian dogma, Nathan's tree is uncountable.
Let me get this straight. Last week, you were claiming that your tree
contained the complete power set P(N), and that the tree is countable.
Now you are claiming that the tree contains only the set of finite
subsets of N, and that the tree is uncountable.
Consistency is not one of your strong suits.
> (i) X contains no elements.
> (ii) X has a finite number of elements.
> (iii) X has an infinite number of elements.
Actually, there are only two cases:
(i) X contains a finite number of elements (impossible if the
mapping N <-> F(N) that you started with is a bijection).
(ii) X contains an infinite number of elements.
>At this point, notice that it is not necessary to disprove
>(iii) directly. If (iii) can be _validly_ reduced to (i),
>without, in the process, destroying the status of the
>assumed bijection, then it (iii) must be considered
>untenable. I will now show how (i) can be _validly_ derived
>from (iii).
You can't do that without changing the mapping. Changing the mapping,
once it is fixed, is not allowed. The diagonal argument produces, for
each mapping, a subset of N that is not in the range of the map.
>The bijection below pairs each element of L to a set in
>S containing it (the equivalent element of L) as one of
>its members.
> L S
> === ===
> 1 <-> {1}
> 2 <-> {1,2}
> 3 <-> {1,2,3}
> 4 <-> {1,2,3,4}
> 5 <-> {1,2,3,4,5}
> ... etc. ...
>I will reach the bijection above, by using valid Cantorian
>manipulations, performed on an assumed valid starting bijection.
>Thus, any inconsistency (contradiction) derived, from the
>bijection above, invalidates the starting bijection.
>Note, set X, for the bijection above, has to be empty.
Agreed. Since the empty set is not in your set S, there is no
contradiction. The diagonal argument always produces a set that is not
in the range of the given mapping.