Questions: Complete Theory and Consequence Relations

Question 1

Structures M and N satisfy exactly the same first-order sentences. Which of the following must be true?

• A. M and N are isomorphic, since identical first-order behavior implies identical structure
• B. M and N are elementarily equivalent, but need not be isomorphic
• C. Th(M) and Th(N) are different, since distinct structures have distinct theories
• D. M and N share some but not all first-order sentences, since complete theories can overlap

Answer: (B)

Two structures satisfying the same first-order sentences are elementarily equivalent by definition (Th(M) = Th(N)). But elementary equivalence does not imply isomorphism — ℚ and any non-standard dense linear order without endpoints are elementarily equivalent but not isomorphic. The key point is that first-order logic cannot always distinguish non-isomorphic structures; elementary equivalence is a strictly coarser relation.

Question 2

The Euclidean algorithm shows that ℤ and ℚ, both ordered under <, have properties in common. A student claims Th(ℤ, <) = Th(ℚ, <) since both are linear orders without greatest element. What is wrong?

• A. The claim is correct — both structures have the same complete theory
• B. The claim is wrong because ℤ lacks an ordering relation
• C. The claim is wrong because ℚ satisfies 'between any two elements there is another,' which ℤ does not — so their complete theories differ
• D. The claim is wrong because Th(M) can only be defined for finite structures

Answer: (C)

ℚ is a dense linear order: between any two rationals there is another. ℤ does not have this property — there is nothing between 1 and 2. This is a first-order sentence that is true in ℚ but false in ℤ, so it belongs to Th(ℚ, <) but not Th(ℤ, <). Finding a single sentence with different truth values in two structures is all it takes to prove their complete theories differ.

Question 3

The complete theory Th(M) of any structure M is a complete theory, meaning for every sentence φ, either φ ∈ Th(M) or ¬φ ∈ Th(M).

• T. True
• F. False

Answer: True

Every first-order sentence is either true or false in M — there is no third option. If φ is true in M, then φ ∈ Th(M). If φ is false in M, then ¬φ is true in M, so ¬φ ∈ Th(M). This totality is exactly what makes Th(M) complete: no sentence is left undecided.

Question 4

If two structures are isomorphic, they may have different complete theories depending on how the isomorphism is defined.

• T. True
• F. False

Answer: False

Isomorphic structures always have the same complete theory. An isomorphism is a bijection that preserves all the structure (relations, functions, constants), so any sentence true in one structure is true in the other. Th(M) = Th(N) is a consequence of isomorphism. The reverse does not hold — Th(M) = Th(N) does not imply isomorphism — but the forward direction is a basic theorem.

Question 5

Why is elementary equivalence a strictly coarser relation than isomorphism, and what does this tell us about the expressive power of first-order logic?

Model answer: Elementary equivalence (same complete theory) is coarser because non-isomorphic structures can satisfy exactly the same first-order sentences. Isomorphism implies elementary equivalence, but not vice versa. This shows that first-order logic is expressively limited: it cannot always distinguish structures that differ in ways first-order sentences cannot capture, such as cardinality differences between countable dense linear orders.

The classic example is Cantor's theorem that all countable dense linear orders without endpoints are isomorphic — so ℚ and the set of irrationals as ordered sets have the same complete theory even though they are structurally different as sets. First-order logic cannot say 'there are uncountably many elements' in a single sentence, so it cannot distinguish structures that differ only in cardinality beyond what can be captured finitely.