$y = 2x$ vs. $y = 3x$

Stolboushkin, Alexei; Niwinski, Damian

J. Symbolic Logic, Tome 62 (1997) no. 1, p. 661-672 / Harvested from Project Euclid

Résumé

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.

Publié le : 1997-06-14
Classification:

@article{1183745250,
     author = {Stolboushkin, Alexei and Niwinski, Damian},
     title = {$y = 2x$ vs. $y = 3x$},
     journal = {J. Symbolic Logic},
     volume = {62},
     number = {1},
     year = {1997},
     pages = { 661-672},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745250}
}

Stolboushkin, Alexei; Niwinski, Damian. $y = 2x$ vs. $y = 3x$. J. Symbolic Logic, Tome 62 (1997) no. 1, pp.  661-672. http://gdmltest.u-ga.fr/item/1183745250/