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