Count(ifq) does not imply Count

Annals of Pure and Applied Logic 90 (1-3):1-56 (1997)
  Copy   BIBTEX

Abstract

It is shown that the elementary principles Count and Count are logically independent in the system IΔ0 of Bounded Arithmetic. More specifically it is shown that Count implies Count exactly when each prime factor in p is a factor in q

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(97)00029-8

Other Versions

No versions found

Links

PhilArchive

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

Count(q) versus the pigeon-hole principle.Søren Riis - 1997 - Archive for Mathematical Logic 36 (3):157-188.
Variables, generality and existence.Henry Laycock - 2006 - In Paolo Valore, Topics on General and Formal Ontology. Polimetrica International Scientific Publisher. pp. 27.
Can Reasons be Self-Undermining?Rob Van Someren Greve - 2012 - Philosophia 40 (2):411-414.
Why the count de borda cannot beat the Marquis de condorcet.Mathias Risse - unknown
Reasons for Belief.Hannah Ginsborg - 2006 - Philosophy and Phenomenological Research 72 (2):286 - 318.
Research funding and authorship: does grant winning count towards authorship credit?Barton Moffatt - 2014 - Journal of Medical Ethics 40 (10):683-686.

Analytics

Added to PP
2014-01-16

Downloads
66 (#907,239)

6 months
9 (#1,208,822)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Photo of Søren Riis
Søren Riis
Roskilde University

Citations of this work

The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.

Add more citations

References found in this work

Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.

View all 8 references / Add more references