# 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:

1. 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.

-
Zhen, given types $X$ and $Y$, does it ever make sense to ask whether or not they're equal? –  user18921 Sep 12 '13 at 14:07
In Martin-Löf type theory, types "are" themselves terms, so yes. More precisely, there is a hierarchy of "universes" of types, and each type belongs to some universe. Voevodsky's univalence axiom states that propositional equality of types is essentially the same thing as equivalence (i.e. internal isomorphism) of types. –  Zhen Lin Sep 12 '13 at 16:16
Okay, I'm having trouble squaring what you're saying here with what Luca Bressen wrote in his answer here. Your saying there is a hierarchy of universes of types already in existence, and I think that within any given universe, we can ask whether two types are equal. But Luca seems to be saying that types don't exist in Martin-Lof until we "create" them. Btw, how do you put the double dots above the o? –  user18921 Sep 12 '13 at 16:26
Well, you can say the same thing about terms! Perhaps the issue is linguistic. A term is something you can write down explicitly, but in a model of type theory it is possible to have elements that do not correspond to any term. In the same way, it is possible to have types in a model that don't correspond to anything that can be written down. But can these things really be said to "exist"? –  Zhen Lin Sep 12 '13 at 16:49
By the way, this is such a great answer. –  user18921 Mar 29 at 16:25