9
$\begingroup$

As a result of Russell's paradox (and maybe other problems I'm not aware of), naive set theory had to be replaced, and Russell himself proposed type theory, which (if I understand correctly) replaced the language of set theory with a different one. (And I read it is somehow related to something called $\lambda$-calculus).

However, Zermelo–Fraenkel set theory (ZFC) also took care of Russell's paradox, by formulating restrictive axioms on sets.

Mathematicians clearly have favored ZFC over type theory as a foundation for mathematics. and therefore most people (including myself) are familiar with set theory but not necessarily with type theory.

What are the downsides of type theory compared to set theory?

What are benefits of type theory over ZFC set theory?

$\endgroup$

closed as too broad by Rob Arthan, астон вілла олоф мэллбэрг, Morgan Rodgers, Namaste, kingW3 Feb 7 '17 at 15:19

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Benefits of $\mathsf {ZFC}$ : see the standard presentation of any algebra or real analysis textbook : you can develop the basic concepts of all math disciplines in terms of the fundamental set concept. Basically, the initial success of set theory was due to its adoption by the mathematician community. $\endgroup$ – Mauro ALLEGRANZA Feb 5 '17 at 14:39
  • 3
    $\begingroup$ For Type Theory, see William Farmer, The Seven Virtues of Simple Type Theory. $\endgroup$ – Mauro ALLEGRANZA Feb 5 '17 at 14:40
  • 3
    $\begingroup$ I think this is too broad for MSE. Any serious attempt to answer either question would be an essay and would still end up being largely a matter of personal opinion. I suggest you have a look at en.wikipedia.org/wiki/Type_theory and the references it gives, e.g., the paper by Bill Farmer. Then come back with some more specific questions if you have them. (@Mauro: great minds ...!) $\endgroup$ – Rob Arthan Feb 5 '17 at 14:41
  • 2
    $\begingroup$ I think a major part of the appeal of ZFC is ultimately a consequence of it being a form of untyped higher order logic. $\endgroup$ – Hurkyl Feb 6 '17 at 8:43
  • $\begingroup$ The links between type-theory, lambda calculus and proofs-as-programs which makes modern type theory useful where discovered in the 1980s which put it at a disadvantage to ZFC $\endgroup$ – Q the Platypus Feb 7 '17 at 4:01
14
$\begingroup$

I'm going to answer your title question but not the two questions in the body. As the comments correctly point out, doing so well could fill a book. That said, I think there are a few technical aspects that were likely factors, which I'll talk about, and then, no doubt, plenty of historical and political factors which I'm not going to talk about. These technical factors, while, of course, still true, don't have the force today that they did in the early parts of the 20th century. The choice today is clearly driven by history and pedagogical "infrastructure". My impression is most mathematics students (even restricted to graduate students) aren't even aware that there is a thing called "type theory" except maybe vaguely. (As a terminological note, by "type theory" I'll usually mean conceptual descendants of Russell's type theory, by all accounts I've read, Russell's early formulation of type theory was a bit of a mess.)

Now the actual answer. The first thing you should note if you look at Farmer's paper, even just the abstract, is that type theory isn't an alternative to set theory, it's an alternative to first-order logic (FOL). A type theory is another kind of logic; it's not a theory within first-order logic like set theory. In other words, type theory (as a foundation) is a logical basis for mathematical constructions while set theory could be called, for lack of a better word1, a "mathematical" basis for mathematical constructions. This isn't a big surprise. This is the spirit of Logicism. There are three things that can be taken from this, and I'll elaborate on each below. First, type theory was a brand new logic. Second, from a philosophy of math perspective these two approaches suggest very different philosophies. Third, axiomatizing of set theory via ZFC is a kind of "reduction" of set theory to first-order logic.

While the formal details of FOL were being worked out around this time, more or less equivalent informal systems had been used since antiquity. As far as I know formally formulating FOL went smoothly. FOL was widely accepted, or at least easy to accept. Type theory was nothing like this at the time. Type theory was effectively adding new "rules of inference" without a satisfying basis. Presentations of type theory were complicated and unclear. One of the major issues with type theory is that it effectively made the notion of "function" or "predicate" first-class. One of the things going for FOL was the notion of semantics for it was uncontroversial. In modern terms we usually use set theory to talk about the semantics of a first-order theory, but any such semantics doesn't require the notion of powersets or the axiom of infinity or that the elements of the domain themselves be sets. Basically, all you need is cartesian products and bounded comprehension. Semantics for type theory would require function spaces or powersets. But figuring out what "functions" were was one of the problems that precipitated the "crisis of foundation".

