Re: incompleteness of ZF

[Thomas Streicher <streicher@mathematik.tu-darmstadt.de>]

Dear Paul,

a short reply to your mail about inconsistency of replacement.

As Paul has already remarked in his mail the type-theoretic counterpart of
replacement is that of universe `a la Martin-Loef. As in case of replacement
the use of universes is that they allow for construction of families of types
(as e.g. needed for inverse limit constructions in Domain Theory which cannot
be performed in pure topos logic precisely for this reason).

But as already observed in a survey article by Thierry Coquand 
(ftp://ftp.cs.chalmers.se/users/cs/coquand/meta.ps.Z) and, surely, 
known to Martin-Loef himself it holds that in type theory with n+1 universes
one may prove the consistency of type theory with n universes simply by 
constructing a model using the n+1st universe. But, of course, this extra
universe is needed for the consistency proof. Accordingly, one cannot prove
the consistency of type theory with $\omega$ universes without postulating an
$\omega$th universe.

Quite the same phenomenon is going on in set theory as already pointed out by
some previous replies. However, in set theory due to the presence of 
``impredicative'' axioms the proof theoretic strength is incredibly stronger
than set of Martin-Laoef type theory with $\omega4 universes.

Best, Thomas