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

- All Categories 2.4K
- Chat 502
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 73
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 718

Options

## Comments

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.

`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.`

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

`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`

\(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.

`\\(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.`

Is a key insight for this proof, that the upper set

U,cancontain elements that cannot be compared to the smallest element inU?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.

`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.`

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.

`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.`

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:

with this case of incomparable members.

`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.`

Not exactly.

It means "generated by just one element".

We say \(U\) is the

principal upper setof \(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\}\).

`> 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\\}\\).`

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

On the discrete preorder,

nothing is ever bigger. So this condition is vacuously true, always.`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.`

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

notbigger than x -- then that set isnotan 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

nis the number of elements in the discrete set), not \(2^n \) ?`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 \\) ?`