The proof of the following theorem uses the axiom of choice. (Which begs the question: "is there a constructive proof?")
Theorem: A set X with an irreflexive relation < is trans-inductive (with respect to <) if and only if it is well-founded (i.e. every nonempty subset has a <-minimal element).
proof: If (X, <) is well-founded, then of course it is trans-inductive.
So suppose that (X, <) is trans-inductive. This means that every nonempty totally ordered subset (i.e. chain) of X has a minimum. We want to show that (X, <) is well-founded. For indirect proof, suppose that (X, <) is not well-founded. Then we have a nonempty subset S of X such that S has no <-minimal element. By recursion (and the axiom of *choice*) one can define a function f: N ---> S which produces an infinite descending chain f(0) > f(1) > f(2) > ... (and this contradicts the assumption that (X, <) is trans-inductive):
Fix any element in S and let this be f(0). Since S has no minimal element, there is an element in S which is smaller than f(0). *Choose* such an element and let this be f(1). We can define f(n + 1) to be some *chosen* element in S that is smaller than f(n).
So, by recursion, we have a function f: N ---> S and f(0) > f(1) > f(2) > ... is indeed an infinite descending chain (no mininum) since < is irreflexive. []
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)