Choiceless Polynomial Time Logic: Inability to Express
Saharon Shelah6, 7
| (6) |
Institute of Mathematics, The Hebrew University, Jerusalem, Israel |
| (7) |
Mathematics Department, Rutgers University, New Brunswick, NJ, USA |
Abstract
We prove for the logic
(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
and prove 0-1 laws for it.
Key words and phrases Finite model theory - Computer Science - Polynomial time logic - choiceless - games
Dedicated to my friend Yuri Gurevich
Partially supported by the United States-Israel Binational Science Foundation. Publication 634.
I would like to thank Alice Leonhardt for the beautiful typing.
References secured to subscribers.