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