Which number is bigger?

Last time, we invented the natural numbers, defining them as “prototypes” of sets of different sizes: that is, 5 is actually a particular set of cardinality 5.

This is a pretty big deal, but it’s not nearly a complete treatment. The problem with our natural numbers is that they don’t do anything yet!

Natural numbers aren’t just a bunch of objects, they’re a bunch of objects together with a bunch of tools for manipulating them. There are all sorts of things you can do with numbers:

  • you can add them
  • you can multiply them
  • you can use one as an exponent for the other
  • you can determine whether one is divisible by the other
  • you can say whether one is greater than another

That last one is probably the simplest, so we’ll deal with it first. How do we compare natural numbers?

Membership and inclusion

We’re going to introduce a little notation today. Remember how a set is determined entirely by its members? If an object (call it a) is a member of a set (call it S), we usually call a an element of S. We use the notation “a ∈ S” for the relationship “a is an element of S,” and the notation “a ∉ S” for the relationship “a is not an element of S.”

For example, if E is the set of even natural numbers, then

  • 1 ∉ E
  • 2 ∈ E
  • 13 ∉ E
  • 14 ∈ E
  • “the set of fingers on my left hand” ∉ E.

If you take sets as the most primitive objects in mathematics, then ∈ is the most primitive relation: the one on which all others are built.

Now look at the relationship between sets like

  • “the fingers on my left hand” and “the fingers on my two hands”
  • “the even natural numbers” and “the natural numbers”
  • “everyone in my calculus class” and “everyone in the University of New Hampshire.”

What these pairs of sets all have in common is just that everything in the first set must also be in the second. Or, in mathy parlance, “If a ∈ S, then a ∈ T” (assuming you call the first set S, and the second T).

In a situation like this, we call S a subset of T. There’s a symbol for this too: “S ⊆ T.”

An aside

The definition above has one sticking point: it implies that any set is a subset of itself. Look at the definition again: “S ⊆ T” means “if a ∈ S, then a ∈ T.” So “S ⊆ S” means “if a ∈ S, then a ∈ S.” And that is definitely true.

How do we fix this? Generally, we don’t—we just accept it. S really is a subset of itself, or at least it doesn’t usually cause problems to accept it as one. In the occasional cases where it does, however, we also have the term proper subset, meaning something like “subset but not equal”—so that S is a subset of itself, but not a proper subset of itself. if S is a proper subset of T, we can also write “S ⊂ T.”

Notice that the difference between the symbols ⊆ and ⊂ is similar to the difference between the symbols ≤ and <. This isn’t a coincidence.

Which set is bigger?

We already know how to say two sets are the same size: we set up a bijection between them. But what if we want to say one set is bigger than another?

Let’s look at a concrete example. Suppose you want to convince me that there aren’t enough party favors for everyone coming to my house: that the set of favors is smaller than the set of guests.

Well, if something is smaller than my set of guests, it ought to be the same size as some subset of my set of guests. So you might try the following:

  • Choose a proper subset of my set of guests: say, “everyone but Ralph.”
  • Find a bijection between the party favors and just that subset of the set of guests.
  • Panic. “There are as many party favors as there are guests except Ralph! There’ll be nothing for him!”

[IMG: a failed bijection between party favors and guests]
Poor Ralph.

In fact, this relatively simple strategy actually works!1 But we can do even better. These mysterious ‘numbers’ have helped us a lot with deciding whether two sets are the same size; maybe they can help us with this problem too.

Comparing numbers

Look at the structure of the numbers themselves:

  • 0 = {}
  • 1 = {0}
  • 2 = {0, 1}
  • 3 = {0, 1, 2}
  • 4 = {0, 1, 2, 3}
  • …..

One thing you may notice, looking over the above, is that 0 is a proper subset of 1. Or that 0 is a proper subset of 3. Or that 2 is a proper subset of 3. In fact,

0 ⊂ 1 ⊂ 2 ⊂ 3 ⊂ 4 ⊂ …..

And now we get to the point: when one natural number, n, is a subset of another, m, we’ll say n is less than or equal to m. And we’ll write it as “nm.”

There are all other sorts of comparison terms, but we can write them all in terms of ≤:

  • n ≥ m” means “mn.”
  • n > m” means “it is not the case that nm.”
  • n < m” means “it is not the case that mn.”

Using this terminology, it’s now easy to figure out whether I have too few party favors. Count them, and count the guests. If the first number is less than the second, I don’t have enough. If the first number is greater than or equal to the second, I do have enough.

[IMG: counting favors and guests]
7 < 8

Ordered sets

The relation ≤ above is an example of an ordering relation (in fact, it is probably the first example ever discovered). Combined with ≤, the collection of natural numbers goes from being a plain old set, to an ordered set: we can now say, for any two elements, either that they are actually equal, or that one is larger than the other.

It’s worth noting that any set can be made an ordered set, in any number of ways, simply by choosing an order; and that there are many possible orders on a set. For example, ≥ is actually just as good an ordering relation on the natural numbers as ≤—just a change in vocabulary, really, as using it causes us to call a set “smaller” when it’s larger, or “larger” when it’s smaller.

Or, for something completely different, we could use an order like

1 < 3 < 5 < …. < 0 < 2 < 4 < ….

That is, we could put all the odd numbers first, in order, followed by all the even numbers. This order doesn’t serve much of a purpose, but it’s still “there”.

Or we could consider the alphabet as an ordered set, with the usual order:

A < B < C < D < ….

There are a few basic rules that we expect a relation like ≤ to follow before we can really call it an ordering relation on some set S:

  1. Given two elements a and b in S, either ab or ba. (This requirement is called totality.)
  2. The only way we can have both ab and ba is if in fact a = b. (This requirement is called antisymmetry.)
  3. Conversely, in fact aa. (This requirement is called reflexivity.)
  4. Given three elements a, b, and c in S, if ab and bc, then ac. (This requirement is called transitivity.)

Fortunately for us, the subset relation on the natural numbers does satisfy these rules (you might want to verify this if you don’t believe me).

Ordered sets in general are one of the objects of study in order theory. To be perfectly honest I don’t know that much about this area—which is to say, I don’t really know what sort of questions order theorists are interested in. Anyone who would like to tell me is welcome to comment.


[1] Well, it works as long as all the sets involved are finite. I hope to deal with infinite sets in a future post.

Advertisements

3 responses to “Which number is bigger?

  1. 0 ⊂ 1 ⊂ 2 ⊂ 3 ⊂ 4 ⊂ …..

    And now we get to the point: when one natural number, n, is a subset of another, m, we’ll say n is less than or equal to m. And we’ll write it as “n ≤ m.”

    That should be “less than”, not “less than or equal”, since 3 ⊄ 3.

    • True that 3 ⊄ 3—or, read aloud, “3 is not a proper subset of 3”.
      But 3 ⊆ 3—or, read aloud, “3 is a subset of 3”.
      When n is a subset of m, it’s less than or equal to m.
      When n is a proper subset of m, it’s less than m.

      I guess I could change the ⊂ above to ⊆, so that it’s clearer what’s going on there.

  2. Pingback: Equations, and undoing operations | Irrational Inquiries

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s