Strong set order

Short description: Partial order in lattice theory

In order theory, the strong set order ${\le }_s$ is a partial order over the subsets of a lattice. It is widely used to study monotone comparative statics of parametrized optimization problems in economic theory and operations research.

The strong set order was first defined and used by Arthur F. Veinott in his unpublished lecture notes. It was later popularized by Donald M. Topkis, Paul Milgrom and Chris Shannon via their work on monotone comparative statics, in particular through Topkis' Theorem.

Definition

Given a lattice $(X,\le )$, consider the its power set ${𝒫}(X)$. The strong set order ${\le }_s$ is a partial order on ${𝒫}(X)$ given by:

$A{\le }_{s}B⟺\{\begin{array}{l}a\wedge b\in A,\\ a\vee b\in B\end{array}\mathrm{\forall }a\in A,b\in B,$

where $a\vee b$ and $a\wedge b$ are respectively the join and meet of $a,b$.

Examples and non-examples

Real numbers

Consider the real numbers $\mathbb{ℝ}$ with the usual order $\ge$. Let $A=[\underset{\_}{a},\bar{a}]$ and $B=[\underset{\_}{b},\bar{b}]$. Then

$A{\le }_{s}B⟺\underset{\_}{a}\le \underset{\_}{b}\text{ and }\bar{a}\le \bar{b}$.

More generally, for any $A,B\subseteq \mathbb{ℝ}$, we have

$A{\le }_{s}B⟺\inf A\le \inf B\text{ and }\sup A\le \sup B$.

Euclidean space

Consider the Euclidean space ${\mathbb{ℝ}}^n$ with the usual pointwise order: $\mathbf{𝐱}\le \mathbf{𝐲}⟺x_i\le y_i\mathrm{\forall }i\le n$. For $n=2$, let

$A=[0,2]\times [0,3],$

$B=[1,3]\times [1,4].$

Then :$A{\le }_{s}B$. But now consider

$B^{\prime }=[-1,3]\times [1,4]$;

Then $A{\nleqq }_s{B}^{\prime }$, since $(0,0)\in A$, $(-1,1)\in B^{\prime }$ but

$(0,0)\wedge (-1,1)=(-1,0)\notin B^{\prime }$.

Power set

Consider the power set of the natural numbers ${𝒫}(\mathbb{\mathbb{N}})$ under the set-inclusion order: $A\le B⟺A\subseteq B$. Let

$A=\{\{1\}\}$,

$B=\{\{1\},\{2\},\{1,2,3\}\}$.

It it not true that $A{\le }_{s}B$. Indeed, we have $\{1\}\in A$, $\{2\}\in B$, but

$\{1\}\wedge \{2\}=\{1\}\cap \{2\}=\varnothing \notin A,$

whence $A{\nleqq }_{s}B$.

Applications

Topkis' Theorem

The strong set order is widely used in monotone comparative statics, in particular via Topkis' Theorem. Given a lattice $X$, a poset $\mathrm{\Theta }$, a constraint correspondence $D:\mathrm{\Theta }\rightrightarrows X$ and a function $f:X\times \mathrm{\Theta }\to \mathbb{ℝ}$, the theorem gives sufficient conditions for the correspondence

$x^{*}(\theta )=\arg \underset{x\in D(\theta )}{\max }f(x,\theta )$

the be increasing in the strong set order, that is, for the statement

$\theta \ge {\theta }^{\prime }⟹x^{*}(\theta ){\ge }_s{x}^{*}({\theta }^{\prime })$

to hold.

Monotone selections

Increasigness in the strong set order can be used to obtain monotone selections from correspondences. Indeed, if $X$ is a poset and $Y$ is a lattice, the correspondence $\mathrm{\Gamma }:X\rightrightarrows Y$ is nonempty-valued and increasing in the strong set order, then a monotone selection $g$ from $\mathrm{\Gamma }$ exists if any of the following hold:

• $\mathrm{\Gamma }(x)\subseteq Y$ has a minimal element for every $x\in X$ (in particular, if $\mathrm{\Gamma }$ is complete-lattice-valued). One can thus take :$g:X\to Y$ by putting $g(x)=\min \mathrm{\Gamma }(x)$. The same works if a maximal element is available.

• $Y$ is a sublattice of a finite product of chains. This covers, for example, $Y\subseteq {\mathbb{ℝ}}^n$.

• $X$ is countable.

Zhou's Fixed-Point Theorem for correspondences

The strong set order can also be used for a generalization of Tarski's fixed-point theorem to correspondences known as Zhou's fixed-point theorem:

Theorem: let $X$ be a nonempty complete lattice and $\mathrm{\Gamma }:X\rightrightarrows X$ a nonempty-valued correspondence. If $\mathrm{\Gamma }$ is increasing int the strong set order and $\mathrm{\Gamma }(x)$ is a subcomplete sublattice for all $x\in X$, then $\mathrm{\Gamma }$ has a fixed point. Moreover, the set $\text{Fix}(\mathrm{\Gamma })$ of such fixed points is a nonempty complete lattice.

Weak set order

The strong set order if often too restrictive for some applications, in particular because it assumes that the underlying space $X$ is a lattice. A useful weaker ordering which can be used on the subsets of any poset $X$ is the weak set order ${\le }_w$, defined by:

$A{\le }_{w}B⟺\{\begin{array}{l}\mathrm{\forall }a\in A\mathrm{\exists }b\in B\text{ such that }a\le b,\text{ and }\\ \mathrm{\forall }b\in B\mathrm{\exists }a\in A\text{ such that }b\ge a.\end{array}$

This order can moreover be broken down into two weaker orders: the upper and lower weak set orders ${\le }_{uw},{\le }_{lw}$, respectively defined by:

$A{\le }_{uw}B⟺\mathrm{\forall }a\in A\mathrm{\exists }b\in B\text{ such that }a\le b,$

$A{\le }_{lw}B⟺\mathrm{\forall }b\in B\mathrm{\exists }a\in A\text{ such that }b\le a.$

Clearly $A{\le }_{w}B⟺A{\le }_{uw}B\text{ and }A{\le }_{lw}B$.

See also

• Topkis's Theorem

• Monotone comparative statics