Talk:Upper set

Please discuss this on the talk page of lower set. — Tobias Bergemann 08:51, 28 August 2006 (UTC)

OK, I did the merge. The two articles had slightly different wording for their examples, so for now I left them both. This will be confusing, since the upper and lower sets are really the same, but someone with more math theory than me should figure out which wording is the best, and use it for both definitions.Lisamh 21:01, 19 September 2006 (UTC)

Do you reckon we should change the name of the article to 'Upper sets and lower sets' or similar? Joel Brennan (talk) 16:35, 19 April 2019 (UTC)

The article says "... an upper set is a subset Y of a given partially ordered set (X,≤) such that, ...". But the condition that the set is partially ordered is too strong. A preorder is sufficient for the possibility that a upper set exists. —The preceding unsigned comment was added by 217.225.228.95 (talk) 19:19, 31 December 2006 (UTC).

You're right. We could add a section to tell that. But in practice it has very little use, since by defining the equivalence relation A≈B iff A≤B and B≤A and taking the quotient space of X under this relation (X/≈), once gets a partial order ←. You can then find the upper sets of (X,≤) from the upper sets of (X,←). Moreover, some properties and definitions of upper sets are easier to define/demonstrate, or only valid in the context of partial orders.--Clément Pillias (talk) 20:06, 6 November 2008 (UTC)

Am I right that upper sets of a partially ordered set Y with |Y|=n are isomorphic to the abstract simplicial complexes over n vertices? If so, it seems reasonable to add cross-references. Hv (talk) 11:39, 10 August 2010 (UTC)

The article currently says, "A lower set is called principal if it is of the form ↓{x} where x is an element of X." Is this really supposed to say lower set? It makes almost no sense in terms of motivation/usefulness. For the case of power sets, a principal lower set is then just the specified singleton and the empty set. Who cares enough about this structure to single it out? Perhaps I have misunderstood something.? It makes much more sense for upper sets, and indeed ultrafilters (which are upper sets) are called principal just in case they have this form (some cluster point x). Also, are upper sets of the form ↑{x} not called principal? Cheers, Honestrosewater (talk) 04:05, 10 January 2012 (UTC)

I think you're missing a level of set containership. The principal lower set defined by a singleton set {x} of a power set P(X) would be ↓{{x}}, not ↓{x}. The principal lower set defined by any other set S in in a power set P(X) is ↓{S}. S does not have to be a singleton here. In the article, it writes "↓{x}" but in that case x ias an element of a partially ordered set, not an element of the universe of a powerset. —David Eppstein (talk) 04:47, 10 January 2012 (UTC)

Oh, right, right. I misread that. Cheers, Honestrosewater (talk) 05:29, 10 January 2012 (UTC)

The article state : "Conversely any antichain A determines an upper set {x: for some y in A, x ≥ y}. For partial orders satisfying the descending chain condition this correspondence between antichains and upper sets is 1-1, but for more general partial orders this is not true". Can you give a reference for this property ? — Preceding unsigned comment added by 78.198.27.23 (talk) 14:30, 18 October 2017 (UTC)

Sorry for my ignorance, and sorry if I reply in the wrong place, but as I read this books description of Upper Set,

https://math.mit.edu/~dspivak/teaching/sp18/7Sketches.pdf

then isn’t the Upper Sets of the Powerset of {1,2,3,4}, the sets {1,2,3,4}, {2,3,4}, {3,4} and {4}?

I mean, how can {1} be an Upper Set in itself, since according to the definition then all elements larger than 1 is included in the Upper Set? 94.18.238.170 (talk) 16:50, 9 December 2022 (UTC)

The power set is the family of all subsets. It is partially ordered by set inclusion. The numerical values are irrelevant to its definition. —David Eppstein (talk) 19:39, 9 December 2022 (UTC)

Thanks for responding on this and sorry, I think I failed to express my question clearly.

I was refering to the hasse diagram exampple on this page, ordering the power set of {1, 2, 3, 4} and marking the Upper Sets in the diagram in green.

Here e.g. {1} has been marked in green to represent an Upper Set as I read the text.

