Questions about sets

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Questions about sets

Postby Mike_Bson » Thu Dec 30, 2010 5:30 am UTC

1. I know [imath]\aleph_1[/imath] is defined as the cardinality of the set of ordinal numbers. What I ask is, consider this set: a countable set, whose members are countable sets. An example of this would be this set: {{1}, {2}, {3}, {4}, . . .}, where {1} is the set of all of the multiples of 1, {2} is the set of all of the multiples of two, et cetera. What cardinality does this set have?

2. How you you defined [imath]\aleph_{2}, \aleph_{3},[/imath] and so on? In general, how do you define [imath]\aleph_x[/imath], such that x is a natural number?

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Questions about sets

Postby Nitrodon » Thu Dec 30, 2010 6:31 am UTC

[imath]\aleph_1[/imath] is the cardinality of the set of countable ordinals. [imath]\aleph_2[/imath] is the cardinality of the set of ordinals with cardinality [imath]\le \aleph_1[/imath], and so forth.

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Questions about sets

Postby Mike_Bson » Thu Dec 30, 2010 6:54 am UTC

Would you kindly tell me what the difference between the set of ordinals and the set of countable ordinals is? Thanks for your help.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Questions about sets

Postby skeptical scientist » Thu Dec 30, 2010 9:55 am UTC

Nitrodon wrote:[imath]\aleph_1[/imath] is the cardinality of the set of countable ordinals. [imath]\aleph_2[/imath] is the cardinality of the set of ordinals with cardinality [imath]\le \aleph_1[/imath], and so forth.

Similarly, [imath]\aleph_0[/imath] is the cardinality of the set of finite ordinals.

A finite ordinal is just an ordinal which is finite, and a countable ordinal is just an ordinal which is countable.

A finite ordinal is just another name for a natural number: the finite ordinals are just 0, 1, 2, 3, and so on. An ordinal, more generally, is an order type of a well-ordered set, which is a set which is linearly ordered by some order <, such that each subset has a least member under <. So 0 is identified with the order type of the empty set, 1 is identified with the order type of the set {0}, and in general n is identified with the order type of the set of natural numbers less than n. There's no reason to stop with finite order types. You'll notice that the set of natural numbers is well ordered according to the standard order on the natural numbers, and the set {0,1,2,3,...,ω} is well-ordered under the order a<b iff a and b are natural numbers with a less than b, or a≠ω and b=ω. Thus the order types of these two sets are themselves ordinals. And since the sets are not finite, but countably infinite, they are examples of countably infinite ordinals.

It is also possible to have uncountable ordinals. The well ordering principle says that any set can be well-ordered, so there are uncountable well-orders. The order type of one of those would be an uncountable ordinal.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Questions about sets

Postby Mike_Bson » Thu Dec 30, 2010 11:05 am UTC

Could you give me an example of a set with a cardinality of [imath]\aleph_1[/imath] and one with [imath]\aleph_2[/imath]?

EDIT- And what cardinality is the set of reals?

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Questions about sets

Postby Nitrodon » Thu Dec 30, 2010 5:50 pm UTC

The reals have cardinality [imath]2^{\aleph_0} = \beth_1[/imath]. Under the continuum hypothesis, this is equal to [imath]\aleph_1[/imath].

Without the continuum hypothesis, there aren't really any easy examples of sets of cardinality [imath]\aleph_1[/imath] or [imath]\aleph_2[/imath].

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Questions about sets

Postby Xanthir » Thu Dec 30, 2010 6:46 pm UTC

Mike_Bson wrote:1. I know [imath]\aleph_1[/imath] is defined as the cardinality of the set of ordinal numbers. What I ask is, consider this set: a countable set, whose members are countable sets. An example of this would be this set: {{1}, {2}, {3}, {4}, . . .}, where {1} is the set of all of the multiples of 1, {2} is the set of all of the multiples of two, et cetera. What cardinality does this set have?

For each natural number, form a set of all the reduced fractions with that natural number as their numerator. This set is countably infinite, and each subset is also countably infinite. However, it's clearly a subset of the rationals, which is countably infinite. Thus, the former set is countably infinite as well.

