Discussion
Consider the first-order logic sentence
\[ \begin{aligned} \varphi \equiv\ & \exists s \exists t \exists u \forall v \forall w \forall x \forall y \\ & \psi(s,t,u,v,w,x,y) \end{aligned} \]
where \(\psi(s,t,u,v,w,x,y)\) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose \(\varphi\) has a model with a universe containing 7 elements.
Which one of the following statements is necessarily true?
Answer: A
The statement that is necessarily true is that there exists at least one model of \(\varphi\) with universe of size at most 3.
Take the model with 7 elements and choose witnesses \(s, t, u\) for the three existential quantifiers. Restrict the model to the set {s, t, u}, which has at most 3 elements. Because there are no function symbols, this set is closed and gives a substructure, and the quantifier-free formula \(\psi\) has the same truth value on its elements as in the big model.
The universal part says \(\psi(s,t,u,v,w,x,y)\) holds for every choice of \(v, w, x, y\) in the big model, so in particular for every choice from {s, t, u}. Hence the small structure is also a model of \(\varphi\).
That makes 'no model of size at most 3' false. The other two fail too: if \(\psi\) is always true, \(\varphi\) has models of every size, including sizes above 7, so the universe need not be exactly 7.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development