Type theory, though, wasn't meant to be used like FOL. FOL is like a specification language. A first-order theory is like a specification, and we're primarily interested in models of the theory, i.e. things that fit the specification. This lends itself to a Platonist reading: things exist and FOL lets us talk about them. From this point of view, ZFC set theory is a way of talking about "sets" which "intuitively exist". The fundamental leap of faith is that ZFC has a model. Type theory is more like a programming language. There's no need to worry about models (though this is a rich and powerful field nowadays) because you can just construct what you want in type theory itself, out of "pure logic" so to speak. Nevertheless, people still want to know what "functions" and "predicates" are and there are two natural answers. First, the abstract answer is "something we can apply to an argument" and generally satisfies the appropriate rules. This leads people to wonder if there are such things and this leads back to semantics. The second answer is "anything you can write down of the appropriate type". This is much closer to a Formalist philosophy. This says a function, and everything else, is pure syntax. This line of thought does and did lead to computer science. The former approach doesn't really seem to help in solving the problem of foundations; the latter approach was poorly understood at the time and as time progressed it became increasingly clear that it led to a rather different mathematics.

Another perspective on what set theory is is that it is an "implementation" of (untyped) higher order logic in terms of first order logic. FOL is like a low-level programming language and ZFC is like a "machine program" in that language, while type theory is like a high level language. (Note again how type theory and set theory are different kinds of things.) From a usability perspective, this makes ZFC cumbersome. From a foundations perspective, though, this is exactly what you want. Arguably ZFC does reasonably well compared to type theories at minimizing the complexity needed to formalize a language that can reasonably handle all of mathematics, see Is ZFC a Hack?. (This paper includes the cost of formalizing FOL as well, so the picture is even rosier for ZFC if you take FOL as a given.)

Ultimately, it seems that by the time type theorists got their act together mathematicians were already getting comfortable with set theory and were no longer that concerned about foundations. Instead, computer scientists picked up type theory. Nowadays the unexpected but deep connections between type theory and category theory plus the completely expected but still deep connections between type theory and computer science have led a growing renaissance of type theory in mathematics. Constructivists have also laid a lot of ground work in showing that you actually can do a lot of mathematics "syntactically", and category theory has shown that even if you're not a constructivist, this is extremely profitable. Type theory has matured over the past hundred years.

1 Maybe someone can provide me with a better word...

$\endgroup$
  • $\begingroup$ "by "type theory" I'll usually mean conceptual descendants of Russell's ramified type theory, by all accounts I've read, ramified type theory was a bit of a mess." — Is there a typo here? Was the first "ramified" supposed to be "simple" or "unramified"? $\endgroup$ – bof Feb 7 '17 at 3:05
  • $\begingroup$ I'm not sure what you mean by a "non-trivial" model of ZFC--any model at all is rather non-trivial... $\endgroup$ – Eric Wofsey Feb 7 '17 at 3:06
  • $\begingroup$ @bof All I'm really trying to say there is that I'm not using "type theory" to mean specifically one of the early systems Russell proposed but I'm including simplifications/reformulations as e.g. by Chwistek and Church (and ultimately modern variants though my intent for all but the last paragraph is more focused on '10s-'30s era). I can probably just removed "ramified" entirely for this purpose. $\endgroup$ – Derek Elkins Feb 7 '17 at 3:41
  • $\begingroup$ @EricWofsey If ZFC is inconsistent, would it not then permit a trivial model? I was hesitant about bothering with adding the adjective "non-trivial". My point there was, from a Platonist perspective, if ZFC is inconsistent, "sets" still exist, ZFC was just a bad way of describing them. $\endgroup$ – Derek Elkins Feb 7 '17 at 3:44
  • $\begingroup$ If ZFC is inconsistent, it has no models at all. $\endgroup$ – Eric Wofsey Feb 7 '17 at 3:46
3
$\begingroup$

One of the problems with your question is that many of these terms have changed over time. I have studied the continuum hypothesis for the last thirty years with the conviction that the independence of the question lies with a problem with how logic is addressed. In pursuing this conviction I have traced certain questions through translations of original sources all the way back to Aristotle.

