Exercise. [dt-001C]

What is the lub operator on subsets $X \subseteq \mathbb {N}$ of the poset $(\mathbb {N},\leq )$ ?

Solution.

The lub operator is maximum.

Context

Least upper bounds [dt-0016]

Liam O'Connor

Definition. Least upper bound [dt-0017]

Liam O'Connor

Let $X \subseteq Y$ be a subset of a poset $Y$ . An element $y \in Y$ is a least upper bound (or lub) for $X$ iff:

It is an upper bound: $\forall x \in X.\ x \sqsubseteq y$
It is less than any other upper bound: $\forall y' \in Y.\ (\forall x \in X. x \sqsubseteq y') \Rightarrow y \sqsubseteq y'$

It follows that lubs are unique if they exist. We write the lub of a set

X

as

\bigsqcup X

, and usually write

x \sqcup y

as a shorthand for

\bigsqcup \{x,y\}

.

Corollary. Properties of $\sqcup$ [dt-0018]

Liam O'Connor

When lubs exist, the binary $\sqcup$ operator is idempotent, commutative, and associative. Also, we have that $x \sqsubseteq y$ iff $x \sqcup y = y$ .

Theorem. Pointedness via lubs [dt-0019]

Liam O'Connor

A poset $Y$ is pointed iff $\bigsqcup \emptyset$ exists, as the lub of an empty set is just the bottom element in the poset, i.e. $\bigsqcup \emptyset = \bot$ .

Information intuition [dt-001A]

When the poset $Y$ from Definition [dt-0017] is ordered by our information ordering, the intuition of the lub $\bigsqcup X$ is that it combines all of the information content of all the elements of $X$ but it does not add any additional information (hence least).

Example. Lubs in the domain $\mathbb {B}_\bot \times \mathbb {B}_\bot$ [dt-001B]

$(\bot , \mathit {F}) \sqcup (\mathit {T},\bot ) = (\mathit {T},\mathit {F})$
$(\bot , \mathit {F}) \sqcup (\bot ,\bot ) = (\bot ,\mathit {F})$
$(\bot , \mathit {F}) \sqcup (\mathit {T}, \mathit {T})$ does not exist.

Exercise. [dt-001C]

What is the lub operator on subsets $X \subseteq \mathbb {N}$ of the poset $(\mathbb {N},\leq )$ ?

Solution.

The lub operator is maximum.

Related

Definition. Least upper bound [dt-0017]

Liam O'Connor

Let $X \subseteq Y$ be a subset of a poset $Y$ . An element $y \in Y$ is a least upper bound (or lub) for $X$ iff:

It is an upper bound: $\forall x \in X.\ x \sqsubseteq y$
It is less than any other upper bound: $\forall y' \in Y.\ (\forall x \in X. x \sqsubseteq y') \Rightarrow y \sqsubseteq y'$

It follows that lubs are unique if they exist. We write the lub of a set

X

as

\bigsqcup X

, and usually write

x \sqcup y

as a shorthand for

\bigsqcup \{x,y\}

.

Definition. Poset [dm-0004]

Liam O'Connor

A partially ordered set, or poset for short, is a pair $(X, \sqsubseteq )$ of a set $X$ equipped with a partial order $(\sqsubseteq ) \subseteq X \times X$ .

Sometimes, when the ordering is arbitrary or clear from context, the set $X$ itself may be referred to as a poset.