If set cardinality and power sets are not functions, then what are they

elementary-set-theory

Lets say you have a (finite) set $S$ and want to know its cardinality $|S|$. Then this seems like a function
$$|\cdot|: \mathbb{S} \to \mathbb{N}$$
which certainly cannot exist, given that there is no such thing as "$\mathbb{S}$", which would be the set of all sets. The same goes for the power set $\mathcal{P}(S)$, which would look like
$$\mathcal{P} : \mathbb{S} \to \mathbb{S}$$
which also certainly makes no sense. However, these still seem like functions: they take in an input (a set) and spit out an output. So since these are not functions, what are they?

Best Answer

This is a great question, and the answer in ZFC set theory lies in the notion of a "class function". Formalizations of ZFC view it as a first-order theory in the language $\mathcal{L}=\{\in\}$, which has a single binary predicate meant to express the idea of "membership". The idea of "classes" and "proper classes" can then be formalized through the idea of $\mathcal{L}$-formulas; I recommend reading a bit about first-order logic to understand how to formalize the ideas written below.

$\mathcal{L}$-formulas are powerful enough to express the majority of constructions we want in our set theory; for instance, the following formula expresses that $X$ is a subset of $S$: $$\sigma(X,S)\equiv\forall x(x\in X\rightarrow x\in S).$$ We can then use this to create a formula expressing that $P$ is the power set of $S$: $$\eta(S,P)\equiv\forall X(X\in P\leftrightarrow\sigma(X,S)).$$ With this tool under our belt, we can codify the idea of a "class" as intuitively being the collection of all sets that satisfy a particular $\mathcal{L}$-formula. For instance, the "class" of all sets is cut out by the formula $\psi(X)\equiv X=X$. Since every set is equal to itself, every set will satisfy $\psi$, so $\psi$ "cuts out" the proper class of all sets, in some sense. Formally, we can think then of classes as equivalence classes of $\mathcal{L}$-formulas, where two $\mathcal{L}$-formulas are equivalent when one holds if and only if the other does.

With some work, it is possible in ZFC to create a class $\textbf{Card}$ of all the sets we want to consider "cardinal numbers", satisfying the properties we expect of cardinality. (If we are interested only in the cardinalities of finite sets, then we can just take $\textbf{Card}$ to be the set $\mathbb{N}$, but this construction is much more general. Look up ordinal numbers and well-orderings if you want to see the tools needed for it.) $\textbf{Card}$ is "too large" to be a set – ie, there is no set that contains every cardinal number. If there were, we would be able to recreate a Russell-like paradox. However, the property of "being a cardinal number" (when suitably defined) is expressable by a (complicated) $\mathcal{L}$-formula, and this justifies referring to $\textbf{Card}$ as a "class". For convenience, let's suppose $\phi(X)$ is a formula expressing "$X$ is a cardinal number". Let's also take $\psi(X)$ as above, so that $\psi(X)$ cuts out the class $\textbf{Set}$, consisting of all sets.

With classes under our belt, we can work on defining "class functions", which codify in some sense the idea of functions between classes. For instance, a "function" from the class $\textbf{Set}$ to the class $\textbf{Card}$ is a formula $\theta(X,Y)$ with the property that, for any $S$, if $S$ lies in the class $\textbf{Set}$ – ie if $\psi(S)$ holds – then there exists a unique $T$ such that $T$ lies in the class $\textbf{Card}$ – ie, such that $\phi(T)$ holds – and such that $\theta(S,T)$ holds. If $\theta$ further satisfies that there exists a bijection between $S$ and the unique cardinal number $T$ such that $\theta(S,T)$ holds, we then denote this unique $T$ by $|S|$ and consider $\theta(X,Y)$ to define the "cardinality" operation that you mention.

Similarly, the "power set" operation that you mentioned is a class function from $\textbf{Set}$ to $\textbf{Set}$. In fact, the formula $\eta(X,Y)$ that I've given above defines the power set class function! The fact that, for each set $S$, there is a unique set $P$ satisfying $\eta(S,P)$ is one of the axioms of ZFC, and this justifies our claim that $\eta$ is in fact a class function. (Actually, to be pedantic, the existence of $P$ is one of the axioms of ZFC, and uniqueness follows from a different axiom called "extensionality", which says that two sets are equal if and only if they have the same elements.)

These ideas lie at the root of the deep field of set theory, and are covered in any good introductory resource on the subject. If you find them interesting I very much recommend learning them in detail! For instance, here is a good set of lecture notes that should hopefully be accessible, which covers all of the ideas above (and many more) in detail.

Related Question