# Initial Segments and Initial Sections of Posets

For a set A with a partially ordering <=, define the following

1) A subset s(x) of A = {y in A such that y <=x}

2) A subset S of A with the property that for every x in S then all y in A which are <= x are also in S.

Most references I find call s(x) the initial segment of the element x in A. But in Azriel Levy’s book

he calls s(x) the initial section of x in A and defines S as an initial segment. I can’t find any other reference to a set defined as S is.

Levy goes on to say that every set s(x) has the property of S (which would appear to follow by transitivity).

To me it would appear that even if the ordering is total then it doesn’t necessarily follow that every S has an x where S = s(x): e.g. A is the rationals with normal ordering and S = {rationals that when squared <= 2} .

I chanced on the “initial section” reference reading a proof of transfinite recursion, p.27 of http://www.uwec.edu/andersrn/SETSIII.pdf

Can anyone clarify segments and sections, confirm common usage of terminology, and give a hint or reference to the usage of sets like S ?

-

My answer below has been edited in response to @user21929's comment.

Let $\mathbb{P}=\langle P,\leq\rangle$ be a poset.

A set $S\subseteq P$ satisfying $$\forall p\leq q\in P \, \big(q\in S \to p\in S\big)$$ has lots of names. Davey and Priestley's Introduction to Lattices and Order refers to them simply as down sets. The "bible" of the field, Continuous lattices and domains takes a more topological approach and calls them lower sets. Myself, I have always preferred downward closed. And of course, initial segment is also widely used, although more often in the context of total orders (such as Jech's Set Theory).

Major edit: In my original answer, I included order ideal in my list of synonyms for lower set. However, as @user21929 pointed out, an order ideal in a directed lower set. (A lower set $A$ is directed if: $$\forall x,y\in A\, \big(\exists z\in A \, (x\leq z) \wedge (y\leq z)\big).$$ This property of being directed is true of some but not all lower sets. It follows that all order ideals are lower sets, but not all lower sets are order ideals. For example, if $\mathbb{P}$ is the power set of some infinite set $U$, ordered by inclusion, then the set of finite subsets of $U$ is an order ideal (since for any two finite subsets, there is a finite subset containing them), but the set of subsets $\subseteq U$ satisfying $\vert A\vert\leq k$ (for some finite $k$) is a lower set which is not an order ideal.

However, if $\mathbb{P}$ has additional structure (e.g., if it's a lattice, or Boolean algebra, or anything stronger than a join-semilattice) then the notions of lattice ideal, Boolean ideal, etc. coincide with that of an order ideal.)

If we let $\mathcal{O}(\mathbb{P})$ denote the poset of downward closed sets of $\mathbb{P}$, ordered by inclusion (Davey and Priestly claim that this is traditional notation, the $\mathcal{O}$ denoting *order ideal*m my comments above notwithstanding, (texts such as Johnstone's Stone Spaces use $\textrm{Idl}(\mathbb{P})$ to define the actual order ideals), then we define a function $\downarrow:\mathbb{P}\to\mathcal{O}(\mathbb{P})$ by: $$\downarrow p = \{q\in P \vert q\leq p\}.$$

This function doesn't seem to have a particularly nice name, but the set $\downarrow(p)$ is generally called the principal order ideal generated by $p$ (Johnstone), the principal down-set generated by $p$ (Davey and Priestley), or the lower set of $p$ (Continuous Lattices and Domains). This function is an order preserving operation: if $p\leq q$, then $\downarrow p \subseteq \downarrow q$. (Note that calling this the principal order ideal is not problematic here: while some lower sets may not be order ideals, all sets of the form $\downarrow(p)$ are.

Just as not all lower sets are order ideals, not all order ideals are principal order ideals (the example of finite subsets of some infinite set $U$ is a non-principal order ideal). However, it is worth noting that principal order ideals are also principal lattice ideals and principal Boolean algebra ideals, if you are working in a lattice or a Boolean algebra.

If $S\subseteq P$, then one can also take the order ideal generated by $S$ (denoted $\downarrow S$): $$\downarrow S=\bigcup_{s\in S}\downarrow(s).$$ (I'm sure that you can guess the other names that this object has.)

It is in this context that I tend to prefer downward closed (I tend to use order ideal when I am thinking about points and downward closed when talking about sets): this function (viewed as a poset homomorphism from the power set of $P$ to itself) is easily seen to be a closure operator (it is idempotent, expansionary and order preserving). In addition, this operation is stable under finite (in fact, arbitrary) unions, and so is a topological closure opeator (satisfying Kuratowski's closure axioms). It therefore induces a topology, which is, unsurprisingly, the right order topology induced by $\leq$ (that is, the topology generated by the upper sets/order filters).

In this context, principal order ideals are the closures of singletons.

-
Well thanks. At least my rubbish answers on the product of digits math.stackexchange.com/questions/712454/… seems to have generated some attention on this question. My context here is relatively basic: I'm just looking for correct terminology with reference to the proof of the principle of transfinite induction - I assume that I would be generally understood if I referred to a subset s(x) of P where y in P is in s(x) if y<=x as an initial segment. – Tom Collinge Mar 14 '14 at 21:17
Absolutely. In fact, the Jech reference I mentioned above uses the term initial segment in exactly that context. – Unwisdom Mar 14 '14 at 21:20
The answer by Unswisdom is wrong. Johnstone, Stone spaces, page 286: "if A is a poset, we say a subset of A is an ideal if it is upwards directed and a lower set". It is not true that any lower set is an ideal. The ideal completion Idl(P) of a poset P is not the poset of downward closed sets. – user21929 Mar 18 '14 at 18:18
@user21929 Oh dear, that was careless of me. Thanks for pointing that out. I'll edit my answer accordingly! – Unwisdom Mar 18 '14 at 18:37
I have made the edits. The error was that I had forgotten that order ideals need to be directed (a fact that does not affect principal down/lower sets, which are automatically directed and thus automatically principal order ideals). Thanks again to @user21929 for pointing out my mistake. – Unwisdom Mar 18 '14 at 18:59

Jean-Louis Krivine in his book on set theory ("Théorie des ensembles") gives the same definition of "initial segment" ("segment initial" in French) as Azriel Levy. Otherwise the phrasings "lower set" and "the set is downward closed" are often used (see http://en.wikipedia.org/wiki/Upper_set).

You say: "even if the ordering is total then it doesn’t necessarily follow that every S has an x where S = s(x)": notice that it might happen even with well-ordered sets (for instance in $\mathbb{R}$). But we have the following: in a well-ordered set $A$, a subset $S$ of $A$ is an initial segment if, and only if, $S = A$ or $S = s(x)$ for some $x \in A$.

-
Thanks for the reference. To clarify my statement about S, I mean that a set S such that for every x in S and y in A if y <= x then y is in S. A set with this property is not neccessarily an initial segment (taking the more commonly used meaning of initial segment as a set s(x) containing all y in A y <= x): any such set S which does not cotain its supremum will not be an intial segment. But it might be a strong initial segment: does it follow that if S is not an initial segment then S is a strong initial segment (i.e. contains all y < x) Actually not: my example with rationals shows so. – Tom Collinge Mar 10 '14 at 7:28