A theory T has two models M and N such that M satisfies sentence σ but N satisfies ¬σ. What does this tell us about T?
AT is consistent, since both models exist without contradiction
BT is incomplete, because T decides neither σ nor ¬σ
CT is complete, because the sentence σ distinguishes the models
DT is inconsistent, because no theory can have models disagreeing on any sentence
For T to be complete, it must decide every sentence — that is, for every σ, either T ⊢ σ or T ⊢ ¬σ. If M ⊨ σ but N ⊨ ¬σ, then σ is not provable from T (or N would be a countermodel to provability) and ¬σ is not provable either (or M would be a countermodel). So T leaves σ undecided — T is incomplete. Option A confuses consistency (no contradiction) with completeness (every sentence decided). Option C misreads the situation: the fact that σ distinguishes the models is precisely what makes T incomplete.
Question 2 Multiple Choice
Why does a recursively enumerable complete theory have a decidable truth set — that is, why can you algorithmically determine whether any sentence is a theorem?
ABecause complete theories have finitely many sentences, making exhaustive search feasible
BBecause completeness guarantees that enumerating proofs will eventually find a proof of σ or ¬σ for any σ
CBecause complete theories have only one model, making truth evaluation straightforward
DBecause completeness implies the theory has no undecidable sentences by Gödel's theorem
Given a recursively enumerable complete theory T: to decide whether σ is a theorem, simultaneously enumerate all proofs from T. By completeness, either T ⊢ σ or T ⊢ ¬σ — one of these proofs must exist and will eventually be enumerated. The search always terminates. Without completeness, you might search forever and never know whether the absence of a proof means 'not provable' or 'just not found yet.' Option C is wrong: complete theories can have multiple non-isomorphic models (e.g., different infinite cardinalities).
Question 3 True / False
If a first-order theory is complete, then most of its models are isomorphic to each other.
TTrue
FFalse
Answer: False
Completeness guarantees only that all models are elementarily equivalent — they agree on the truth of every first-order sentence. But elementary equivalence does not imply isomorphism. For example, the theory of dense linear orders without endpoints (Th(ℚ, <)) is complete, but it has models of every infinite cardinality: ℚ, ℝ, and uncountable dense linear orders are all models, yet none are isomorphic to each other. A theory whose models are all isomorphic is called categorical (for a given cardinality), which is a stronger property than completeness.
Question 4 True / False
For any structure M, the set of all first-order sentences true in M — written Th(M) — is automatically a complete theory.
TTrue
FFalse
Answer: True
For any sentence σ, M either satisfies σ or it doesn't — there is no third option. Therefore either σ ∈ Th(M) or ¬σ ∈ Th(M), which means Th(M) decides every sentence. This is the semantic route to completeness: Th(M) picks a definite side on every question, and no consistent extension can add any new sentence without it already being in Th(M). Every complete theory arises in this way — as the theory of some structure (or equivalently, as the theory of an equivalence class of elementarily equivalent structures).
Question 5 Short Answer
What is the precise relationship between a theory being complete and all of its models being elementarily equivalent? Why do these two conditions coincide?
Think about your answer, then reveal below.
Model answer: The two conditions are equivalent. If T is complete, then for every sentence σ, all models agree on σ (because T proves one of σ or ¬σ, and all models satisfy T). Conversely, if all models of T are elementarily equivalent, then for every σ all models agree on its truth value, which means T cannot have models of both σ and ¬σ, so T must prove one of them — making T complete. The equivalence holds because both conditions say exactly the same thing: T leaves no first-order question open.
Understanding this equivalence is central to model theory: completeness (a syntactic/proof-theoretic condition) and all-models-elementarily-equivalent (a semantic condition) are two faces of the same restriction. This is why proving that all models of a theory are elementarily equivalent is a standard strategy for proving completeness, and it is the approach used in quantifier elimination arguments.