[FOM] Extension of well-founded relation well-ordering

[Alberto Marcone]

Il 10/02/2015 07:56, Gert Smolka ha scritto:
> Consider the following statement:
>
> Let X be a set with a choice function. Then every well-founded relationon X can be extended to a well-ordering of X.
>
> Is there a proof of the statement in the literature?
>
> I would expect that a proof of Zermelo's theorem can be extended to a proof of the statement.
>
> Gert Smolka
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
> .
>

This statement is just saying that omega^* is extendible (also 
enforceable). In general say that a linear order type tau is extendible 
if a poset containing no copy of tau always has a linear extension 
containing no copy of tau. this kind of statements have been stated from 
the viewpoint of reverse mathematics.

I quote a bit of history from the introduction to 
"Computability-theoretic and proof-theoretic aspects of partial and 
linear orderings" by Downey, Hirschfeldt, Lempp, and Solomon (Israel J. 
Math. 138 (2003), 271-289):

"The extendibility of various linear order types was studied extensively 
by Bonnet, Corominas, Fraissé, Jullien, and Pouzet in France, as well as 
independently by Galvin, Kostinsky, and McKenzie in the United States. A 
complete characterization of the countable extendible linear order types 
was obtained by Bonnet [Bo69]."

The final reference is to R. Bonnet, Stratifications et extension des 
genres de chaînes dénombrables, C. R. Acad. Sci. Paris Sér. A-B 269 
1969, A880–A882.

Best wishes,
Alberto
-- 
Alberto Marcone                                 alberto.marcone at uniud.it
Dip. di Matematica e Informatica
Universita' di Udine                                tel: +39-0432-558482
via delle Scienze 206                               fax: +39-0432-558499
33100 Udine
Italy                       http://users.dimi.uniud.it/~alberto.marcone/