Set Theory:
Category: Set Theory
The point of set theory isn't just to sit around and twiddle our thumbs about the various definitions we can heap together. It's to create a basis on which we can build and study interesting things. A great example...
Read on »
Posted by Mark C. Chu-Carroll at 8:21 AM • 69 Comments •
Category: Set Theory
When last we left off, I'd used set theory to show how to construct the natural numbers; and then from the natural numbers, I showed how to construct the integers. Now, we can take the next step in building...
Read on »
Posted by Mark C. Chu-Carroll at 3:54 PM • 13 Comments •
Category: Set Theory
Even though this post seems to be shifting back to axiomatic set theory, don't go thinking that we're done with type theory yet. Type theory will make its triumphant return before too long. But before that, I want to...
Read on »
Posted by Mark C. Chu-Carroll at 2:53 PM • 34 Comments •
Category: Set Theory
When Cantor's set theory - what we now call naive set theory - was shown to have problems in the form of Russell's paradox, there were many different attempts to salvage the theory. In addition to the axiomatic approaches...
Read on »
Posted by Mark C. Chu-Carroll at 10:55 AM • 18 Comments •
Category: Set Theory
I was visiting my mom, and discovered that I didn't leave my set theory book on the train; I left it at her house. So I've been happily reunited with my old text, and I'm going to get back...
Read on »
Posted by Mark C. Chu-Carroll at 8:45 PM • 20 Comments •
Category: Graph Theory
Suppose you've got a huge graph - millions of nodes. And you know that it's not connected - so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly...
Read on »
Posted by Mark C. Chu-Carroll at 11:40 AM • 12 Comments •
Category: Set Theory
So far, we've been talking mainly about the ZFC axiomatization of set theory, but in fact, when I've talked about classes, I've really been talking about the von Newmann-Bernays-Gödel definition of classes. (For example, the proof I showed the other...
Read on »
Posted by Mark C. Chu-Carroll at 6:44 PM • 10 Comments •
Category: Set Theory
With ordinals, we use exponents to create really big numbers. The idea is that we can define ever-larger families of transfinite ordinals using exponentiation. Exponentiation is defined in terms of repeated multiplication, but it allows us to represent numbers that...
Read on »
Posted by Mark C. Chu-Carroll at 3:22 PM • 27 Comments •
Category: Set Theory
I'll continue my explanation of the ordinal numbers, starting with a nifty trick. Yesterday, I said that the collection of all ordinals is not a set, but rather a proper class. There's another really neat way to show that....
Read on »
Posted by Mark C. Chu-Carroll at 10:00 PM • 8 Comments •
Category: Set Theory
I've talked about the idea of the size of a set; and I've talked about the well-ordering theorem, that there's a well-ordering (or total ordering) definable for any set, including infinite ones. That leaves a fairly obvious gap: we know...
Read on »
Posted by Mark C. Chu-Carroll at 9:31 PM • 6 Comments •