Talk:Well-order

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, High-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
High Importance
 Field: Foundations, logic, and set theory
This article has comments.

Example needed[edit]

I think this would be clearer with an example. Does a well-order require the definitions of mathematical sets? - anon

I added an example of how to well order the integers (all the integers), but my reference book is at home, I didn't write it well and it needs a proof it well orders the integers. Somebody please improve it. (marked for cleanup) RJFJR 21:46, Feb 7, 2005 (UTC)

definition?[edit]

The definition of a well ordered set says that every subset of a set has a least element. However, since the relational operator must be anti-symmetric, I'm having a hard time imagining a totally ordered set which itself has a least element but has a subset without a least element.

Can anyone give an example of why this definition is necessary? It might be something nice to include on the page. 129.110.240.1 05:18, 25 Mar 2005 (UTC)

Easy. The set of real numbers [0,1]. It has a least number, 0. What is the least element of the subset consisting of the interval (0,1] ? It is the smallest number greater than zero. But what is the smallest real number greater than zero? [Actually, if the Axiom of Choice is true then there is a way to well order the reals, but the proof, in addition to requiring AC, is non constructive so no one knows how to well order the reals. Unlike well ordering integers where there is a way to well order the negative numbers). RJFJR 15:22, Mar 25, 2005 (UTC)

Clean?[edit]

I removed the cleanup template from here since it has been cleanedup. RJFJR 13:46, Jun 24, 2005 (UTC)

New version[edit]

The new version looks great! RJFJR 13:43, Jun 24, 2005 (UTC)

Strict or nonstrict?[edit]

The article is not very specific about whether it's discussing strict or nonstrict partial orders. The link to total order uses the nonstrict notion, but the examples given seem to be strict. Among adepts this is one of those things you don't worry too much about because it's usually clear from context, but in an article like this maybe we should be a little more careful. --Trovatore 8 July 2005 00:04 (UTC)

intro para[edit]

The intro para was stated in such a way that the linearity of the ordering was a consequence of the proposed definition (a partial order in which every subset has a least element). The alternative way of defining a well ordering is as a linear order which is well founded in the sense that every nonempty subset has a minimal element. The third possibility, namely a poset in which every nonempty subset has a minimal element, is not the same. To prevent confusion between least and minimal, I think it is better to be explicit that a well ordering is defined to be a well founded linear order. CMummert 13:10, 1 July 2006 (UTC)

unhyphenated spelling[edit]

