سوال ۹۳ کنکور ارشد علوم کامپیوتر ۱۴۰۳

Here $\Sigma_{DLO}$ axiomatizes a dense linear order without endpoints: $\le$ is a total order that is dense ($\forall x\,\forall y\,(x<y \to \exists z\,(x<z<y))$) and has no least or greatest element. The canonical model is $(\mathbb{Q}, \le)$.

Statement I — countable models are isomorphic

This is Cantor's theorem: any two countable dense linear orders without endpoints are isomorphic. The proof is the back-and-forth method — enumerate the two countable domains and build a partial order-isomorphism finite step by step, at each stage extending it to include the next element of one side (using density to find a matching element on the other side, and no-endpoints to handle extremes). The union is a bijection preserving order.

Equivalently, $\Sigma_{DLO}$ is $\aleph_0$-categorical (countably categorical): up to isomorphism it has exactly one countable model, namely $(\mathbb{Q}, \le)$. So statement I is TRUE.

Statement II — the theory is complete

Apply the Łoś–Vaught test: if a theory $T$

• is consistent,
• has no finite models, and
• is $\kappa$-categorical for some infinite cardinal $\kappa \ge |L|$,

then $T$ is complete.

$\Sigma_{DLO}$ satisfies all three: it is consistent ($\mathbb{Q}$ is a model); density forces every model to be infinite, so there are no finite models; and by Part I it is $\aleph_0$-categorical. Therefore $\Sigma_{DLO}$ is complete — for every sentence $\sigma$ exactly one of $\Sigma_{DLO} \vdash \sigma$ or $\Sigma_{DLO} \vdash \neg\sigma$ holds. So statement II is TRUE.

(Completeness also follows because all models of a complete-via-categoricity theory are elementarily equivalent: a sentence true in $\mathbb{Q}$ is provable, one false in $\mathbb{Q}$ has its negation provable.)

Conclusion

Both I and II hold, so the answer is Both — option (3).

Exam trick: $\aleph_0$-categorical + no finite models + consistent $\Rightarrow$ complete (Łoś–Vaught). DLO is the textbook poster child: Cantor's back-and-forth gives categoricity, and categoricity hands you completeness for free.