Talk:Completeness (order theory)

From formulasearchengine
Jump to navigation Jump to search

Question about A poset is chain-complete iff it is a dcpo.

The following equivalence requires the Axiom of Choice:

A poset is chain-complete iff it is a dcpo.
Can anybody give a proof of this proposition?

(this is an anon question I moved from the article page) Oleg Alexandrov 17:32, 22 Apr 2005 (UTC)

Chain-completeness is a stronger notion than omega-completeness, contrary to the definition given in the article. Omega-completeness says that every chain of order type omega has a least upper bound, whereas chain-completeness says that every totally ordered set (regardless of order type) has a least upper bound. (WilliamDClinger (talk) 19:52, 4 June 2008 (UTC))

Hard to understand

I just learned about the "completeness axiom" (that is, existence of all infima and suprema) in advanced calculus but unfortunately this article is a bit too dense for me. Why is the axiom necessary?What would happen if we were to assume the opposite, that not all of them exist? And I guess I see how all these axioms are related but I don't quite 'get it'. Maybe the other notions of completeness could be moved out of the article summary? Dranorter (talk) 21:41, 3 July 2009 (UTC)

Perhaps you are thinking of Zorn's lemma, which is equivalent to the axiom of choice. linas (talk) 15:28, 17 April 2012 (UTC)

Easiest example?

OK, call me stupid, but... I don't understand the "easiest example". The section Least and greatest elements begins with:

The easiest example of a supremum is the empty one, i.e. the supremum of the empty set. By definition, this is the least element among all elements that are greater than each member of the empty set. But this is just the least element of the whole poset.

This seems to make two implicit assumptions: first, that given my binary order relation, that "all elements are greater than each member of the empty set". This seems to imply that I can compare element x to nothing at all, but this seems crazy. The alternative is to try to do logic with the empty set: 'nothing is greater than every element of the empty set'. And 'the least element of nothing is nothing'. And 'sup is defined as the least element'. Therefore 'sup is nothing', and therefore 'nothing is the least element of the whole poset.' You can see that my logic broke down, there, somewhere. This kind of thinking seems very contorted to me. I honestly don't get it. But I've noticed that many texts on order theory seem to make this implicit assumption, but I don't understand why, I don't understand the mechanics. It seems strange to me.

(Viz, I have a text here that says and . And I don't get it.)

If I view an order relation R as a class of pairs (x,y), I just don't understand how to interpret the empty set w.r.t. R. There seems to be some kind of unwritten "law of excluded middle" at work, here: 'it can't be less then, ergo it must be greater than'? But there are certainly logics that don't admit/require the law of the excluded middle, so why should order theory demand it?

Next, the above makes the implicit assumption of the existence of the least element. So, consider the set of all negative integers. Normally, one says that this set has no least element. The above sentence imply that this set not only has a least element, but that its somehow given by the empty set. Confusing, to me.

What am I missing? Can the article be modified to clarify this, in general? linas (talk) 15:13, 17 April 2012 (UTC)

From upper and lower bounds: The empty subset ∅ of a partially ordered set K is conventionally considered to be both bounded from above and bounded from below with every element of P being both an upper and lower bound of ∅.

What's missing from 'the least element of the whole poset' is if it has one. The empty set doesn't necessarily have a supremum or infimum. I added it. (talk) 04:44, 26 January 2014 (UTC)

About the section "completeness of domains"

Domain theory is a very well-studied branch of mathematics with significant applications in Computer Science. Order theory and completeness properties are very important in Domain Theory so it's quite appropriate to mention Domain Theory in this article.

However, when I looked at the Completeness(order theory) article on 4/16/2013, the section "Completeness of Domains" did not even refer to the Wikipedia article on Domain Theory but instead put forth a a non-traditional formulation of Domain Theory in terms of "isolated elements" which weren't even mentioned in the Domain Theory article on 4/16/2013. I don't believe this article is the appropriate place to do that.

Domain Theory had already been mentioned earlier in the article. Maybe that could be expanded on further, but I don't believe this section was the appropriate way to do that in an encyclopedia. Since the entire section was based on a non-traditional formulation of Domain Theory, I removed the entire section.

Upon further investigation (see the article History) it appears that the section "completeness of domains" was written by Carl Hewitt, who was subsequently banned by Wikipedia see The section in question heavily emphasized the work of Hewitt and his students, including Will Clinger. I was not aware of this when I removed the section. Pmokeefe (talk) 12:51, 16 April 2013 (UTC)