Difference between a type and a set
I've been trying to understand this distinction for a while, buts its still not making sense to me.
Originally, I thought the distinction between type and set was as follows.
The relationship between any two sets is already determined. For example, given sets $A$ and $B$, either its the case that $A \subseteq B,$ or else its the case that $A \not \subseteq B.$ Along a similar vein, we can always take the union of two sets $A$ and $B$, and we always have $A \subseteq A \cup B.$ Furthermore, in a set-theoretic foundation, no function needs a codomain.
On the other hand, types "float free" in the universe, and are only related by the functions between them. Thus, we cannot write $A \cup B$ if $A$ and $B$ are types, although we can form the sum type $A + B,$ which is basically a disjoint union. Furthermore, in a type-theoretic foundation, every function needs to have a codomain.
So, that's what I used to think.
However, for a variety of reasons, the above paragraph is completely wrong! For example, there are set-theoretic foundations in which sets float free, functions have codomains, etc. (e.g. ETCS).
So now I'm just completely confused.
Can someone explain to me, once and for all, what the difference is?
It's worth recalling what Martin-Löf wrote in [Intuitionistic type theory]: (But note that Martin-Löf writes "set" for what we would call "type"!)
- What is a set?
- What is it that we must know in order to have the right to judge something to be a set?
- What does a judgement of the form "$A$ is a set" mean?
The first is the ontological (ancient Greek), the second the epistemological (Descartes, Kant, ...) and the third semantical (modern) way of posing essentially the same question. [...] So:
- a set $A$ is defined by prescribing how a canonical element of $A$ is formed as well as how two equal canonical elements of $A$ are formed.
This is the explanation of the meaning of a judgement of the form $A$ is a set.
My own view is that it doesn't make sense to compare sets and types at all – they are entities in very different worlds. The right question to ask is:
What is the difference between a set theory and a type theory?
The answer, which is hinted at by the quote above, is syntax. Set theory is a logical theory, built on top of a preexisting deductive system such as first-order logic, while type theory is a deductive system in its own right. (Well, you could formalise type theory as a certain kind of first-order theory, but I consider that to be a kind of abstraction inversion.)
One of the key differences is that terms in type theories are first-class citizens: they do not denote elements, they are elements. (That is not to say that different terms can't be equal, though – more on that later.) Of course, what one means by "element" also has to be somewhat more general than in set theory, since terms do not have to be closed: for instance, the term $\mathsf{succ} (x)$, in the context $x : \mathbb{N}$, is of type $\mathbb{N}$; so interpreted literally, it says that $\mathbb{N}$ has an "element" $\mathsf{succ} (x)$, the successor of a "variable element" $x$. One way of making concrete sense of this is to employ the notion of "generalised element" from category theory: the "variable element" $x$ is interpreted as the identity function $\mathbb{N} \to \mathbb{N}$, and similarly $\mathsf{succ} (x)$ is interpreted as the successor function $\mathbb{N} \to \mathbb{N}$. This is to be distinguished from (the interpretation of) the closed term $\lambda x : \mathbb{N} . \mathsf{succ} (x)$, which is of type $\mathbb{N} \to \mathbb{N}$ in the empty context. (This, by the way, is one reason why ETCS is considered a set theory and not a type theory – though, granted, it draws heavily from type-theoretic practices.)
A much more subtle difference between set theory and type theory is the treatment of equality. In type theory, it is possible (but not necessary) to distinguish between so-called judgemental equality (denoted by $\equiv$) and propositional equality (denoted by $=$). Judgemental equality concerns equality of terms qua terms: for instance, $1 \equiv \mathsf{succ}(0)$ because the former is an abbreviation for the latter, and (assuming consistency) we never have $x \equiv y$ when $x$ and $y$ are two different variables. This is sometimes called "definitional equality", because one usually deduces judgemental equalities by repeatedly applying definitions ("$\beta$-reduction"). No matter what you call it, judgemental equality is (supposed to be) an external metalinguistic notion, and needless to say, judgemental equality is absent in set theory.
On the other hand, propositional equality concerns semantics. Of course, judgemental equality implies propositional equality, but the converse need not hold. (If it does, then the type theory is said to be extensional.) Here's a somewhat involved example. Let $x$ and $y$ be variables of type $\mathbb{N}$. Then $x + y$ and $y + x$ are terms of type $\mathbb{N}$, defined by induction in the usual way: \begin{align*} x + 0 & \equiv x & x + \mathsf{succ}(y) & \equiv \mathsf{succ}(x + y) \\ y + 0 & \equiv y & y + \mathsf{succ}(x) & \equiv \mathsf{succ}(y + x) \end{align*} Now, by repeatedly applying definitions, one can show that $x + y \equiv y + x$ after substituting closed numerals for $x$ and $y$, so e.g. $2 + 3 \equiv 5 \equiv 3 + 2$. But that does not mean that $x + y \equiv y + x$; in fact, this judgement cannot be derived in intensional type theory! Rather, one has to use induction on $x$ and $y$, and the only kinds of equalities provable by induction are propositional equalities.
I think, to really get a good feel for type theories as a mathematician, one should either go play around with proof assistants like Coq or Agda, or otherwise try to learn what it takes to build a model of intensional type theory. My own understanding was seriously hindered by intuitions drawn from extensional type theory, which is in many ways more like set theory than not.
For a philosopher trying to get an initial handle on the conceptual difference between ZFC sets, ETCS sets, and types, Shulman's blog post is useful: https://golem.ph.utexas.edu/category/2013/01/from_set_theory_to_type_theory.html
The following quotes from his post speak to the issue. The cartoon version of the distinction is that ZFC is a propositional system, ETCS is an ontological system, and MLTT is an operational system. (Zhen Lin's answer is less cartoonish.) The bold indicates my emphasis, not Shulman's.
The basic objects of ZFC and ETCS are both called “sets”, but they behave so differently that it can be confusing to use the same name for both. For clarity, in this post I’ll call them material-sets (for ZFC) and structural-sets (for ETCS). There are a lot of differences between the two, but personally, I think one very important one is that although both kinds of sets have elements, their manner of “having elements” is different.
If $X$ is a material-set, then for any other thing $A$, we can ask whether $A\in X$. The statement $A\in X$ is a proposition in the logician’s sense: something which can be either true or false, which can be assumed as a hypothesis and proven as a conclusion, negated, combined with other propositions using conjunction, disjunction, and implication, quantified over, and so on (...)
By contrast, if $X$ is a structural-set, then there are some things which by their very nature are [given as] elements of $X$ (...) $A\in X$ should not be considered as a proposition (...).
if $\Bbb R$ is a structural-set, then the quantifier “for all $x\in \Bbb R$” is an atomic operation of logic; (...) structural-set theory matches mathematical practice more closely (...) The quantifier “for all $z\in \Bbb C$” is naturally treated as atomic, with $z$ being given as a complex number, rather than as an arbitrary thing with the additional hypothesis that it happens to be a complex number.
(...) power sets seem more natural materially. (...) natural numbers seem more natural structurally. (...) I don’t think that function sets are particularly natural in either case.
(...) we ought to seek a foundational system which contains structural-sets and their elements as basic things, but also subsets of these which behave like material-sets; contains both the structural quantifier-bounding membership and the material membership proposition; and allows elements of structural-sets to have some internal structure, but doesn’t force them to always have a particular kind of internal structure. The elements of a structural-set should have different structure depending on what that structural-set is: they may be material-sets, or functions, or ordered pairs, or natural numbers. In fact, such a foundational system already exists: it is called Martin-Löf dependent type theory (MLTT). (...) Instead of “structural-sets” we speak of types. (...)
In MLTT, we have many different ways to construct (or “form”) types, and each type-forming operation comes with rules specifying what the elements of that type are and how they behave.