Wednesday, August 5, 2015

Classes vs. sets

Over the last couple of years I've become increasingly interested in various foundational approaches to mathematics -- logic, set theory, category theory, lambda calculus, and so on. It's fascinating to see how these different schools of thought provide accounts for each other, and themselves.

Classes, simply put, are an elegant dodge to get around Russell's Paradox while retaining some of the expressive power of universal quantification.

To elaborate: if we allow a set theory to express "the set of all sets", or "the set of all cardinal numbers", or even just "the set of all singleton sets", we quickly run into the ground. Contemporary set theories like ZF give us restricted quantification, allowing us to say "$\forall x \in S \cdot P(x)$" (given a set $S$ and a predicate $P$) but not "$\forall x \cdot P(x)$". But it's still useful to be able to quantify over collections of things that are too large to be sets. E.g. "all sets either contain an element or are empty"; "all sets admit a well-ordering".

Classes (effectively) correspond to predicates in language. For example, "is a singleton set" might be described by "$\textrm{Singleton}(x) := \exists y \forall z \cdot (z \in x \Leftrightarrow y = z)$". In the usual first-order presentations of ZF, "is a set" is a predicate that always returns true. And "represents a well-ordering of $S$" might be shorthand for "$x \subseteq S^2 \land \textrm{IsWellOrdering}(x)$", where $\textrm{IsWellOrdering}$ itself is shorthand for a more complicated predicate that checks whether something encodes a reflexive antisymmetric transitive relation without infinite descending chains.

Claims that all members of a class satisfy some additional property can be encoded as universal quantifiers in the language, "$\forall x \cdot P(x) \Rightarrow Q(x)$". (The logic itself is still allowed universal quantifiers: it's the set building axioms which must be denied access to these.)

Classes typically exist in the metalanguage (i.e. are not first-class citizens of the theory itself). Classes can correspond to sets (e.g. the class of all empty sets, the class of natural numbers) but this is not guaranteed. This distinction is enough to get us past the classical presentation of Russell's paradox: