#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Exercise 41 - Chapter 1

edited April 2018

Prove that the poset of upper sets on a discrete poset (see Example 1.25) on a set $$X$$ is simply the power set $$P(X)$$.

• Options
1.

An upper set in P is a subset U of P satisfying the condition that if p ∈ U and p ≤ q, then q ∈ U.

Because in a discrete poset we only have order between a element and itself, for every element p ∈ X any subset of X containing p will be in the set of all upper sets of X. Because we are talking about any p in X, we have all non-empty subsets of X. We can also add the empty subset, because upper sets are defined in terms of some conditions on elements, and without elements, it'll be automatically true. In other words, the set of of upper sets is the set of all subsets of X - the power set PX.

The exercise does not limit us in how the order on the poset of upper sets should be defined, but the authors probably meant something like in 1.38 "We can give the set U an order by letting U ≤ V if U is contained in V." which is for subsets reflexive and transitive.

Comment Source:An upper set in P is a subset U of P satisfying the condition that if p ∈ U and p ≤ q, then q ∈ U. Because in a discrete poset we only have order between a element and itself, for every element p ∈ X any subset of X containing p will be in the set of all upper sets of X. Because we are talking about any p in X, we have all non-empty subsets of X. We can also add the empty subset, because upper sets are defined in terms of some conditions on elements, and without elements, it'll be automatically true. In other words, the set of of upper sets is the set of all subsets of X - the power set PX. The exercise does not limit us in how the order on the poset of upper sets should be defined, but the authors probably meant something like in 1.38 "We can give the set U an order by letting U ≤ V if U is contained in V." which is for subsets reflexive and transitive.
• Options
2.

Start with the empty set. If $$\emptyset \in U$$, then so are each of the discreet elements of $$X$$. If each of the discreet elements are in the upper set, so are each of the unique pairs, and so on. Finally, the "largest" upper set must be $$X$$ itself. This collection is the power set $$PX$$ .

But why would $$\emptyset$$ be permitted as an upper set? I understand it to be present in the power set, so it must be allowed somehow

Comment Source:Start with the empty set. If \$$\emptyset \in U \$$, then so are each of the discreet elements of \$$X \$$. If each of the discreet elements are in the upper set, so are each of the unique pairs, and so on. Finally, the "largest" upper set must be \$$X \$$ itself. This collection is the power set \$$PX \$$ . But why would \$$\emptyset \$$ be permitted as an upper set? I understand it to be present in the power set, so it must be allowed somehow
• Options
3.

$$X$$ is discrete, so $$x \leq x, \forall x \in X$$ and $$x \nleq y$$ iff $$x \neq y$$

Consider any subset of $$X$$, $$U \subseteq X$$

Since, for all $$u \in U$$ the only thing related to $$u$$ is itself, and $$u \in U$$, $$U$$ is an upper set of $$X$$.

It follows that the power set $$PX$$ of all subsets of $$X$$ forms a poset of upper sets.

Comment Source:\$$X\$$ is discrete, so \$$x \leq x, \forall x \in X\$$ and \$$x \nleq y\$$ iff \$$x \neq y\$$ Consider any subset of \$$X\$$, \$$U \subseteq X\$$ Since, for all \$$u \in U\$$ the only thing related to \$$u\$$ is itself, and \$$u \in U\$$, \$$U\$$ is an upper set of \$$X\$$. It follows that the power set \$$PX\$$ of all subsets of \$$X\$$ forms a poset of upper sets.
• Options
4.
edited April 2018

Is a key insight for this proof, that the upper set U, can contain elements that cannot be compared to the smallest element in U?

Asking because it almost easier to answer the question: Given all possible subsets of a discrete preorder P, show that they are all 'upper sets' of some element of P.

Comment Source:Is a key insight for this proof, that the upper set *U*, **can** contain elements that cannot be compared to the smallest element in *U*? Asking because it almost easier to answer the question: Given all possible subsets of a discrete preorder P, show that they are all 'upper sets' of some element of P.
• Options
5.
edited April 2018

I think the trick is that there may be multiple "smallest" elements. In the discrete case, they're all smallest -- and all incomparable.

