upper set operation is a closure operator

In this entry, we shall prove the assertion made in the main entry (http://planetmath.org/UpperSet) that $\uparrow$ is a closure operator. This will be done by checking that the defining properties are satisfied. To begin, recall the definition of our operation:

Definition 1.

Let $P$ be a poset and $A$ a subset of $P$. The upper set of $A$ is defined to be the set

$$\uparrow A=\{b\in P\mid (\exists a\in A)a\le b\}$$

Now, we verify each of the properties which is required of a closure operator.

Theorem 1.

$\uparrow \mathrm{\varnothing }=\mathrm{\varnothing }$

Proof.

Any statement of the form “$(\exists a\in \mathrm{\varnothing })P(a)$” is identically false no matter what the predicate $P$ (i.e. it is an antitautology) and the set of objects satsfying an identically false condition is empty, so $\uparrow \mathrm{\varnothing }=\mathrm{\varnothing }$. ∎

Theorem 2.

$A\subseteq \uparrow A$

Proof.

This follows from reflexivity — for every $a\in A$, one has $a\le a$, hence $a\in \uparrow A$. ∎

Theorem 3.

$\uparrow \uparrow A=\uparrow A$

Proof.

By the previous result, $\uparrow A\subseteq \uparrow \uparrow A$. Hence, it only remains to show that $\uparrow \uparrow A\subseteq \uparrow A$. This follows from transitivity. In order for some $a$ to be an element of $\uparrow \uparrow A$, there must exist $b$ and $c$ such that $a\ge b\ge C$ and $C\in A$. By transitivity, $A\ge C$, so $a\in \uparrow A$, hence $\uparrow \uparrow A\subseteq \uparrow A$ as well. ∎

Theorem 4.

If $A$ and $B$ are subsets of a partially ordered set, then

$$\uparrow (A\cup B)=(\uparrow A)\cup (\uparrow B)$$

Proof.

On the one hand, if $a\in \uparrow (A\cup B)$, then $a\ge b$ for some $b\in A\cup B$. It then follows that either $b\in A$ or $b\in B$. In the former case, $a\in \uparrow A$, in the latter case, $a\in \uparrow B$ so, either way $a\in (\uparrow A)\cup (\uparrow B)$. Hence $\uparrow (A\cup B)\subseteq (\uparrow A)\cup (\uparrow B)$.

On the other hand, if $a\in (\uparrow A)\cup (\uparrow B)$, then either $a\in (\uparrow A)$ or $a\in (\uparrow B)$. In the former case, there exists $b$ such that $a\ge b$ and $b\in A$. Since $A\subseteq A\cup B$, we also have $b\in A\cup B$, hence $a\in \uparrow (A\cup B)$. Likewise, in the second case, we also conclude that $a\in \uparrow (A\cup B)$. Therefore, we have $(\uparrow A)\cup (\uparrow B)\subseteq \uparrow (A\cup B)$. ∎

Theorem 5.

$\uparrow P=P$

Theorem 6.

$A\subseteq B$, $\mathrm{\uparrow }A\mathrm{\subseteq }\mathrm{\uparrow }B$

Title	upper set operation is a closure operator
Canonical name	UpperSetOperationIsAClosureOperator
Date of creation	2013-03-22 16:41:43
Last modified on	2013-03-22 16:41:43
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	8
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 06A06