Questions: Well-Founded Relations

Question 1

Which of the following relations is NOT well-founded?

• A. The 'less than' relation on the natural numbers ℕ
• B. The membership relation ∈ on the universe of sets (assuming regularity)
• C. The 'greater than' relation on the integers ℤ
• D. The 'proper subset' relation on the powerset of {1, 2, 3}

Answer: (C)

The 'greater than' relation on ℤ is not well-founded because there are infinite descending chains: ... > -1 > -2 > -3 > ... . By contrast, < on ℕ is well-founded (no natural number has an infinite descending chain of smaller naturals), ∈ on sets is well-founded by the axiom of regularity, and ⊂ on the powerset of a finite set is well-founded because chain length is bounded by the size of the set.

Question 2

A textbook claims: 'The membership relation ∈ is well-ordered on the universe of sets, since the axiom of regularity ensures every nonempty set has a minimal element.' What is wrong with this statement?

• A. Nothing — well-foundedness and well-ordering are the same property for the membership relation
• B. The axiom of regularity only applies to finite sets, not the full universe
• C. Well-ordering requires totality (any two elements are comparable), but ∈ is not a total order — most pairs of sets are incomparable
• D. The axiom of regularity ensures the relation is reflexive, not well-founded

Answer: (C)

A well-ordering requires both well-foundedness (no infinite descending chains, equivalently every nonempty subset has a minimal element) AND totality (any two elements are related in one direction). The membership relation ∈ is well-founded but emphatically not a total order — for most pairs of sets x, y, neither x ∈ y nor y ∈ x holds. Well-foundedness is the strictly weaker and more general property; it does not require the relation to be transitive, antisymmetric, or total.

Question 3

Well-foundedness of a relation is the structural property that licenses induction and recursion along that relation.

• T. True
• F. False

Answer: True

This is the central theorem about well-founded relations: given any well-founded relation R on A, to prove property P holds for all a ∈ A, it suffices to prove P(a) holds whenever P(b) holds for all b R a (the inductive step). If R were not well-founded, an infinite descending chain would provide a sequence where the inductive step applies at each step but the property never has a base case to anchor on. Well-foundedness is exactly the property that guarantees every descending chain terminates, making the induction valid.

Question 4

A well-founded relation must be irreflexive — no element can be related to itself.

• T. True
• F. False

Answer: True

If a R a held for some element a, then a, a, a, ... would be an infinite descending R-chain (with a related to itself at every step), violating well-foundedness. So well-foundedness does imply irreflexivity. This is consistent with the axiom of regularity ruling out x ∈ x: if ∈ were reflexive, it would create an infinite ∈-chain and fail to be well-founded. Note that this is one of the few structural consequences of well-foundedness that is not about ordering or totality.

Question 5

Explain why ε-induction (∈-induction) is valid, and what would go wrong if the axiom of regularity were dropped.

Model answer: ε-induction is valid because ∈ is well-founded on the set universe — a consequence of the axiom of regularity. To prove P(x) for all sets x, show that P(x) holds whenever P(y) holds for all y ∈ x. If P failed for some set x, then since P holds for all members of x, x must have a member y₁ where P fails. Then y₁ must have a member y₂ where P fails, and so on — producing an infinite ∈-descending chain x ∋ y₁ ∋ y₂ ∋ ..., which regularity forbids. Without regularity, sets like x = {x} (where x ∈ x) could exist, creating ∈-cycles that make the induction circular and break the rank function.

The rank function is also at stake: rank(x) = the least α such that x ∈ V_{α+1} is defined recursively — it requires that members of x have strictly smaller ranks. Without regularity, a set like x = {x} would need rank(x) > rank(x), a contradiction. Regularity is precisely what prevents these pathological cases and makes the cumulative hierarchy V₀ ⊂ V₁ ⊂ ... a coherent stratification of the entire set universe.