Proper classes

I apologise for the sporadicity of recent cp4space posts, but I do have several legitimate excuses (including MOG marking, which occupied a significant portion of yesterday). Naturally, it would be improper for me to prematurely release the results, so you’ll have to wait until they appear on Joseph Myers’ website.

Anyway, Cantor first proved that there are multiple distinct infinite cardinals (infinite sets that cannot be bijected), such as the naturals and reals, which are countable and uncountable, respectively. It transpires that we can get ‘sets’ which are too large to be actual sets, and these are called proper classes. For instance, we cannot have a set of all sets, but we can have a proper class of all sets, namely the von Neumann universe. All proper classes are subclasses of V, some of which we shall explore:

You might be forgiven for thinking that we can form a set Ω of all ordinals, but unfortunately this is not the case. If we could, then Ω would itself be a limit ordinal and possess a successor ordinal, Ω + 1, which cannot be an element of Ω due to the Axiom of Foundation. Hence, Ω is not a set. However, it consists entirely of sets, so is a legitimate proper class.

The class of all ordinals is a subclass of the surreal numbers, a totally ordered ‘field’ (obeying all field axioms except for failing to be a set) invented by John Conway. It is the largest possible ordered field, and contains reals, ordinals and infinitesimals, amongst other things. People have also considered the surcomplex numbers, S[i], which are the algebraic closure of the surreals. I mentioned them earlier in connection with combinatorial game theory.

A less exciting proper class is the free complete lattice. This is an object with the following properties:

  • Complete: For any set of points, there exists a supremum and an infimum.
  • Free: No additional relations are present beyond those implied by the definition.

With just one generator, x, we get a finite singleton lattice. With two generators, x and y, we also get a finite set, namely {x, y, sup(x, y), inf(x, y)}. But with three generators, x, y and z, this suddenly explodes into a proper class. Specifically, we can construct a class of points with the same cardinality as the ordinals, by taking:

  • Zero ordinal: p_0 = x;
  • Successor ordinal: p_{\alpha + 1} = x \lor (y \land (z \lor (x \land (y \lor (z \land p_{\alpha})))));
  • Limit ordinal: p_{\alpha} = supremum of p_{\beta} for all β < α.

If we only define suprema and infima for finitely many arguments, then the free lattice is merely a countable set, rather than a proper class.

This entry was posted in Uncategorized. Bookmark the permalink.

5 Responses to Proper classes

  1. Thomas says:

    I’m confused, isn’t sup(x,y) equal to either x or y? Also, if it isn’t, why isn’t sup(x,sup(x,y)) in the set?

    • apgoucher says:

      The points in a lattice are not necessarily totally-ordered. Hence, in the free lattice on two generators, sup(x, y) is greater than both x and y, so sup(x, sup(x,y)) = sup(x,y).

      • Thomas says:

        Ah, that makes more sense now. Are there other interesting lattices you can make by including other relations?

        • Thomas says:

          I’ve tried to see what happens when you add the relation y>x, or more rigorously: sup(x,y)=y (and include inf(x,y)=x if necessary) as an exercise in working with lattices. Although, I would like to know beforehand if this lattice is also a proper class, so I don’t try to do something that is impossible.

  2. It may be free, but it requires real work and sweat equity to understand it. At least for me.

Leave a Reply

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

You are commenting using your 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