Y = 2x vs. Y = 3x

&
Journal of Symbolic Logic 62 (2):661-672 (1997)
  Copy   BIBTEX

Abstract

We show that no formula of first order logic using linear ordering and the logical relation y = 2x can define the property that the size of a finite model is divisible by 3. This answers a long-standing question which may be of relevance to certain open problems in circuit complexity

Categories

Keywords

Reprint years

DOI

10.2307/2275554

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,846

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Relativized logspace and generalized quantifiers over finite ordered structures.Georg Gottlob - 1997 - Journal of Symbolic Logic 62 (2):545-574.
The finite model property for various fragments of intuitionistic linear logic.Mitsuhiro Okada & Kazushige Terui - 1999 - Journal of Symbolic Logic 64 (2):790-802.
On the decision problem for two-variable first-order logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
Complexity and nicety of fluted logic.William C. Purdy - 2002 - Studia Logica 71 (2):177 - 198.
Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Finite conformal hypergraph covers and Gaifman cliques in finite structures.Ian Hodkinson & Martin Otto - 2003 - Bulletin of Symbolic Logic 9 (3):387-405.
Loosely guarded fragment of first-order logic has the finite model property.Ian Hodkinson - 2002 - Studia Logica 70 (2):205 - 240.

Analytics

Added to PP
2009-01-28

Downloads
19 (#798,463)

6 months
4 (#787,709)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1-6):66-92.
¹1-formulae on finite structures.M. Ajtai - 1983 - Annals of Pure and Applied Logic 24 (1):1.

Add more references