# Was there any need or utility or aim, for Cantor's theory?

• I
Yes, basically I think if we define a predicate WO(x) (where x∈ℕ), which should describe whether the program corresponding to index x(computing a function ℕ2 to {0,1}), describes a well-order (of ℕ with any order-type) or not . Then we can define the smallest ordinal α such that: "theory T can't prove any computable well-order relation with order-type α as a well-order."
Though I am not fully sure whether this is the standard definition, if there is one (or whether there are multiple definitions?).
Although the discussion has run its course, there is a small point that should be pointed out. If we look at the wiki definition:
"a well-order on a set S is a total order on S with the property that every non-empty of S has a least element in this ordering."

So, while the above definition would fit perfectly well when T can talk about "every non-empty subset of", it seems that it isn't straight-forward when that is not the case.

For example, quantification over ℕ (like in PA) really has to be insufficient to describe the property "WO(x)" that was described in the quote above. If that was true, then the set containing the elements for which WO(x) is true would be an arithmetic set (which is known to be false).

So, if there is no explicit way to describe the property WO(x) for some T, then it seems the definition would definitely have to be different in that case (in one way or another).

Cantor080
stevendaryl
Staff Emeritus
Although the discussion has run its course, there is a small point that should be pointed out. If we look at the wiki definition:
"a well-order on a set S is a total order on S with the property that every non-empty of S has a least element in this ordering."

So, while the above definition would fit perfectly well when T can talk about "every non-empty subset of", it seems that it isn't straight-forward when that is not the case.

For example, quantification over ℕ (like in PA) really has to be insufficient to describe the property "WO(x)" that was described in the quote above. If that was true, then the set containing the elements for which WO(x) is true would be an arithmetic set (which is known to be false).

So, if there is no explicit way to describe the property WO(x) for some T, then it seems the definition would definitely have to be different in that case (in one way or another).
Right. Arithmetic cannot define whether a relation is well-ordered, or not. However, you can switch it around to the question of induction.

If ##R(x,y)## is a well-founded relation, then the following "induction schema" is true, for any formula ##\phi(x)##:

##(\forall y: (\forall x: R(x,y) \rightarrow \phi(x)) \rightarrow \phi(y)) \rightarrow \forall y: \phi(y)##

To see that this is valid:
1. Assume that ##\forall y: (\forall x: R(x,y) \rightarrow \phi(x)) \rightarrow \phi(y)##.
2. Let ##S## be the set of all ##y## such that ##\neg \phi(y)##
3. Since ##R## is well-founded, then there must be a "smallest" element of ##S##, ##y_0##. Smallest means that there is no ##y## in ##S## such that ##R(y,y_0)##
4. So that means that if ##R(y,y_0)## holds, then ##y## is not in ##S##, which means that ##\phi(y)## holds (since ##S## is defined as those ys that don't satisfy ##\phi(y)##)
5. So we conclude: ##\forall y: R(y,y_0) \rightarrow \phi(y)##
6. But by axiom 1, this implies ##\phi(y_0)##. Contradiction. So the assumption that ##S## was non-empty led to a contradiction, so ##S## is empty. So that means ##\forall y: \phi(y)##
So rather than talking about arithmetic proving that a relation ##R## is well-founded (it can't even state that), you can ask whether the ##R## induction schema is provable for every formula ##\phi(y)##

SSequence
##(\forall y: (\forall x: R(x,y) \rightarrow \phi(x)) \rightarrow \phi(y)) \rightarrow \forall y: \phi(y)##

Well my intuition with orderings (except well-orders), well-founded relations etc. is very limited ...... but I think I understand the gist of it.

So if we take ##R## to be a well-order relation (on ℕ), then this schema can really be thought of as a form of transfinite induction? So, for example suppose we have some computable ##R##. So there should always exist at least some ##R## so that if ##R## represented an order-type <ε0, then PA would conclude ##\forall y: \phi(y)## (assuming the hypothesis to be true)? But if ##R## represented an order-type ≥ε0, then PA would never be able to conclude ##\forall y: \phi(y)## (once again, assuming the hypothesis to be true)?

(and similarly for other weaker theories perhaps)

stevendaryl
Staff Emeritus
##(\forall y: (\forall x: R(x,y) \rightarrow \phi(x)) \rightarrow \phi(y)) \rightarrow \forall y: \phi(y)##

Well my intuition with orderings (except well-orders), well-founded relations etc. is very limited ...... but I think I understand the gist of it.

So if we take ##R## to be a well-order relation (on ℕ), then this schema can really be thought of as a form of transfinite induction?
It is transfinite induction.

So, for example suppose we have some computable ##R##. So there should always exist at least some ##R## so that if ##R## represented an order-type <ε0, then PA would conclude ##\forall y: \phi(y)## (assuming the hypothesis to be true)? But if ##R## represented an order-type ≥ε0, then PA would never be able to conclude ##\forall y: \phi(y)## (once again, assuming the hypothesis to be true)?

(and similarly for other weaker theories perhaps)
I would put it this way: For every order type less than ##\epsilon_0##, there is a computable ##R## defining a well-founded relation of this order type such that PA proves every instance of R-induction. For any order type greater than or equal to ##\epsilon_0##, there is no such ##R## (there is a computable ##R## of that order type, but PA doesn't prove the induction schema---meaning that it doesn't prove every instance; there is some ##\phi## that it fails to prove)

SSequence
mathwonk