Questions: Well-Founded Relations and Transfinite Recursion

Question 1

Which of the following is NOT a well-founded relation?

• A. The 'divides' relation on positive integers (n divides m means n ≤ m)
• B. The 'proper subset' relation on finite sets
• C. The 'less than' relation on the integers ℤ
• D. The 'child of' relation on a finite family tree

Answer: (C)

The integers under < are not well-founded because there is an infinite descending chain: … < -3 < -2 < -1 < 0. Every non-empty subset of ℤ does not have a minimum element — the negative integers have no least element. By contrast, the positive integers under 'divides' are well-founded (every non-empty set of positive integers has a divisibility-minimal element), finite family trees under 'child of' bottom out at founders with no parents, and proper subsets of finite sets bottom out at the empty set.

Question 2

A function f is defined on binary trees by: f(leaf) = 1, and f(tree with subtrees L and R) = f(L) + f(R) + 1. This recursive definition is guaranteed to be well-defined because:

• A. Binary trees are finite, so the recursion will always terminate eventually
• B. The 'subtree of' relation on binary trees is well-founded — every tree bottoms out at leaves, which have no subtrees
• C. The function f is increasing, so it cannot cycle
• D. The definition specifies a unique value at every node independently

Answer: (B)

The key property is well-foundedness of the 'subtree of' relation: every non-empty collection of binary trees contains a tree with no further subtrees (a leaf). This means any 'look back at smaller elements' recursion always terminates — you eventually reach leaves, which are base cases with no further recursive calls. Well-foundedness guarantees unique definition, not just termination. Option A is close but misleading: the finiteness of individual trees matters, but the general principle that makes recursion work is the well-foundedness of the structural relation.

Question 3

The integers under the usual < relation are not well-founded.

• T. True
• F. False

Answer: True

A relation is well-founded if every non-empty subset has an R-minimal element — something smaller than everything else in that subset. The integers under < fail this: the set of all negative integers {…, -3, -2, -1} is non-empty but has no minimum. Equivalently, there are infinite descending chains: … < -2 < -1 < 0. This is exactly what fails for ℤ but holds for ℕ, making induction work on natural numbers but not integers.

Question 4

A well-founded relation is expected to have a single global minimum element — one element that is smaller than most others in the entire domain.

• T. True
• F. False

Answer: False

Well-foundedness requires that every *non-empty subset* has a minimal element, but those minimal elements may differ across subsets, and no single element need be globally minimal across the whole domain. For example, the 'proper subset' relation on sets of natural numbers is well-founded (every non-empty collection of sets has a set with no proper subset in the collection), but there is no single globally minimal element — the empty set ∅ is a minimal element under proper subset, but the condition is about each subset having *some* minimal element, not the same one globally.

Question 5

Explain why well-foundedness is the key property that allows recursive definitions to produce unique, well-defined functions.

Model answer: A recursive definition specifies f(x) in terms of f at R-smaller elements. For this to uniquely determine f everywhere, every such chain of lookbacks must eventually terminate at R-minimal elements (base cases) where f is directly specified. Well-foundedness guarantees exactly this: there are no infinite descending chains, so every computation sequence of 'what is f at something smaller?' eventually reaches a base case. Without well-foundedness, you could have an infinite regress with no base — the recursive specification would never bottom out, and the function might not be well-defined at all.

This is why induction and recursion are equivalent over well-founded relations: both require the 'no infinite descent' property to avoid circular or undefined reasoning. On structures without well-foundedness (like ℤ under <), you cannot define functions by 'look at smaller values' because there is always something smaller — the process never terminates. Well-foundedness converts the infinite 'look back' process into a finite one that reaches base cases.