Working in the fragment of Martin-Löfs extensional type theory [12] which has products (but not sums) of dependent types, we consider two additional assumptions: firstly, that there are (strong) equality types; and secondly, that there is a type which is universal in the sense that terms of that type name all types, up to isomorphism. For such a type theory, we give a version of Russell's paradox showing that each type possesses a closed term and (hence) that all terms of (...) each type are provably equal. We consider the kind of category theoretic structure which corresponds to this kind of type theory and obtain a categorical version of the paradox. A special case of this result is the degeneracy of a locally cartesian closed category with a morphism which is generic in the sense that every other morphism in the category can be obtained from it via pullback. (shrink)

Paradox is a logical phenomenon. Usually, it is produced in type theory, on a type Ω of “truth values”. A formula Ψ (i.e., a term of type Ω) is presented, such that Ψ↔¬Ψ (with negation as a term¬∶Ω→Ω)-whereupon everything can be proved: In Sect. 1 we describe a general pattern which many constructions of the formula Ψ follow: for example, the well known arguments of Cantor, Russell, and Gödel. The structure uncovered behind these paradoxes is generalized in Sect. 2. This (...) allows us to show that Reynolds' [R] construction of a typeA ≃℘℘A in polymorphic λ-calculus cannot be extended, as conjectured, to give a fixed point ofevery variable type derived from the exponentiation: for some (contravariant) types, such a fixed point causes a paradox.Pursueing the idea that $$\frac{{{\text{type theory}}}}{{{\text{categorical interpretation}}}} = \frac{{{\text{(propositional) logic}}}}{{{\text{Lindebaum algebra}}}}$$ the language of categories appears here as a natural medium for logical structures. It allows us to abstract from the specific predicates that appear in particular paradoxes, and to display the underlying constructions in “pure state”. The essential role of cartesian closed categories in this context has been pointed out in [L]. The paradoxes studied here remain within the limits of the cartesian closed structure of types, as sketched in this Lawvere's seminal paper — and do not depend on any logical operations on the type Ω. Our results can be translated in simply typed λ-calculus in a straightforward way (although some of them do become a bit messy). (shrink)