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:

Monday, August 3, 2015

“Endless, formless ruins” (Invisible Cities)

In the lives of emperors there is a moment which follows pride in the boundless extension of the territories we have conquered, and the melancholy and relief of knowing we shall soon give up any thought of knowing and understanding them. There is a sense of emptiness that comes over us at evening, with the odor of the elephants after the rain and the sandalwood ashes growing cold in the braziers, a dizziness that makes rivers and mountains tremble on the fallow curves of the planispheres where they are portrayed, and rolls up, one after the other, the despatches announcing to us the collapse of the last enemy troops, from defeat to defeat, and flakes the wax of the seals of obscure kings who beseech our armies’ protection, offering in exchange annual tributes of precious metals, tanned hides, and tortoise shell. It is the desperate moment when we discover that this empire, which had seemed to us the sum of all wonders, is an endless, formless ruin, that corruption’s gangrene has spread too far to be healed by our scepter, that the triumph over enemy sovereigns has made us the heirs of their long undoing. Only in Marco Polo’s accounts was Kublai Khan able to discern, through the walls and towers destined to crumble, the tracery of a pattern so subtle it could escape the termites’ gnawing.
Italo Calvino, Invisible Cities