wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> try to solve this riddle
        
(Message started by: srn347 on Sep 27th, 2007, 8:02pm)
Title: try to solve this riddle
Post by srn347 on Sep 27th, 2007, 8:02pm
Prove that uncountable infinity is higher than countable infinity. Linking to a page that says uncountable infinity is higher doesn't count.
Title: Re: try to solve this riddle
Post by Michael_Dagg on Sep 27th, 2007, 8:57pm
Should we use cardinals or robins?
Title: Re: try to solve this riddle
Post by Obob on Sep 27th, 2007, 9:35pm
Let S be a set with uncountably many elements.  Now suppose that the size of S is less than or equal to the size of the set of natural numbers, i.e. suppose that "uncountable infinity" is no bigger than "countable infinity".  Then, by the definition of the terms, there is a one-to-one mapping from S to the natural numbers.  Then there is a sequence of natural numbers n1, n2, n3,... such that the image of S in the natural numbers consists exactly of that sequence.  But then S is countable, for we can order the elements of S by making first the element of S mapping to n1, second the element mapping to n2, etc.  This contradicts the assumption that S is uncountable.  So it is not the case that the size of S is less than or equal to the size of the set of natural numbers.  Thus the size of S is bigger than countable infinity, i.e. "uncountable infinity" is bigger than countable infinity.

Of course, showing that an uncountable set (and therefore "uncountable infinity") exists is a very different (and more difficult) matter.
Title: Re: try to solve this riddle
Post by srn347 on Sep 28th, 2007, 7:21am
True. Which is bigger, uncountable infinitycountable infinity or countable infinityuncountable infinity?
Title: Re: try to solve this riddle
Post by Grimbal on Sep 28th, 2007, 7:33am
Which uncountable infinity?

Because, you know, there are more than one.
Title: Re: try to solve this riddle
Post by Obob on Sep 28th, 2007, 8:16am
Yes; your initial question was well defined because every uncountable set has more than countably many elements.  This is why I put "uncountable infinity" in quotes in my initial post: uncountable infinity does not specify a precise "size."

Provided that in your follow up you have fixed a single set S with uncountably many elements, the second cardinal will be larger.
Title: Re: try to solve this riddle
Post by SMQ on Sep 28th, 2007, 8:18am
Well, let's see; assuming the axiom of choice:

Let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/kappa.gif = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varaleph.gif0 and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/nu.gif = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varaleph.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subn.gif, where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gif > 0.

Max(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/kappa.gif, 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif) = 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/kappa.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif Max(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supkappa.gif, 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif) = 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/longrightarrow.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/kappa.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif= 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif,
Max(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/nu.gif, 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supkappa.gif) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/nu.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supkappa.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif Max(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif, 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supkappa.gif) = 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/longrightarrow.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/nu.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supkappa.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif.

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/therefore.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/kappa.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supnu.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/nu.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supkappa.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/longrightarrow.gif countable infinityuncountable infinity is at least as large as or larger than uncountable infinitycountable infinity.

Furthermore, since for all naturals (of which the cardinals are an extension) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/b.gif : http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 3, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/b.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 4, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/b.gif > http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif,  we have that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supb.gif > http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/b.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supa.gif, and since the normal arithmetic rules of exponentiation in naturals apply to cardinals as well, it would be reasonable to assume that countable infinityuncountable infinity is strictly larger than uncountable infinitycountable infinity -- but then reasonable assumptions tend to fail where transfinite cardinals are involved, so I'll stick with the weaker result. ;)



on 09/27/07 at 20:57:05, Michael_Dagg wrote:
Should we use cardinals or robins?

Don't you mean orioles? ;D

--SMQ
Title: Re: try to solve this riddle
Post by Obob on Sep 28th, 2007, 8:41am
In fact, if w denotes the cardinality of the natural numbers and y denotes the cardinality of an uncountable set, then yw=y and wy=2y>y.  So in fact wy is strictly larger.
Title: Re: try to solve this riddle
Post by Michael_Dagg on Sep 28th, 2007, 6:10pm

on 09/28/07 at 08:18:04, SMQ wrote:
Don't you mean orioles? ;D--SMQ

Yes, you are correct. I don't know what I was thinking!
Title: Re: try to solve this riddle
Post by srn347 on Sep 28th, 2007, 7:43pm
Correct. Is countable infinity a subset of uncountable infinity?
Title: Re: try to solve this riddle
Post by Obob on Sep 28th, 2007, 11:27pm
Countable infinity and uncountable infinity aren't sets, so that question makes no sense.

An uncountably infinite set does have a countably infinite subset, however.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board