I have removed the {{fact}} tag from the spelling note; of course this is not the sort of thing for which citations are likely to be available. It's the kind of thing you'd find in a dictionary, but no one writes dictionaries of contemporary set-theoretic usage. If you want a citation in which the spelling is used, I can find that for you once I get home (I'd put it on the talk page, not in the article). --Trovatore 23:22, 30 April 2007 (UTC)

OK, here we go.

  • Moschovakis, Yiannis N. (1980). Descriptive Set Theory. North Holland. pp. p. 104. ISBN 0-444-70199-0. 

The relevant quote is

There are various names attached to relations that satisfy some of these conditions and we put them down here for the record.
[...]
(2) \preceq is a wellordering if it is a wellfounded ordering.

Hope this helps, --Trovatore 05:17, 1 May 2007 (UTC)

well-ordering of reals under ZF[edit]

Is it known whether {\mathbb R} can be proven to have a well-ordering using only the ZF axioms (without AC)? I guess that means using some conventional construction of R, with Dedekind cuts or whatever. Thanks. 75.62.4.229 (talk) 11:32, 13 December 2007 (UTC)

ZF does not prove that R can be wellordered. In fact the usual proof (or at least the first proof that I learned) that ZF does not prove AC, goes through the fact that ZF does not prove there's a wellordering of the reals.
However it is also consistent with ZF that the reals can be wellordered, but some larger set (say, the powerset of the reals) cannot be. --Trovatore (talk) 18:33, 13 December 2007 (UTC)
However, if V=L holds, then there is a specific (but very complicated) formula which well-orders the reals. JRSpriggs (talk) 05:51, 14 December 2007 (UTC)
I don't really see how that relates to the question. --Trovatore (talk) 07:06, 14 December 2007 (UTC)
To Trovatore: You are right that I was not addressing the specific question that was asked. But if his question was motivated by wanting to avoid having to postulate the existence of a set without having a way of constructing it, then I was pointing out that there is a way to construct it provided one is willing to discard all sets which are not in the constructible universe. JRSpriggs (talk) 08:06, 14 December 2007 (UTC)
Actually, it is sufficient to discard the reals which are not constructible. That is, because the constructible universe is well-ordered by a specific formula, its intersection with the reals is also well-ordered by that formula. In other words, you can use the construction of the constructible real numbers themselves to construct a well-ordering of the set of constructible real numbers. JRSpriggs (talk) 05:29, 15 December 2007 (UTC)

Can the wellorder of the reals as proved to exist under ZF+AC be explicitly stated, or described in any detail? I'm trying to wrestle with the implications of the wellordering theorem. I can conceptualize wellorders for all finite and countable sets. It would be nice to have an idea of what a wellorder of an uncountable set looks like or how it acts. Thanks! - UC Berkeley math student. —Preceding unsigned comment added by 98.210.233.159 (talk) 01:13, 19 April 2010 (UTC)

In general, the well-ordering of the reals may not be definable in any reasonable way. For example, in a model of ZFC + projective determinacy, every projective set is Lebesgue measurable, so there cannot be a projective well-ordering of the reals, because this would lead to the existence of a projective Vitali set. On the other hand, if V = L then there is a \Delta^1_2 well ordering of the reals. So although AC implies that there is a well-ordering of the reals, there may or may not be a nice formula that defines this well-ordering. — Carl (CBM · talk) 01:38, 19 April 2010 (UTC)
There is however a limit to how bad the simplest formula can be, if there's a formula at all. That's because there's a canonical, definable, wellorder of the ordinal-definable reals. If there is any definable wellorder of the reals, then every real is ordinal-definable, and therefore the canonical wellorder of the OD reals is a wellorder of all the reals.
Woodin has also placed a limit on the best lower bound on the complexity you can get just from large cardinals of the sort that we know about (the ones that are preserved under small forcing). As I understand it, he showed that small forcing suffices to add a \Delta^2_2 wellorder of the reals; therefore, no known large cardinals can refute the existence of such a wellorder. I don't know whether that's lightface or boldface. --Trovatore (talk) 08:01, 19 April 2010 (UTC)

Axiom of choice[edit]

How does the sentence Every well-ordered set is uniquely order isomorphic to a unique ordinal number, called the order type of the well-ordered set. relate to the axiom of choice? Unless I am confusing something, I think "axiom-of-choice-deniers" don't accept this. Albmont (talk) 15:52, 10 December 2008 (UTC)

You don't need choice to prove the above statement. You do need the axiom of replacement to prove a certain formalization of it (namely the one that identifies ordinals with von Neumann ordinals.) --Trovatore (talk) 18:46, 10 December 2008 (UTC)
Ok, I saw that in article ordinal number, section "Von Neumann definition of ordinals", this point is made; maybe the reference to the AC should be made more explicit, since "intuition" yells that the AC is invoked whenever we talk about infinite sets :-) Albmont (talk) 10:40, 11 December 2008 (UTC)
It does? What intuition is that? I would agree with this statement: The way of thinking about infinite sets that we've found most useful, makes it intuitively clear that AC is true. Is that what you meant? --Trovatore (talk) 20:14, 11 December 2008 (UTC)
Humour... it's a difficult concept... Of course, "intuition" and "set theory" are disjoint sets classes. Albmont (talk) 11:04, 12 December 2008 (UTC)
BTW, I added a {{main}} link to the article about ordinal numbers; there is the natural place to explore in more details what constructions do and what constructions don't require AC. Albmont (talk) 11:05, 12 December 2008 (UTC)
Intuition is absolutely central to set theory, as to any mathematics; you can't make progress without it. The important (and difficult) thing is to get the right intuitions. --Trovatore (talk) 17:07, 12 December 2008 (UTC)

Equivalent Formulations[edit]