You might be assuming that upper sets are always principal, which is not necessarily true. In the discrete case, $$\{x, y\}$$ (for distinct $$x, y$$) is an upper set, but it is not principal.

Comment Source:I think the trick is that there may be multiple "smallest" elements. In the discrete case, they're all smallest -- and all incomparable. You might be assuming that upper sets are always principal, which is not necessarily true. In the discrete case, \$$\\{x, y\\}\$$ (for distinct \$$x, y\$$) is an upper set, but it is not principal.
• Options
6.

Thx @JonathanCastello. What is the meaning of 'principle', is it similar to 'the only one'?

I am finding it somewhat challenging to reconcile, the book's def of upper set:

“If p is an element then so is anything bigger"

with this case of incomparable members.

Comment Source:Thx @JonathanCastello. What is the meaning of 'principle', is it similar to 'the only one'? I am finding it somewhat challenging to reconcile, the book's def of upper set: >*“If p is an element then so is anything bigger"* with this case of incomparable members. 
• Options
7.
edited April 2018

Thx @JonathanCastello. What is the meaning of 'principal', is it similar to 'the only one'?

Not exactly.

It means "generated by just one element".

We say $$U$$ is the principal upper set of $$p$$ if and only if $$U = \{ q\, : \, p \leq q \}$$

I've seen this written as $$\uparrow\{p\}$$, $$\{p\}^u$$, $$\{p\}^{\tiny \triangle}$$, and sometimes $$\uparrow p$$ or the like.

Similarly, in abstract algebra, we say $$I$$ is the principal ideal generated by $$a$$ in a ring $$R$$ if and only if $$I = \{ a \cdot r \, : \, r \in R\}$$.

Comment Source:> Thx @JonathanCastello. What is the meaning of 'principal', is it similar to 'the only one'? Not exactly. It means "generated by just one element". We say \$$U\$$ is the *principal upper set* of \$$p\$$ if and only if \$$U = \\{ q\, : \, p \leq q \\}\$$ I've seen this written as \$$\uparrow\\{p\\}\$$, \$$\\{p\\}^u\$$, \$$\\{p\\}^{\tiny \triangle}\$$, and sometimes \$$\uparrow p \$$ or the like. Similarly, in abstract algebra, we say \$$I\$$ is the principal ideal generated by \$$a\$$ in a [ring](https://en.wikipedia.org/wiki/Ring_(mathematics)) \$$R\$$ if and only if \$$I = \\{ a \cdot r \, : \, r \in R\\}\$$.
• Options
8.

One problem with internalizing upper sets on a discrete preorder rests precisely on what you quoted, Vladislav:

“If p is an element then so is anything bigger"

On the discrete preorder, nothing is ever bigger. So this condition is vacuously true, always.

Comment Source:One problem with internalizing upper sets on a discrete preorder rests precisely on what you quoted, Vladislav: > “If p is an element then so is anything bigger" On the discrete preorder, _nothing is ever bigger_. So this condition is vacuously true, always.
• Options
9.
edited April 2018

Thank you. With that ,and reading Thrina's explanation, above, I now understand why there are as many upper sets in X, as there are elements in X's powerset. Essentially, any non-empty subset of X is an upper set of some element in x, except the empty set.

I initially would say, that if a set contains at least one element that is not bigger than x -- then that set is not an upper set of x. But it seems to be an incorrect negation of "If p is an element then so is anything bigger".

The number of upper sets of a discrete set, then, should be $$2^n - 1$$ (where n is the number of elements in the discrete set), not $$2^n$$ ?

Comment Source:Thank you. With that ,and reading Thrina's explanation, above, I now understand why there are as many upper sets in X, as there are elements in X's powerset. Essentially, any non-empty subset of X is an upper set of some element in x, except the empty set. I initially would say, that if a set contains at least one element that is **not** bigger than x -- then that set is **not** an upper set of x. But it seems to be an incorrect negation of "*If p is an element then so is anything bigger*". The number of upper sets of a discrete set, then, should be \$$2^n - 1 \$$ (where *n* is the number of elements in the discrete set), not \$$2^n \$$ ?