{"id":440,"date":"2007-06-10T21:22:42","date_gmt":"2007-06-10T21:22:42","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/06\/10\/set-cardinalities-and-the-cardinal-numbers\/"},"modified":"2007-06-10T21:22:42","modified_gmt":"2007-06-10T21:22:42","slug":"set-cardinalities-and-the-cardinal-numbers","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/06\/10\/set-cardinalities-and-the-cardinal-numbers\/","title":{"rendered":"Set Cardinalities and the Cardinal Numbers"},"content":{"rendered":"

One of the strangest, and yet one of the most important ideas that grew out of set theory is the idea of cardinality<\/em>, and the cardinal numbers<\/em>.
\nCardinality is a measure of the size<\/em> of a set. For finite sets, that’s a remarkably easy concept: count up the number of elements in the set, and that’s its cardinality. But there are interesting questions that we can ask about the relative<\/em> size of different sets, even when those sets have an infinite number of elements. And that’s where things get really fun.<\/p>\n


\nWe’ve already seen an example of how to compare the cardinality of different infinite sets: Cantor’s diagonalization. The idea of measuring relative cardinality is based on the use of one-to-one functions between sets. If I have two sets S and T, and there is a total, onto, one-to-one function from S to T, them S and T have the same cardinality.
\nIt seems like a simple notion, but it leads to some very strange results. For example, the set of even natural numbers has the same cardinality as the set of natural numbers: f(x)=2*x is a total, one-to-one, onto function from the set of naturals to the set of even naturals. So the set of even naturals and the set of all naturals have the same size<\/em>, even though the set of evens is a proper subset<\/em> of the set of natural numbers.
\nWhen we look at most sets, we can classify them into one of three cardinality classes: finite sets<\/em>, whose cardinality is smaller<\/em> that the cardinality of the natural numbers; countable sets<\/em>, which have the same cardinality as the set of natural numbers; and uncountable sets<\/em> which have a cardinality greater than<\/em> the cardinality of the natural numbers.
\nSet theorists, starting with Cantor, created a new kind of number just for describing the relative cardinalities of different sets. Before set theory, people thought that for talking about sizes, there were finite numbers, and there was infinity<\/em>. But set theory showed that that’s not enough: there are different infinities.
\nTo describe the cardinalities of sets, including infinite sets, you need a system of numbers that includes something more than just the natural numbers: Cantor proposed what is know as the cardinal numbers<\/em>: the cardinal numbers consist of the natural numbers plus the transfinite numbers<\/em>. The transfinite numbers specify the cardinality of infinite sets. The first transfinite number is written ℵ0<\/sub> (pronounced aleph-null), and it’s the size of the set of natural numbers.
\nHere’s where the really nifty trick comes in. The same trick used in Cantor’s diagonalization can be used to prove that for any non-empty set S, the set of all subsets of S (also called the powerset of S<\/em>) – is strictly larger<\/em> – that is, has greater cardinality than S. So given the smallest infinite set, you can prove that there’s got to be another infinite set larger, and one larger than that, and so on – an infinite sequence of ever-larger infinite numbers: ℵ0<\/sub> < ℵ1<\/sub> < ℵ2<\/sub>, …
\nCantor proposed that the first infinite set larger than ℵ0<\/sub> was of size 2ℵ0<\/sub><\/sup>, which is the size of the set of reals. That proposition is known as the continuum hypothesis<\/em> – if that were true, then ℵ1<\/sub>=2ℵ0<\/sub><\/sup>.
\nThere’s also an extended version
\nof the continuum hypothesis: the generalized continuum hypothesis<\/em>, which says that
\nfor every infinite set S, there are no cardinals between the cardinality of S, and the cardinality of the powerset of S – so ℵ1<\/sub>=2ℵ0<\/sub><\/sup>, ℵ2<\/sub>=2ℵ1<\/sub><\/sup>, and so on.
\nThe continuum hypothesis remains unproven. in fact, it’s more than unproven: it’s unprovable<\/em> using ZFC.<\/p>\n","protected":false},"excerpt":{"rendered":"

One of the strangest, and yet one of the most important ideas that grew out of set theory is the idea of cardinality, and the cardinal numbers. Cardinality is a measure of the size of a set. For finite sets, that’s a remarkably easy concept: count up the number of elements in the set, and […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[56],"tags":[],"class_list":["post-440","post","type-post","status-publish","format-standard","hentry","category-set-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-76","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/440","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=440"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/440\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=440"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=440"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=440"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}