Truth definitions without exponentiation and the \(\Sigma _{1}\) collection scheme. (English) Zbl 1245.03058

The paper presents three results related to the notoriously difficult open problem: Is the theory \(\mathrm{I}\Delta_0+\lnot \mathrm{exp}+\lnot \mathrm{B}\Sigma_1\) consistent? It is well known that if there is a model of \(\mathrm{I}\Delta_0+\lnot \mathrm{exp}\) with a universal \(\Sigma_1\) formula, then there is also a model of \(\mathrm{I}\Delta_0+\lnot \mathrm{exp}+\lnot \mathrm{B}\Sigma_1\). The first result weakens the assumption a bit. It is shown that if there is a model of \(\mathrm{I}\Delta_0+\lnot \mathrm{exp}\) with cofinal \(\Sigma_1\)-definable elements and a \(\Sigma_1\) truth definition for sentences, then \(\mathrm{I}\Delta_0+\lnot \mathrm{exp}+\lnot \mathrm{B}\Sigma_1\) is consistent. It is not know whether such models exist, but in the second part the authors show that there is a model of \(\mathrm{I}\Delta_0+\Omega_1+\lnot \mathrm{exp}\) in which \(\Sigma_1\) definable elements are cofinal and for which there is a \(\Sigma_2\) truth definitions and \(\Pi_2\) truth definition for \(\Sigma_1\) sentences and for all \(n\geq 2\) there is a \(\Sigma_n\) truth definition for \(\Sigma_n\) sentences. The last section presents a proof of an older, but previously unpublished result, that the assuption “Lessan’s bound for truth definitions is optimal” implies that \(\mathrm{I}\Delta_0+\lnot \mathrm{exp}+\lnot \mathrm{B}\Sigma_1\) is consistent. The paper concludes with some comments on why the problem of consistency of \(\mathrm{I}\Delta_0+\lnot \mathrm{exp}+\lnot \mathrm{B}\Sigma_1\) is so hard.


03C62 Models of arithmetic and set theory
03F30 First-order arithmetic and fragments
Full Text: DOI Euclid


[1] DOI: 10.1016/S0168-0072(97)00026-2 · Zbl 0891.03032
[2] Notes on polynomially bounded arithmetic 61 pp 942– (1996)
[3] Logic, methodology, and philosophy of science VIII (Moscow 1987) pp 143– (1989)
[4] DOI: 10.4064/fm180-2-2 · Zbl 1053.03032
[5] Metamathematics of first-order arithmetic (1993) · Zbl 0781.03047
[6] DOI: 10.1016/0168-0072(94)00057-A · Zbl 0829.03035
[7] DOI: 10.1016/S0049-237X(08)72003-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.