A) Fagin's theorem, 1974 B) Shapiro's theorem, 2000 C) Büchi-Elgot-Trakhtenbrot theorem, 1960 D) Henkin's theorem, 1950
A) NP B) PH C) PSPACE D) co-NP
A) PSPACE B) co-NP C) NP D) EXPTIME
A) PH B) REG C) EXPTIME D) NP
A) PSPACE B) EXPTIME C) NP D) PH
A) co-NP B) PSPACE C) NP D) EXPTIME
A) Adding a least fixed point operator would not make it more expressive B) It would make second-order logic less expressive C) Adding a transitive closure operator would not make it more expressive D) It would make second-order logic equivalent to first-order logic
A) Shapiro, S. (2000) B) Quine, W. V. (1970) C) Väänänen, J. (2001) D) Hinman, P. (2005)
A) Quine, W. V. B) Henkin, L. C) Shapiro, S. D) Väänänen, J.
A) Hinman, P. (2005) B) Shapiro, S. (2000) C) Väänänen, J. (2001) D) Quine, W. V. (1970)
A) Henkin, L. (1950) B) Fagin's theorem, 1974 C) Büchi-Elgot-Trakhtenbrot theorem, 1960 D) Shapiro's theorem, 2000
A) Henkin's theorem B) Fagin's theorem C) Büchi-Elgot-Trakhtenbrot theorem D) Shapiro's theorem
A) Cayley tables B) Computational complexity classes C) Finite structures D) Regular languages
A) PH is always more expressive than PSPACE B) PSPACE is always more expressive than PH C) If PH = PSPACE, adding a least fixed point operator does not increase expressiveness D) If PH = PSPACE, adding a transitive closure operator does not increase expressiveness
A) A Cayley table of a finite structure B) A finite string w = w1···wn in a finite alphabet A C) An EXPTIME language D) A regular language
A) Shapiro, S. (2000) B) Quine, W. V. (1970) C) Henkin, L. (1950) D) Hinman, P. (2005)
A) They define regular languages B) They characterize NP C) They can be encoded by a finite string D) They are equivalent to second-order logic
A) Only functions with finite domains B) All sets or functions of the appropriate sort C) Only finite sets D) Only subsets of the domain
A) A proper subset of all sets or functions of that sort B) Only finite sets C) The full powerset of the model's first-order part D) Only the empty set
A) The completeness of second-order logic B) The uniqueness of the standard interpretation C) The existence of non-standard interpretations of higher-order domains D) The compactness of second-order logic
A) Its reliance on first-order logic B) Its ability to quantify over sets C) Its use of finite domains D) Its ability to quantify over individual elements only
A) Every set is countable B) Every bounded, nonempty set has a supremum C) Every set has a maximum element D) Every set is finite
A) The existence of infinite sets B) The existence of real numbers C) Uncountability of the domain D) Finiteness and countability of the domain
A) First-order logic with Henkin quantifiers B) First-order logic with Gödel's incompleteness theorem C) Existential second-order logic (ESO) D) Full second-order logic
A) ∃ B) ↔ C) ∀ D) →
A) 'P(0)' B) 'P(n+1)' C) 'P(n-1)' D) 'P(n)'
A) Yes B) It is undecidable C) No D) Only under certain conditions
A) Decidable under certain conditions B) Undecidable C) Only decidable for finite sets D) Decidable
A) Logical hierarchy B) Analytical hierarchy C) Arithmetical hierarchy D) Computational hierarchy
A) An infinite number of models. B) Many models, including countable ones. C) No models. D) Only one model.
A) Gödel's incompleteness theorem. B) The Löwenheim–Skolem theorem. C) Cantor's theorem. D) There is only one Archimedean complete ordered field.
A) A theory that defines the real numbers without any reference to cardinality. B) A theory that assumes the continuum hypothesis is false. C) A theory characterizing the real numbers as a complete Archimedean ordered field plus an axiom about the domain's cardinality. D) A theory that only includes first-order logic axioms.
A) C. S. Peirce B) Gottlob Frege C) Skolem D) Gödel
A) Russell's paradox B) Löwenheim-Skolem theorem C) Skolem's paradox D) Gödel's incompleteness
A) W. V. Quine B) C. S. Peirce C) George Boolos D) Gottlob Frege |