Sh:634

• Shelah, S. (2000). Choiceless Polynomial Time Logic: Inability to express. In P. G. Clote & H. Schwichtenberg, eds., Computer Science Logic, 14th International Workshop, CSL 2000, Annual Conference of the EACSL, Fischbachau, Germany, August 21–26, 2000, Proceedings, Vol. 1862, Springer, pp. 72–125. arXiv: math/9807179
• Abstract:
We prove for the logic CPTime (the logic from the title) a sufficient condition for two models to be equivalent for any set of sentences which is “small” (certainly any finite set ), parallel to the Ehrenfeucht Fraïssé games. This enables us to show that sentences cannot express some properties in the logic CPTime and prove 0-1 laws for it.
• Version 2000-05-12_10 (54p)
Bib entry
@incollection{Sh:634,
author = {Shelah, Saharon},
title = {{Choiceless Polynomial Time Logic: Inability to express}},
booktitle = {{Computer Science Logic, 14th International Workshop, CSL 2000, Annual Conference of the EACSL, Fischbachau, Germany, August 21--26, 2000, Proceedings}},
series = {Lecture Notes in Computer Science},
volume = {1862},
year = {2000},
pages = {72--125},
publisher = {Springer},
editor = {Peter G. Clote and Helmut Schwichtenberg},
note = {\href{https://arxiv.org/abs/math/9807179}{arXiv: math/9807179}},
arxiv_number = {math/9807179}
}