The question is that I fail to understand how e.g. {1} can be an Upper Set given the definition and an Upper Set?

My understanding from reading the definition and the referenced book, is that the following sets should have been marked in green (i.e. as Upper Sets) {1,2,3,4}, {2,3,4}, {3,4} and {4}?

But maybe I am misunderstanding the purpose of the coloring? 94.18.238.170 (talk) 04:45, 10 December 2022 (UTC)

The diagram does not show {1} being an upper set. It shows {{1},{1,2},{1,3},{1,4},{1,2,3},{1,2,4},{1,3,4},{1,2,3,4}} as being an upper set. Upper sets are defined for things that have a partial order on them. The "things" here are themselves sets, like {1}, and the partial order on them is set inclusion, like {1} ⊆ {1,2,4}. It is an upper set because whenever a thing like {1} is in it, the bigger things like {1,2,4} are also in it. —David Eppstein (talk) 05:42, 10 December 2022 (UTC)

Beautiful explanation. Thanks a lot! I by mistake thought that the preorder relation (I hope I use the wording correctly) were on the natural numbers. But now I see, as you wrote in your previous comment, that the preorder relation is on the set inclusion. I hope I got it. Again, thanks a lot for the clarification! 94.18.238.170 (talk) 08:06, 10 December 2022 (UTC)

And the diagram is showing the upward closure of the element {1}. I hope I got it. 94.18.238.170 (talk) 08:23, 10 December 2022 (UTC)

I suggest to change to a relation on natural numbers ("is divisor of"), rather than on sets, to avoid the set-of-sets confusion above. - Jochen Burghardt (talk) 15:47, 10 December 2022 (UTC)

Yes, I think that was unnecessarily confusing. —David Eppstein (talk) 18:34, 10 December 2022 (UTC)

Quite surprised that this article almost entirely dismisses the (common, at least in certain areas of mathematics) names "(order) filter" and "order ideal" for upper set and lower set. For example, these are attested to in Stanley's Enumerative Combinatorics, volume 1, Ch 3.1:

An order ideal (or semi-ideal or down-set or decreasing subset) of P is a subset I of P such that if t in I and s ≤ t, then s in I. Similarly a dual order ideal (or up-set or increasing subset or filter) is a subset I of P such that if t in I and s ≥ t, then s in I.

--JBL (talk) 00:05, 14 April 2026 (UTC)

This is because those names conflict with the more common notions of filter and ideal which require directedness. I clarified this point in the article. Elestrophe (talk) 16:48, 14 April 2026 (UTC)

I understand the issue of conflicting terminology, but nevertheless it is the case that the objects that are the subject of this article are often known as "order filters" and "order ideals". Your edits improve clarity on one point but make the situation worse on another point by removing one of the synonyms entirely! The true situation (that should somehow be reflected in this article) is that there is a significant body of mathematics that uses the words "order ideal" for "downset", and also a significant body of mathematics that uses the words "order ideal" for a particular subclass of downsets. Maybe there should be a section titled "Terminology" or something like that, instead of cramming a zillion bold synonyms into the lead. --JBL (talk) 18:59, 14 April 2026 (UTC)

I changed "ideal" to "order ideal" and used more neutral language. Elestrophe (talk) 19:39, 14 April 2026 (UTC)

It has been proposed in this section that Upper set be renamed and moved to Upper and lower setsUpper and lower sets. A bot will list this discussion on the requested moves current discussions subpage within an hour of this tag being placed. The discussion may be closed 7 days after being opened, if consensus has been reached (see the closing instructions). Please base arguments on article title policy, and keep discussion succinct and civil. Please use {{subst:requested move}}. Do not use {{requested move/dated}} directly. Links: current log • target log • direct move

Upper set → Upper and lower setsUpper and lower sets – The article already discusses upper and lower sets with equal weight (which is appropriate since they are entirely symmetrical notions). The title should reflect this for clarity, similar to other articles like Sine and cosine. Elestrophe (talk) 17:08, 14 April 2026 (UTC)

This seems like a good suggestion. --JBL (talk) 18:54, 14 April 2026 (UTC)