2. How you you defined [imath]\aleph_{2}, \aleph_{3},[/imath] and so on? In general, how do you define [imath]\aleph_x[/imath], such that x is a natural number?

[imath]\aleph_{0}[/imath] is defined as the smallest infinite cardinal, [imath]\aleph_{1}[/imath] is defined as the second-smallest, [imath]\aleph_{2}[/imath] is the third smallest, etc.

We assume that [imath]2^{\aleph_{0}}[/imath] is equal to [imath]\aleph_{1}[/imath], but it might be bigger. This assumption is the "continuum hypothesis", and it's been proven to be independent of ZFC (that is, neither "the continuum hypothesis is true" nor "the continuum hypothesis is false" produce contradictions with the axioms of ZFC). To prove it one way or another we'll have to adopt more powerful axioms. In the interim, we instead use the Beth numbers which are explicitly defined by power stacks, where [imath]\aleph_{0} = \beth_{0}[/imath] and [imath]2^{\beth_{n}} = \beth_{n+1}[/imath].

ETA: We do have example of the first three beth numbers, by the way. [imath]\beth_{0}[/imath], obviously, is the cardinality of the integers. [imath]\beth_{1}[/imath] is the cardinality of the reals. [imath]\beth_{2}[/imath] is the cardinality of the functions from R to R. (Note - not all continuous functions, as that set's cardinality is just [imath]\beth_{1}[/imath]. I'm talking *all* functions, including all of those that just randomly map each real to another.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Redundant
Posts: 5
Joined: Fri Aug 01, 2008 9:45 pm UTC

Re: Questions about sets

Postby Redundant » Fri Dec 31, 2010 1:16 am UTC

Mike_Bson wrote:1. I know [imath]\aleph_1[/imath] is defined as the cardinality of the set of ordinal numbers.


Interestingly, there is no set of ordinal numbers. This is called the Burali-Forti paradox on wikipedia. If there were a set of all ordinal numbers, the union of this set would be an ordinal. In ZFC, a set is not allowed to contain itself.

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Questions about sets

Postby Mike_Bson » Fri Dec 31, 2010 1:34 am UTC

Redundant wrote:
Mike_Bson wrote:1. I know [imath]\aleph_1[/imath] is defined as the cardinality of the set of ordinal numbers.


Interestingly, there is no set of ordinal numbers. This is called the Burali-Forti paradox on wikipedia. If there were a set of all ordinal numbers, the union of this set would be an ordinal. In ZFC, a set is not allowed to contain itself.

Hm, that is very interesting indeed.

User avatar
the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

Re: Questions about sets

Postby the tree » Fri Dec 31, 2010 3:29 pm UTC

Xanthir wrote:[imath]\aleph_{0}[/imath] is defined as the smallest infinite cardinal, [imath]\aleph_{1}[/imath] is defined as the second-smallest, [imath]\aleph_{2}[/imath] is the third smallest, etc.
Considering cardinalities is something we really don't know much about (or so I'm told) - what happens if it turns out that between any two cardinalities, there is another one - so that smallest, second smallest etc doesn't work? Or is that impossible?

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Questions about sets

Postby Xanthir » Fri Dec 31, 2010 4:31 pm UTC

Then our definitions are bad, as we're assuming the infinite ordinals aren't dense.

I don't think any of the common ordinal conceptions would permit them being dense, though.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: Questions about sets

Postby letterX » Fri Dec 31, 2010 5:05 pm UTC

the tree wrote:
Xanthir wrote:[imath]\aleph_{0}[/imath] is defined as the smallest infinite cardinal, [imath]\aleph_{1}[/imath] is defined as the second-smallest, [imath]\aleph_{2}[/imath] is the third smallest, etc.
Considering cardinalities is something we really don't know much about (or so I'm told) - what happens if it turns out that between any two cardinalities, there is another one - so that smallest, second smallest etc doesn't work? Or is that impossible?