How is it equivalent to say if a set is totally ordered then it is well-ordered? The way wolfram math world defines this makes this statement incorrect. http://mathworld.wolfram.com/WellOrderedSet.html There it uses the example of  \mathbb{Z} , which is totally ordered but is not well-ordered. Am I misreading this part of the article, or is this part incorrect? If it's correct, I think there needs to be a better explanation. Katachresis (talk) 04:50, 18 June 2010 (UTC)

I think that you are misreading it. It does not say that totally ordered and well ordered are the same.
None the less, I added a few words which I hope will make it clearer to you. JRSpriggs (talk) 08:14, 18 June 2010 (UTC)
Ok, it makes more sense to me, thanks. Katachresis (talk) 23:15, 20 June 2010 (UTC)

Why strict?[edit]

What is the reason for the insistence in the lead on the total order involved being strict? Specifying a total order, or a strict total order, is essentially the same thing, and this insistence is distracting. David Olivier (talk) 09:22, 11 May 2011 (UTC)

"Well-founded", in the definition in the lede, also presumes strict, at least in its formal definition. If you look closely, if x R x, then {x} does not have an R-minimal element. And, von Neumann ordinals are always strictly ordered by the element relation.
On the other hand, requiring the relation to be reflexive allows identification of <<X, R>> with R, as otherwise the empty relation is an exemplar of both the order types 0 and 1, making the proof that Hartog's function H satisfies H(X) \leq^{*} 2^{X^2}or 2^{H(X)} \leq 2^{2^{X^2}} more difficult. Also, all the examples in this article are reflexive. Perhaps we should rewrite, after all. — Arthur Rubin (talk) 13:20, 11 May 2011 (UTC)
I'm not an expert and certainly don't understand all that is at stake (I have no idea what that Groundhog's function is :P). But it does seem akward to me that the first sentence defines the well-order relation as strict, but then does nothing with this strictness: the concept of a least element is in substance the same, whether the order is strict or not (and is actually easier to define with a reflexive order). True, using a reflexive order might make the second sentence a bit more complicated to state; but the readability of the first sentence seems more important to me. David Olivier (talk) 15:40, 11 May 2011 (UTC)
This is a slightly annoying point — I think I brought it up some years ago but never followed through on it. In actual usage, I agree, both strict and nonstrict orders may be described as wellorders, and no one worries about it much. In an article, we probably have to worry about it at least a little.
We could: (A) State that some authors take wellorders to be strict and others to be reflexive, and give the two corresponding definitions, (B) say that there are different definitions depending on context, or (C) give a definition that covers both cases (e.g. the irreflexive part has no infinite descending sequence). For (C) we need a source; is there any source that does that? (A) and (B) are more honest but harder to figure out how we deal with the sourcing. --Trovatore (talk) 19:45, 11 May 2011 (UTC)
My mother, in Set Theory for the Mathematician, used "Hartogs' function" as a representation of what we call Hartogs number. Sorry about the confusion. I can't help with sourcing, though. — Arthur Rubin (talk) 00:46, 12 May 2011 (UTC)
First, {x} always has a minimal element, whether you take the order to be strict or not. You just have to define "minimal" properly.
Second, we should not insist on the order being strict, certainly not in the first paragraph of the article. There is no need to mention "strict" at all, as long as you use symbols like < and ≤ which make it clear whether you are talking about a reflexive or areflexive relation. Of course, in the AC-characterization we have to say "no strictly decreasing sequence" (which we do already).
Third: Personally, I prefer strict orders when talking about well-orders, because then I can use the symbol ∈ to denote the order relation on ordinals.
--Aleph4 (talk) 13:50, 12 May 2011 (UTC)

Many fundamental mistakes in the "Reals" subsection[edit]

I'll briefly cite some: "The natural numbers are a well-order." "The set {1/n : n =1,2,3,...} has no least element and is therefore not a well-order."

How come these errors weren't caught by anyone? This is mis-information and should be deleted or amended. 212.149.212.108 (talk) 14:07, 4 February 2012 (UTC)

Right above this list of examples it says A countably infinite subset of the reals may or may not be a well-order with the standard "≤". so these examples are using that relationship. RJFJR (talk) 16:10, 4 February 2012 (UTC)

Countability of well-ordered subsets of R[edit]

I think the previous paragraph in the Reals section about the countability of the well-ordered subsets of R was a little confusing. Any help in making the demonstration clearer is welcome, as you can probably see I'm not a native speaker. Odexios (talk) 14:39, 21 May 2012 (UTC)

Strict again[edit]

JR has reverted Tobias's changes on the grounds that "well-founded only applies to strictly-less; total order only applies to less-or-equal". Those may be the definitions in the linked articles but I do not think either restriction is really standard. In general these things are understood from context, and the appropriate modifications made silently and probably without even noticing. For example Wadge reducibility is nonstrict, and is wellfounded for as high as determinacy goes — no one bothers AFAIK to state this as "the strict part of Wadge reducibility".

To be sure, we can't be that sloppy in an article for general consumption, but interpreting whatever choice was made by whoever wrote the linked articles as somehow canonical is not the way to go either. Maybe we could use an explanatory footnote or something? --Trovatore (talk) 04:34, 12 December 2012 (UTC)

The existing lead already says "If ≤ is a (non-strict) well-ordering, then < is a strict well-ordering. A relation is a strict well-ordering if and only if it is a well-founded strict total order.". So there is no reason for Tobias's change unless it is more correct which it is not. JRSpriggs (talk) 04:56, 12 December 2012 (UTC)
Sorry about that, I really wasn't aware of that convention. Anyway, I would like to restore my other changes to the lead section which I hope are correct and uncontroversial. I am trying to improve the flow of the lead section which seems a bit unconnected to my eyes. —Tobias Bergemann (talk) 08:23, 12 December 2012 (UTC)
OK. JRSpriggs (talk) 09:28, 12 December 2012 (UTC)

Axiom of Dependent Choice and "Every Strictly Descending Sequence is Finite"[edit]

In the "Equivalent Formulations" section, the article states that the Axiom of Dependent Choice is required to prove that a well-ordered set cannot have an infinite decreasing sequence. However, isn't the fact that the set is well-ordered precisely what the Axiom of Dependent Choice is there to prove? Since we are assuming the set is well-ordered, it is already order-isomorphic to a unique ordinal, and thus has an infinitely decreasing sequence if and only if the ordinal does as well. However, it is easy to prove that any decreasing sequence of ordinals (and thus decreasing sequence of elements of an ordinal) is finite by transfinite induction without any form of the Axiom of Choice. If every ordinal smaller than alpha has no infinitely decreasing subset, then alpha has no infinitely decreasing subset, for its first element must be some alpha_0 < alpha. After this element, every other element is in alpha_0, so the remainder of the sequence must be finite. However, adding a term to a finite sequence does not yield an infinite sequence.

Am I missing something? — Preceding unsigned comment added by 140.180.243.190 (talk) 22:10, 25 March 2013 (UTC)

You are looking at the wrong direction of implication. In well-order#Equivalent formulations, #3 can be deduced from the other versions without DC as you see. Where DC is needed is to go from #3 to the other versions. Without some version of the axiom of choice, there could be a non-well-ordered linear ordering which lacks any infinite decreasing sequences. If x0>x1>x2>...xn is a finite sequence of elements above the end of the well-ordered initial segment of the ordering, then there is an xn+1<xn which is also above the end. But we need DC to make an infinite sequence of such choices. JRSpriggs (talk) 08:37, 26 March 2013 (UTC)

Choice of Set theory and independence result.[edit]

"Every well-ordered set is uniquely order isomorphic to a unique ordinal number, called the order type of the well-ordered set. "

This is a consequence of ZF, but is independent of Zermelo Set Theory (and if I recall correctly is the biggest reason for preferring ZF over Z set theory.) Is it fair to mention this? Given that Z is a common axiomitization I feel it's a valid thing to mention, unlike for example something that's a consequence of the axiom of infinity. — Preceding unsigned comment added by James Waddington (talkcontribs) 21:23, 15 July 2014 (UTC)

I'm not opposed to mentioning after the fact that you need Replacement to prove this property. But we should still state the property without waffling. --Trovatore (talk) 21:33, 15 July 2014 (UTC)