Archive for the 'Set Theory' category

From Sets to Groups: Deep Meaning in Simple Constructs

Dec 03 2007 Published by under 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 of that is something
called a group. Once we've built up sets enough to be able to understand a set of values and an operator, we're able to build an amazing deep and interesting construction, called a group.

Back when I started this blog, one of the first topics that I
wrote about was group theory. I was just looking back over that
series of posts, and frankly, they sort of stink. I've leaned a lot about
how to write for a blog in the time since then, and so I'd like to go back
and rewrite it. I've never reposted any of the group theory material, so
it should also be new to most readers.

Continue Reading »

69 responses so far

From Sets to Numbers: Climbing Up to the Rationals

Nov 29 2007 Published by under 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
up the full tower of numbers, showing how if we've got the natural numbers defined in sets, we can define
the rational numbers using sets and our constructed integers.

Continue Reading »

No responses yet

From Sets to Arithmetic

Nov 19 2007 Published by under Numbers, 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 take a bit of time to go through some basic constructions using set theory.

We've seen, roughly, how to create natural numbers using nothing but sets - that's basically what
the ordinal and cardinal number stuff is about. Even doing that much is tricky - witness my gaffe about
ordinals and cardinals and countability. (What I was thinking of is the difference between the ε series in the ordinals, and the ω series in the cardinals, not the ordinals and cardinals themselves.) But if we restrict ourselves to sets of finite numbers (note: sets of finite numbers, not finite sets of numbers!), we're pretty safe.

Of course, we haven't defined arithmetic - we've just defined numbers. You might think it would be
pretty important to define arithmetic on the numbers. If you thought that, you'd be absolutely
Correct. So, that's what I'm going to do next. First, I'm going to define addition and subtraction - multiplication can be defined in terms of addition. Division can be defined in terms of multiplication
and subtraction - but I'm going to hold off on defining division until we get to rational numbers.

Continue Reading »

34 responses so far

Tiptoeing into Type Theory

Nov 15 2007 Published by under 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 that we've looked at (ZFC and NBG), there were attempts
by changing the basis of set theory - discarding sets in favor of something similar, but
with restrictions that avoid the problems of naive set theory. Today, I'm going to
talk about an example of the latter approach, called type theory. Type theory is a
very different approach from what we've seen before, and one which is particularly
useful and interesting to people in my neck of the woods.

Continue Reading »

No responses yet

Why did Set Theory start with transfinite numbers?

Nov 11 2007 Published by under 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 to a few more posts about the beautiful world of set theory.

When you talk about set theory, you're talking about an extremely abstract notion, one which is capable of representing all sorts of structures: topological spaces, categories, geometries, graphs, functions, relations, and more. And yet, almost every description of set theory plunges straight into the cardinal and ordinal numbers. Why? That's a question that mystified me for quite a long time. Why do we take this beautiful structure, which can do so many things, and immediately jump in to these odd things about infinities?

Continue Reading »

No responses yet

Graph Searches and Disjoint Sets: the Union-Find Problem

Sep 06 2007 Published by under Computational Complexity, Graph Theory, Set 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 new vertices and edges being added to the graph, but nothing is ever removed. Some questions you might want to ask about this graph at a particular point in time are:

  • How many components are there in the graph?
  • Which component is vertex X in?
  • Are vertices X and Y in the same component?
  • How many components are there?

All of these questions are variants of a classic computer science problem, called
union-find, which also comes up in an astonishing number of different contexts. The reason for the name is that in the representation of the solution, there
are two basic operations: union, and find. Basically, the division of the graph into
components is also a partition of the vertices of the graph into disjoint sets: union find
is a problem which focuses on a particular kind of disjoint set problem, where you can modify
the sets over time.

Continue Reading »

12 responses so far

Alternative Axioms: NBG Set Theory

Jun 21 2007 Published by under 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 day that the ordinals are a proper class is an NBG proof.) NBG is an alternate formulation of set
theory which has the same proof power as ZFC, but does it with a finite set of axioms. (If
you recall, several of the axioms of ZFC are actually axiom *schemas*, which need to
be distinctly instantiated for all possible predicates.) NBG uses one axiom scheme, but
it's possible to show that that schema only expands into a finite number of distinct

Continue Reading »

10 responses so far

Ordinal Exponents and Really Big Numbers

Jun 17 2007 Published by under 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 we
can't express in terms of any finite sequence of multiplications.

Continue Reading »

27 responses so far

More on Ordinals: Ordinal Arithmetic (part 1)

Jun 13 2007 Published by under 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.

Continue Reading »

8 responses so far

From the Cardinals to the Ordinals

Jun 12 2007 Published by under 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 how big a set, even an infinite one is; we know that the elements of a set can be put in order, even if it's infinite: how do we talk about *where* an element occurs in a well-ordering of an infinite set?
For doing this, there's a construction similar to the cardinal numbers called the *ordinal numbers*. Just like the cardinals provide a way of talking about the *size* of infinitely large things, ordinals provide a way of talking about *position* within infinitely large things.

Continue Reading »

No responses yet

Older posts »