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

Other Versions

reprint Stolboushkin, Alexei; Niwinski, Damian (1997) "$Y = 2x$ vs. $y = 3x$". Journal of Symbolic Logic 62(2):661-672

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 99,362

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

On the complexity of the successivity relation in computable linear orderings.Rod Downey, Steffen Lempp & Guohua Wu - 2010 - Journal of Mathematical Logic 10 (1):83-99.
The finite model property for knotted extensions of propositional linear logic.C. J. van Alten - 2005 - Journal of Symbolic Logic 70 (1):84-98.
The finite model property for various fragments of intuitionistic linear logic.Mitsuhiro Okada & Kazushige Terui - 1999 - Journal of Symbolic Logic 64 (2):790-802.
The complexity of definability by open first-order formulas.Carlos Areces, Miguel Campercholi, Daniel Penazzi & Pablo Ventura - 2020 - Logic Journal of the IGPL 28 (6):1093-1105.
Partial-order Boolean games: informational independence in a logic-based model of strategic interaction.Julian Bradfield, Julian Gutierrez & Michael Wooldridge - 2016 - Synthese 193 (3):781-811.
Inferring a linear ordering over a power set.Ran Spiegler - 2001 - Theory and Decision 51 (1):31-49.
On the Decision Problem for Two-Variable First-Order Logic.Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
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.
Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.

Analytics

Added to PP
2009-01-28

Downloads
32 (#581,724)

6 months
13 (#197,981)

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