While I’ve been writing about the Surreal numbers lately, it reminded me of some of the fun of Set theory. As a result, I’ve been going back to look at some old books. Since I’ve been enjoying it, I thought you folks would as well.<\/p>\n
Set theory, along with its cousin, first order predicate logic, is pretty much the There’s a reason for that. Set theory starts with some of the simplest<\/em> ideas, and extends in a reasonably straightforward way to encompass the most astonishingly complicated one. It’s truly remarkable in that – none of the competitors to set theory So I’m going to write a bit about set theory as I explore my old books. And I thought that a good place to start was Cantor’s diagonalization. Cantor is the inventor of set theory, and the diagonalization is an example of one of the first major results that Cantor published. It’s also a good excuse for talking a little bit about where set theory came from, which is not what most people expect. Set theory was originally created as a tool for talking about the relative sizes of different infinities.<\/p>\n <\/p>\n Almost anyone who went to school in the last 40 years has had some<\/em> exposure to sets, so we tend to think of them in terms of foundations. It surprises most people that sets were not<\/em> proposed as a foundation at all: in fact, set theory started as Cantor’s original idea was to abstract away the details of numbers – order, structure, etc., and just look at them as collections of objects – that is, as sets. Then, if you can create a one-to-one correspondence between two sets of numbers, then those sets must be the same size. But when you look at the set of real numbers and the set of rational numbers, there’s no way to create a one-to-one mapping: in fact, you can easily prove that any<\/em> one-to-one mapping between the rationals and the reals will necessarily It’s worth taking the time to repeat that basic proof here. I’m going to use a slightly simplified version, which shows that you can’t map between the natural numbers and the reals between 0 and 1; since it’s easy to show that there’s a one-to-one mapping between the natural numbers and the rationals; and that there’s a one-to-one mapping between the set of all reals between 0 and 1 and the set of all reals, it means the same thing, but there are less tricks involved.<\/p>\n It’s a basic proof by contradiction. Suppose that we can<\/em> create a one-to-one correspondence between the natural numbers and the reals between 0 and 1. What that would mean is that there would be a total one-to-one onto function R from the natural numbers to the reals. So we could create a complete list of all of the real numbers: R(0), R(1), R(2), …<\/p>\n If we could do that, then we could also<\/em> create another function, D (for digit<\/em>), where D(x,y)=the y<\/em>th digit of the binary expansion of R(x). So D is effectively a table where every row is a real number, and every column is a digit position in the binary expansion of a real number. D(x,3) is the third digit of the binary expansion of x. So, for example, if x=3\/8, then the binary expansion of x is 0.011. So D(3\/8,1)=0, D(3\/8,2)=1, D(3\/8,3)=1, D(3\/8,4)=0, …<\/p>\n Now, here comes the nifty part. Take the table for D, and start walking down the diagonal. So we’re going to go down the table looking at D(1,1), D(2,2), D(3,3), and so on. And as we walk down that diagonal, we’re going to write down digits. For D(0,0), the first digit, we’ll write 0 if D(0,0)=1, and 1 if D(0,0)=0. We’ll do the same thing for each digit. For the i<\/em>th digit, if D(i,i)=0, we’ll write 1, and if D(i,i)=1, we’ll write 0.<\/p>\n The result that we get is a series of binary digits – that is, a binary expansion of some number. Let’s call that number T. T is different<\/em> from every row in D in at least one digit – for the i<\/em>th row, T is different at digit i<\/em>. So there’s no x where R(x)=T. But T is clearly a real number between 0 and 1. So the mapping can’t So the set of all real numbers between 0 and 1 is strictly larger<\/em> than the set of all natural numbers. And by extension, the set of all real numbers is strictly larger<\/em> than the set of all rational numbers.<\/p>\n That argument is called Cantor’s diagonalization. And it’s pretty much the argument While I’ve been writing about the Surreal numbers lately, it reminded me of some of the fun of Set theory. As a result, I’ve been going back to look at some old books. Since I’ve been enjoying it, I thought you folks would as well. Set theory, along with its cousin, first order predicate logic, […]<\/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-419","post","type-post","status-publish","format-standard","hentry","category-set-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-6L","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/419","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=419"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/419\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=419"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nfoundation of nearly all modern math. You can<\/em> construct math from a lot of
\ndifferent foundations, but axiomatic set theory is currently pretty much the<\/em> dominant approach. (Although Topoi seem to be making some headway…)<\/p>\n
\nas a foundation can approach the intuitive simplicity of set theory.<\/p>\n
\nan outgrowth of number theory! Back in the 19th century, Cantor was doing work on
\nnumber theory and algebra, and invented what grew into set theory as a tool for comparing
\nthe sizes of various sets of numbers. The original motivation behind the ideas that ended up growing into set theory was Cantors recognition of the fact that there’s a difference<\/em> between the size of the set of rational numbers, and the size of the set of real numbers. They’re both infinite – but they’re not<\/em> the same!<\/p>\n
\nomit some of the real numbers. <\/p>\n
\npossible work. And since we didn’t specify the structure of the mapping – we just assumed that there was one<\/em>, that means that there’s no possible mapping that will work: this construction will always create a counterexample showing that the mapping is incomplete.<\/p>\n
\nthat put set theory on the map.<\/p>\n","protected":false},"excerpt":{"rendered":"