Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

The neat embedding problem and the number of variables required in proofs


Author: Roger D. Maddux
Journal: Proc. Amer. Math. Soc. 112 (1991), 195-202
MSC: Primary 03G15; Secondary 03B10, 03F07
DOI: https://doi.org/10.1090/S0002-9939-1991-1033959-7
MathSciNet review: 1033959
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: By constructing special relation algebras we show that if $ 3 < \alpha < \omega $, then

$\displaystyle {\mathbf{S}}N{{\text{r}}_3}C{A_\alpha } \ne {\mathbf{S}}N{{\text{r}}_3}C{A_{3\alpha - 7}}$

and there is a logically valid first-order sentence containing at most three variables with a proof in which every sentence has at most $ 3\alpha - 7$ variables, but no proof in which every sentence has at most a variables.

References [Enhancements On Off] (What's this?)

  • [HMT71] Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras, Part I, North-Holland, Amsterdam, 1971. MR 781929 (86m:03095a)
  • [HMT85] -, Cylindric algebras, part II, North-Holland, Amsterdam, 1985. MR 781930 (86m:03095b)
  • [J69] J. Johnson, Nonfinitizability of classes of representable polyadic algebras, J. Symbolic Logic 34 (1969), 344-352. MR 0256862 (41:1518)
  • [Ma78] Roger D. Maddux, Topics in relation algebras, Doctoral dissertation, University of California, Berkeley, 1978, pp. iii+241.
  • [Ma82] -, Some varieties containing relation algebras, Trans. Amer. Math. Soc. 272 (1982), 501-526. MR 662049 (84a:03079)
  • [Ma85] -, Finite integral relation algebras, Universal Algebra and Lattice Theory (Proc. Southeastern Conf. in Universal Algebra and Lattice Theory, July 11-14, 1984), Lecture Notes in Math., vol. 1149, Springer-Verlag, Berlin, 1985, pp. 175-197. MR 823016 (87d:03180)
  • [Ma89] -, Nonfinite axiomatizability results for cylindric and relation algebras, J. Symbolic Logic (3) 54 (September 1989), 951-974. MR 1011183 (90f:03099)
  • [Mo69] J. Donald Monk, Nonfinitizability of classes of representable cylindric algebras, J. Symbolic Logic 34 (1969), 331-343. MR 0256861 (41:1517)
  • [Mo71] -, Provability with finitely many variables, Proc. Amer. Math. Soc. 27 (1971), 353-358. MR 0276063 (43:1811)
  • [TG87] Alfred Tarski and Steven Givant, A formalization of set theory without variables, Amer. Math. Soc. Colloq. Publ. vol. 41, 1987. MR 920815 (89g:03012)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03G15, 03B10, 03F07

Retrieve articles in all journals with MSC: 03G15, 03B10, 03F07


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1991-1033959-7
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society