With the Axiom of Choice, this is indeed impossible. AoC is equivalent to the Well-Ordering Principle. By well-ordering, every cardinal is the cardinality of some ordinal number (since we just well-order some set with that cardinality). Then, (re)define each cardinal number to be the first ordinal with that cardinality. Now, since the cardinals are a sub-class of the ordinals, they are well-ordered, and your problem goes away.

Without the AoC? I have no idea. To my knowledge, mathematicians don't generally talk about large cardinals without the AoC, but I could easily be wrong.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Questions about sets

Postby mike-l » Fri Dec 31, 2010 6:44 pm UTC

skeptical scientist wrote:It is also possible to have uncountable ordinals. The well ordering principle says that any set can be well-ordered, so there are uncountable well-orders. The order type of one of those would be an uncountable ordinal.


Even without well ordering, there are uncountable ordinals, as the set of all ordinals for which there is an injection to a given set is itself an ordinal for which there is no injection to that set. (See Hartog's Number) So you can get ordinals not less or equal to any cardinality (you can't say greater without the well ordering principal/axiom of choice)
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Questions about sets

Postby Mike_Bson » Fri Dec 31, 2010 9:27 pm UTC

So, let me get this straight: [imath]\aleph_0[/imath] the cardinality of the set of all of the ordinals up to [imath]\omega \times 2[/imath], [imath]\aleph_1[/imath] is the cardinality of the set of all ordinals up to [imath]\omega^2[/imath], [imath]\aleph_2[/imath] is the cardinality of all ordinals up to [imath]\omega^\omega[/imath], etc.? Do I have this right?

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Questions about sets

Postby antonfire » Fri Dec 31, 2010 10:02 pm UTC

No. All the sets of ordinals you've named are countable.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Questions about sets

Postby Mike_Bson » Fri Dec 31, 2010 10:25 pm UTC

Okay, that makes more sense to me. What is an example of a set with the cardinality [imath]\aleph_1[/imath], then? And what about [imath]\aleph_2[/imath]?

EDIT- Wait, [imath]\aleph_1[/imath] would be the set of all ordinal numbers I listed, i.e. the countable ones, right? Alright, now I just want an example of [imath]\aleph_2[/imath]. Also, I assume [imath]\epsilon_0[/imath] is a countable ordinal? What is an example of an uncountable ordinal?

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Questions about sets

Postby Xanthir » Sat Jan 01, 2011 2:49 am UTC

Again, we're not sure of any set that's [imath]\aleph_{1}[/imath]. The reals are of cardinality [imath]\beth_{1}[/imath], while the set of all functions from R->R have cardinality [imath]\beth_{2}[/imath].

I'm not certain what sets of ordinals have particular cardinalities, though.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Questions about sets

Postby antonfire » Sat Jan 01, 2011 10:08 am UTC

Mike_Bson wrote:Wait, [imath]\aleph_1[/imath] would be the set of all ordinal numbers I listed, i.e. the countable ones, right? Alright, now I just want an example of [imath]\aleph_2[/imath].
Well, you only listed 3. Obviously you can't list the set of countable ordinals. Since that set is not countable. That set is, in fact, the first uncountable ordinal, which is usually denoted [imath]\omega_1[/imath]. Similarly, the first ordinal of cardinality more than [imath]\aleph_1[/imath] is denoted [imath]\omega_2[/imath] and has cardinality [imath]\aleph_2[/imath].

Mike_Bson wrote:Also, I assume [imath]\epsilon_0[/imath] is a countable ordinal? What is an example of an uncountable ordinal?
Yes, [imath]\epsilon_0[/imath] is the sup of countably many countable ordinals, and hence is countable. As I mentioned before, [imath]\omega_1[/imath] is an uncountable ordinal.


As is pretty standard, I use the ordinal a and the set of ordinals smaller than a interchangeably, since that's how ordinals are usually built up in the first place.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Questions about sets

Postby Mike_Bson » Sat Jan 01, 2011 11:23 am UTC

Alright, I finally completely understand it. Thank you guys so much for your help!


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests