Consider the first-order logic sentence πœ‘ ≑ βˆƒπ‘ βˆƒπ‘‘βˆƒπ‘’βˆ€π‘£βˆ€π‘€βˆ€π‘₯βˆ€π‘¦ πœ“(𝑠,𝑑,…

PYQ GATE 2018

Consider the first-order logic sentence

πœ‘ ≑ βˆƒπ‘ βˆƒπ‘‘βˆƒπ‘’βˆ€π‘£βˆ€π‘€βˆ€π‘₯βˆ€π‘¦ πœ“(𝑠,𝑑, 𝑒, 𝑣, 𝑀, π‘₯, 𝑦)

where πœ“(𝑠,𝑑, 𝑒, 𝑣, 𝑀, π‘₯, 𝑦) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose πœ‘ has a model with a universe containing 7 elements.

Which one of the following statements is necessarily true?

  1. A.

    There exists at least one model of πœ‘ with universe of size less than or equal to 3.

  2. B.

    There exists no model of πœ‘ with universe of size less than or equal to 3.

  3. C.

    There exists no model of πœ‘ with universe of size greater than 7.

  4. D.

    Every model of πœ‘ has a universe of size equal to 7.

Attempted by 70 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…