You are here
HomeRussell's theory of types
Primary tabs
Russell’s theory of types
After the discovery of the paradoxes of set theory (notably Russell’s paradox), it become apparent that naive set theory must be replaced by something in which the paradoxes can’t arise. Two solutions were proposed: type theory and axiomatic set theory based on a limitation of size principle (see the entries class and von NeumannBernaysGödel set theory).
Type theory is based on the idea that impredicative definitions are the root of all evil. Bertrand Russell and various other logicians in the beginning of the 20th century proposed an analysis of the paradoxes that singled out so called vicious circles as the culprits. A vicious circle arises when one attempts to define a class by quantifying over a totality of classes including the class being defined. For example, Russell’s class $R=\{x\mid x\not\in x\}$ contains a variable $x$ that ranges over all classes.
Russell’s type theory, which is found in its mature form in the momentous Principia Mathematica avoids the paradoxes by two devices. First, Frege’s fifth axiom is abandoned entirely: the extensions of predicates do not appear among the objects. Secondly, the predicates themselves are ordered into a ramified hierarchy so that the predicates at the lowest level can be defined by speaking of objects only, the predicates at the next level by speaking of objects and of predicates at the previous level and so forth.
The first of these principles has drastic implications to mathematics. For example, the predicate “has the same cardinality” seemingly can’t be defined at all. For predicates apply only to objects, and not to other predicates. In Frege’s system this is easy to overcome: the equicardinality predicate is defined for extensions of predicates, which are objects. In order to overcome this, Russell introduced the notion of types (which are today known as degrees). Predicates of degree 1 apply only to objects, predicates of degree 2 apply to predicates of degree 1, and so forth.
Type theoretic universe may seem quite odd to someone familiar with the cumulative hierarchy of set theory. For example, the empty set appears anew in all degrees, as do various other familiar structures, such as the natural numbers. Because of this, it is common to indicate only the relative differences in degrees when writing down a formula of type theory, instead of the absolute degrees. Thus instead of writing
$\exists P_{1}\forall x_{0}(x_{0}\in P_{1}\leftrightarrow x_{0}\neq x_{0})$ 
one writes
$\exists P_{{i+1}}\forall x_{i}(x_{i}\in P_{{i+1}}\leftrightarrow x_{i}\neq x_{% i})$ 
to indicate that the formula holds for any $i$. Another possibility is simply to drop the subscripts indicating degree and let the degrees be determined implicitly (this can usually be done since we know that $x\in y$ implies that if $y$ is of degree $n$, then $x$ is of degree $n+1$). A formula for which there is an assignment of types (degrees) to the variables and constants so that it accords to the restrictions of type theory is said to be stratified.
The second device implies another dimension in which the predicates are ordered. In any given degree, there appears a hierarchy of levels. At first level of degree $n+1$ one has predicates that apply to elements of degree $n$ and which can be defined with reference only to predicates of degree $n$. At second level there appear all the predicates that can be defined with reference to predicates of degree $n$ and to predicates of degree $n+1$ of level 1, and so forth.
This second principle makes virtually all mathematics break down. For example, when speaking of real number system and its completeness, one wishes to quantify over all predicates of real numbers (this is possible at degree $n+1$ if the predicates of real numbers appear at degree $n$), not only of those of a given level. In order to overcome this, Russell and Whitehead introduced in PM the socalled axiom of reducibility, which states that if a predicate $P_{n}$ occurs at some level $k$ (i.e. $P_{n}$ = $P_{n}^{k}$), it occurs already on the first level.
The philosopher and logician Frank Plumpton Ramsey (19031930) was the first to notice that the axiom of reducibility in effect collapses the hierarchy of levels, so that the hierarchy is entirely superfluous in presence of the axiom. The original form of type theory is known as ramified type theory, and the simpler alternative with no second hierarchy of levels is known as unramified type theory or simply as simple type theory.
One descendant of type theory is W. v. Quine’s system of set theory known as NF (New Foundations), which differs considerably from the more familiar set theories (ZFC, NBG, MorseKelley). In NF there is a class comprehension axiom saying that to any stratified formula there corresponds a set of elements satisfying the formula. The Russell class is not a set, since it contains the formula $x\in x$, which can’t be stratified, but the universal class is a set: $x=x$ is perfectly legal in type theory, as we can assign to $x$ any degree and get a wellformed formula of type theory. It is not known if NF axiomatises any extensor (see the entry class) based on a limitation of size principle, like the more familiar set theories do.
In the modern variants of type theory, one usually has a more general supply of types. Beginning with some set $\tau$ of types (presumably a division of the simple objects into some natural categories), one defines the set of types $T$ by setting

if $a,b\in T$, then $(a\rightarrow b)\in T$

for all $t\in\tau$, $t\in T$
One way to proceed to get something familiar is to have $\tau$ contain a type $t$ for truth values. Then sentences are objects of type $t$, open formulae of one variable are of type $\mathbf{Object}\rightarrow t$ and so forth. This sort of type system is often found in the study of typed lambda calculus and also in intensional logics, which are often based on the former.
Mathematics Subject Classification
03B15 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new question: Prime numbers out of sequence by Rubens373
Oct 7
new question: Lorenz system by David Bankom
Oct 19
new correction: examples and OEIS sequences by fizzie
Oct 13
new correction: Define Galois correspondence by porton
Oct 7
new correction: Closure properties on languages: DCFL not closed under reversal by babou
new correction: DCFLs are not closed under reversal by petey
Oct 2
new correction: Many corrections by Smarandache
Sep 28
new question: how to contest an entry? by zorba
new question: simple question by parag
Comments
Why this entry speaks of typed lambda calculus and intension...
There is in this entry a bit of information that surely deserves it's own entry. Modern type systems, typed lambda calculi and intensional logic should all be defined and described in entries of their own. If I have the time, I'll write these.