The expression "type theory" is now vague. What Russell introduced to avoid what he believed to be the source of the contradiction is best called "predicative mathematics". In Zermelo-Fraenkel set theory this is implemented through the axiom of foundation. The sets obtained in the cumulative hierarchy are said to be "well-founded". Thus, one has individuals, sets of individuals, sets of sets of individuals, and so on. This is the predicative structure which Russell introduced with "types". In modern Zermelo-Fraenkel set theory, this is restricted somewhat since its usual interpretation is that of a theory of pure sets. That is, this predicative hierarchy is generated from a single individual called the empty set.

One reason that mathematicians followed Zermelo-Fraenkel set theory is probably the simple fact of reputation for the Hilbert school. But, Russell's approach had certain problems beyond the complexity of typed formulas that diminished its ability to influence the mathematics community. One of these had been the axiom of reducibility. This had been the axiom to which Skolem objected. Another had been the inability to eliminate an axiom of infinity. This is what Goedel ridiculed (very nice man, that) with his constructible universe. And, within the philosophy community, Russell's use of definite descriptions had been found objectionable. Such descriptions constitute an "epistemic warrant" for uses of identity. Typically, this is called the principle of identity of indiscernibles. The philosophical objection is that one cannot "define" an existent. This criticism, however, ignores what Russell wrote in his paper "On denoting".

When you ask about benefits of type theory in the context of Russell's work, you probably need to look at Quine's New Foundations and those authors who have been studying it. Quine's theory simplifies the complexity of working with typed formulas. But, the sense in which it has an advantage over Zermelo-Fraenkel set theory is that it supports what are called Fregean number classes. Logicism has two senses. One is the historical development of British mathematics after the dispute between Newton and Leibniz. Newton had set a standard with the infinitesimal calculus. So, pursuit of a logical calculus had been a higher priority in British mathematics. The work of Peacock and de Morgan is sometimes seen as anticipating modern model theory under this account of history. But, logicism in the sense of Frege had been based on the idea that natural numbers could be defined with respect to the logical notion of a "class". So Quine's work is a natural development of Frege's ideas through Russell's type theory.

Because the Quinean notion of a individual is developed with respect to ideas from the lambda calculus, there is a relationship. However, I do not believe that Church's work originates from the ideas of Russell's type theory directly. From what I can tell in the literature of computation, Church had introduced the lambda calculus in pursuit of a notion of effective computation.

In modern mathematics and computation, the notion of type is not bound to Russell's notion of predicative mathematics. A separate development called category theory began to speak of objects with morphisms between them. Within a category, objects are always associated with an identity morphism. Modern notions of type are more like the Aristotelian notion of class in which identity is a notion local to a type. In turn, this is more like category theory.

There will be those who disagree with what I have said. But, I have tried to answer your questions to the best that I can. I hope it helps.

$\endgroup$
  • 2
    $\begingroup$ I am curious what you mean by "This is what Goedel ridiculed (very nice man, that) with his constructible universe" - can you elaborate? I don't see how $L$ has anything to do with an inability to eliminate an axiom of infinity. $\endgroup$ – Noah Schweber Feb 7 '17 at 3:09
0
$\begingroup$

@noah

I have to reply this way as I am not a member.

First, let me apologize to you and the community. There is a great deal of nasty innuendo in the original sources of foundational literature. A famous example is Russell's "honest toil" comment. These kinds of comments are something I dislike. But, it is so easy to do that I find myself having committed the same. And, on the Internet it often leads to pandemonium.

I was going to write something longer as justification for my misstep. It may have been informative. But, it would have been a further discourtesy.

The quote which bothers me with how Goedel viewed Russell's work can be found in Goedel's collected works. It is also in Kanamori. It reads,

"... there was a special obstacle which really made it practically impossible for constructivists to discover my consistency proof. It is the fact that the ramified hierarchy, which had been invented expressly for constructive purposes, had to be used in an entirely nonconstructive way."

One reason I dislike this quote is that Zermelo-Fraenkel set theory specifically stipulates that the theory has no proper classes. And, Zermelo had clearly been following Fregean views of logic in the manner through which he specified his domain. Having read Frege, I know that his semantics corresponded with what we now know as negative free logic. If you visit the SEP page on free logic and compare the semantics for positive free logic and negative free logic, you will find that Goedelian metatheory is positive free logic.

It is breaking the rules. Of course, proponents of first-order logic as mathematical logic view it through the lens of "progress".

$\endgroup$

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