Some more examples: Maximal and minimal elements, Upper and lower bounds, Greatest element and least element, Infimum and supremum, Initial and terminal objects. Elestrophe (talk) 19:50, 14 April 2026 (UTC)

I think this is a good idea as it would make the symmetric scope of this article more obvious. —David Eppstein (talk) 21:15, 14 April 2026 (UTC)

Support: less confusing about the scope of the article. (I admit I was misled by the article title initially.) Taku (talk) 00:41, 15 April 2026 (UTC)

Support, per nom.--SilverMatsu (talk) 04:06, 15 April 2026 (UTC)

Support as the article treats the notions symmetrically. Stepwise Continuous Dysfunction (talk) 05:01, 15 April 2026 (UTC)

So, I have merged initial segment into this article. To be honest, I'm not too sure about the presentation. In set theory, the term "initial segment" is more common so the article uses that term in the discussions taking place in set theory (otherwise, the text would read very strange to readers.) I have also tried to emphasize the symmetry doesn't really holds for initial segments appearing in set theory; i.e., there is no upper set counterpart. Especially in the case of a binary relation, it just doesn't make much sense (because in logic, we always go from left to right). Hope this doesn't come out too strange. Taku (talk) 08:04, 15 April 2026 (UTC)

Not sure what merger you are talking about. But some comments about "initial segment".

Initial segments in my mind apply to any total order. It's basically a lower set in a total order (in particular in a well-ordered set, which is a totally ordered set). I don't think it makes sense to say that "initial segment" is a synonym for "lower set" for general posets, as you implied by adding the term in a list of terms in the lead. As far as you know, is this term ever used for total orders that are not well-ordered?

We should remove it from the list of terms in the lead, and instead expand the section about "initial segment" to start by giving the definition at the top of it.

Also, since that section is really an example/special of lower set in a very special kind of poset, it could/should be moved further down, after the general "upper closure" section, which applies to any poset.

Let me know if you want me to help with any of that. PatrickR2 (talk) 06:29, 16 April 2026 (UTC)

@Elestrophe Just realized you already did a bunch of cleanup here. What do you think of the above? PatrickR2 (talk) 18:01, 16 April 2026 (UTC)

I agree with all of it. Elestrophe (talk) 18:38, 16 April 2026 (UTC)

By the merger, I meant the merger of (the consensus was a separate article wasn’t warranted). As for initial segments, yes, it’s most commonly applied to total ordered sets like well-ordered sets, but they are also defined and used in a more general situation. The article gives a reference. That usage seems to be mostly limited to the foundation stuff (like set theory) but I think that usage is worth mentioned. I thought that might be distracting, as you noted, so my initial instinct was to cover it in a separate article. As for the order of the closure section or the initial segment section, I don’t have a strong opinion but some readers would be expecting set theoretic materials so I don’t agree the closure is more important (some would come from links to initial segment). That’s my position at least (I can acknowledge others might disagree.) The bottom line is that I care some facts are noted in Wikipedia somehow but less about the exact presentation Taku (talk) 00:38, 17 April 2026 (UTC)

You can change the Initial segment redirect so that it redirects to a particular section. Elestrophe (talk) 14:05, 17 April 2026 (UTC)

Yes, of course, 100%, and someone (JRSpriggs) has already made that change. Taku (talk) 02:30, 18 April 2026 (UTC)

I can agree that we shouldn’t give an impression that a lower set and an initial segment are commonly used synonymously (that was not my intent). I made an attempt to clarify that in the lead. Taku (talk) 00:46, 17 April 2026 (UTC)

