In ZFC there seem to be two ways to define a function, as an ordered triple of domain, codomain and the set of ordered pairs that make its graph, or a relation over the two sets.

Whichever we use doesn't matter, but this seems to present a certain problem. Both are defined over sets, but no-one seems to have any problem defining functions on the ordinals like Hartog's function giving the minimum ordinal that doesn't have an injective function on to the given ordinal. I know we want to be able to obviously, but how are we supposed to justify this, because the definitions of functions don't seem to include classes. Or is there a nicer definition I've missed?


Instead of a set, require that a function is a collection of ordered pairs with the property that if $\langle u,x\rangle$ and $\langle u,y\rangle$ are both in the collection then $x=y$.

Classes in ZFC are syntactic objects, these are the definable sub-collections of "$V=\{x\mid x=x\}$", so a class is a collection (which might not be a set) of the form $\{x\mid\varphi(x)\}$ for some $\varphi$.

Ordinal functions, or in general class functions, are (in the context of ZF) definable classes of the form $\{\langle x,y\rangle\mid\varphi(x,y)\}$ which has the functional property. For example the Hartogs number function makes use of the fact that we can define from ZF what are the ordinals, what are injective functions, etc. then using a parameter $x$ we can define the least ordinal which is not injected into $x$. This goes into a formula $\varphi(x,y)$ which says all of the above.

Two simple and even more natural examples of class functions are:

  1. The power set function, $\{\langle x,\mathcal P(x)\rangle\mid x\in V\}$ where $\mathcal P(x)$ denotes the power set of $x$. The axiom of power set tells us that this set exists and extensionality tells us it is unique.

  2. The union function, $\{\langle x,\bigcup x\rangle\mid x\in V\}$ where $\bigcup x=\{z\mid\exists u(u\in x\land z\in u)\}$. Again we adhere to the axioms, this time to the axiom of union and the axiom of extensionality to argue that this function is well defined.

The von Neumann hierarchy, the Constructible hierarchy, the Fine structure hierarchy, and many other similar ways to construct models of set theory are exactly class-functions from the ordinals.

To read some more:

  1. class function question
  2. What are some examples of classes that are not sets?
  3. In NBG set theory how could you state the axiom of limitation of size in first-order logic?
  • $\begingroup$ This seems incredibly simple, I love it, thank you. I've gone through so many resources all using the definitions I gave, when they just don't work, it's a wonder they get published. Is there any chance you'd know of any references for this definition? While I'm happy with it, I don't think stackexchange is something I can reference. $\endgroup$
    – AaronM
    Apr 26 '12 at 17:58
  • $\begingroup$ @AaronM: I suppose you are not publishing in a logic related journal, because I think this sort of thing is too simple to actually care about. I'll run through Jech and several other introductory books which have a few remarks about classes, <strike>if I will find something I will let you know.</strike> Jech, Set Theory pp. 11-12 (bottom of page 11, top of 12) he remarked that the definitions of a function can be applied to classes as well. I suppose that should do, or do you need to reference exactly how classes are treated in ZF? $\endgroup$
    – Asaf Karagila
    Apr 26 '12 at 18:00
  • $\begingroup$ Haha I guess it shows I'm new to published stuff. Thank you very much though, this is a far better answer than I hoped for, you've been a brilliant help. Edit: That will do brilliantly thank you. I've had a hard time getting hold of that book, typical it would be the one which has the answer I want! :p $\endgroup$
    – AaronM
    Apr 26 '12 at 18:06
  • $\begingroup$ @AaronM: I haven't published anything anywhere. However this sort of thing is not the type of things you see mentioned in papers beyond mentioning that a particular function is a class function, and justifying the well-definition of the formula defining the class if needed. $\endgroup$
    – Asaf Karagila
    Apr 26 '12 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.