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