I just noticed Halmos in his Naive Set Theory defines initial segments for posets; more precisely, principal initial segments (he limited himself to principal ones probably because those are enough; e.g., for a proof of Zorn's lemma). So, again, the term initial segment is not limited to totally ordered sets. Taku (talk) 05:35, 17 April 2026 (UTC)

@TakuyaMurata As an aside, I am not sure Halmos's "Naive set theory" is a good reference nowadays. It is too "naive". The same material is available in better sources. PatrickR2 (talk) 22:09, 19 April 2026 (UTC)

The book is certainly dated in some places like some terminology. But the content itself is finite; despite naive in the title, there is no issue with rigor. For example, I looked at the section on well-ordered sets in Jech, Set Theory and the proofs there are exactly the same as those in Halmos (probably because this is a standard stuff and no need to change it). In fact, Halmos introduces axioms more sparingly so in his treatment on well-ordered sets, it’s clearer that the axiom of replacement is not needed (one reason why you might prefer well-ordered sets to ordinals). So, Halmos, despite age, seems perfectly fine and usable as a reference. (Of course, Jech covers so much other stuff that are not in Halmos.) Taku (talk) 02:10, 20 April 2026 (UTC)

@Elestrophe @Taku I looked a little at Taylor's book "Practical foundations of mathematics". Maybe it's just me, but I find it full of ideas, explained in a very fuzzy, stream-of-conciousness kind of way, the kind of "mathematics book written by a physicist". It is not quite rigorous, not carefully written to allow one to really understand a subject, really not a good book as far as mathematical exposition is concerned. Then I took a look Jech's "Set theory" for a better, more accessible and more serious book. He defines it on p. 18 for a well-ordered set W as the set of elements less than a fixed element of W. Initial segment is then used in various theorems and corollaries. I would suggest to replace Taylor with Jech (or another similar serious reference).

But more importantly, the whole section "Initial segments of well-ordered sets" is much more about properties of well-ordered sets and relations concerns than about lower sets per se. So in my opinion, this section belongs in the Well-order article much more than here and should be moved to that article. Please let me know if you disagree. PatrickR2 (talk) 03:25, 19 April 2026 (UTC)

This review of Taylor's book is instructive. "A confusing hodgepodge of tangential ideas" PatrickR2 (talk) 03:38, 19 April 2026 (UTC)

You’re echoing my initial reservation: this article may not be a good place to discuss the use of initial segments in set theory. It seems the question is where to redirect "initial segment". I can see maybe redirecting it to well-order isn’t too weird since the term is most commonly used in the case of a well-ordered set.

As for Taylor vs other references, Amazon reviews are not reliable. Basically the book isn’t intelligible without some category theory backgrounds. His book is fairly frequently referred in nlab and related places. So, he is certainly well regarded. He definitely likes to refer to history or does philosophical discussion. This does not make the book unreliable. With sufficient due diligence, his book is citable (diligence since his book is somehow unusual, editors need to be careful when citing it; like checking actual proofs). Taku (talk) 05:36, 19 April 2026 (UTC)

I am sure this is not a bad book for people who already know the material. But it is hard to get into and a rather poor book as far as exposition is concerned, specifically for people who want to learn the material. (That was my opinion before finding that Amazon review.) And since there are many other books that are rigorous and clear and do mention initial segments, I think it would be preferable to use those. As for nlab, Taylor's book is the kind of book they like. That does not mean much. Anyway, no problem if you want to keep that reference. It was just a suggestion to find a better one for use in wikipedia. PatrickR2 (talk) 22:02, 19 April 2026 (UTC)

It depends on materials. For standard stuff like statements of the axioms, Jech (or some other) is of course good and may be preferred since they are more widely used (Jech is not necessarily more recent than Taylor, I think). On the other hand, Jech, while I didn’t read the whole book carefully, doesn’t seem to have in-depth discussion of induction and recursion, the main theme of Taylor. (Maybe a filter stuff can be used as an alternative; I don’t know.) So, for some peripheral stuff, some other references are needed. It is important to cover standard stuff in standard ways, obviously, but some alternative or variants also merit mentions (nlab likes those and Wikipedia doesn’t need to be shy away either). Taku (talk) 02:25, 20 April 2026 (UTC)

I agree. PatrickR2 (talk) 17:30, 20 April 2026 (UTC)

I agree about the placement of the material. Elestrophe (talk) 06:29, 19 April 2026 (UTC)

I am happy that everyone here seems to concur about moving that section. As for the redirect, it can be to a specific new section of the Well-order article. PatrickR2 (talk) 22:04, 19 April 2026 (UTC)