Questions: Order Property and Independence Property: Marks of Instability

Question 1

The theory of dense linear orders (DLO) has a formula x < y that satisfies the order property. What follows about the classification of DLO?

• A. DLO is stable, since linear orders have well-understood and tractable model theory
• B. DLO is unstable and, because OP implies IP, DLO must also have the independence property
• C. DLO is unstable but may still be NIP — having OP does not force a theory to have IP
• D. DLO cannot be classified without checking whether every formula has OP, not just x < y

Answer: (C)

OP and IP are not the same. Having the order property makes DLO unstable, but OP does not imply IP. The independence property requires that a formula can encode *all* 2ⁿ subsets of any n-element set — a far stronger condition than merely encoding a linear order. DLO is in fact the canonical example of a NIP (no independence property) theory: it has OP (and is thus unstable) but its formula x < y cannot define arbitrary subsets, only the order relation. Option B reverses the implication: it is IP that implies OP, not the other way around.

Question 2

The theory of the random graph (Rado graph) has the independence property. Which of the following conclusions is correct?

• A. The Rado graph theory is stable — having IP is compatible with stability if OP does not hold independently
• B. The Rado graph theory has IP but not OP, since the two properties are logically independent
• C. The Rado graph theory has both IP and OP, since IP implies OP
• D. The Rado graph theory is NIP by definition, since its edge relation has a regular combinatorial structure

Answer: (C)

IP implies OP: any formula that can encode all 2ⁿ subsets of an n-element set can in particular encode a linear ordering (a specific subset pattern), so IP is strictly stronger than OP. A theory with IP therefore has OP as well, and is unstable. The Rado graph's edge relation can define arbitrary binary relations on any finite set of vertices — the hallmark of IP — so it has IP, which entails OP, which entails instability. Option B is the key misconception: OP and IP are *not* logically independent. They are nested — IP ⊂ OP in terms of what theories possess them.

Question 3

Any theory with the independence property also has the order property.

• T. True
• F. False

Answer: True

IP implies OP. If a formula φ(x, y) can encode all 2ⁿ subsets of any n-element set, it can in particular encode the linear order relation i < j (which is just one specific subset for each n). So the existence of IP guarantees the existence of a formula exhibiting OP as well. The implication runs one way: IP → OP → instability. The converse fails — a theory can have OP without IP, as DLO demonstrates.

Question 4

A theory with the order property is expected to also have the independence property.

• T. True
• F. False

Answer: False

OP does not imply IP. The order property only requires a formula that defines a linear ordering over index sets. The independence property requires a formula that can define *arbitrary* set membership patterns — all 2ⁿ subsets of any n-element set. These are different combinatorial capacities, and OP is the weaker one. DLO is the standard counterexample: it has OP (the formula x < y defines a linear order) but is NIP — it lacks the independence property entirely.

Question 5

Why is the independence property considered 'strictly stronger' than the order property? Describe the structural difference between what OP and IP each require of a formula.

Model answer: OP requires a formula that can distinguish all finite linear orderings — φ(aᵢ, bⱼ) holds iff i < j. IP requires a formula that can distinguish all finite *subsets* — for any n elements bᵢ and any subset S, there exists an a such that φ(a, bᵢ) holds iff i ∈ S. IP encodes exponentially more patterns (2ⁿ subsets vs. n! orderings for fixed n), making it a far more powerful coding device. Since a linear order is just one particular subset pattern, IP implies OP. But OP gives you only one pattern type; IP gives you all of them. Hence IP is strictly stronger: theories with IP have OP, but OP-theories can be NIP.

The key is combinatorial richness. OP measures whether a formula can encode a single ordered relation. IP measures whether a formula can encode *all* binary relations on arbitrary finite sets. A formula with IP can simulate any finite combinatorial structure, which is why IP-theories resist Shelah's classification machinery. OP-but-NIP theories like DLO and valued fields are 'tame' enough to admit their own structure theory (dp-rank, generically stable types), even though they are unstable.