Sandwich Principle

Theorem

Let $A$ be a class.

Let $g: A \to A$ be a mapping on $A$ such that:

for all $x, y \in A$, either $\map g x \subseteq y$ or $y \subseteq x$.

Then:

$\forall x, y \in A: x \subseteq y \subseteq \map g x \implies x = y \lor y = \map g x$

That is, there is no element $y$ of $A$ such that:

$x \subset y \subset \map g x$

where $\subset$ denotes a proper subset.

Corollary 1

Let:

$x \subset y$

where $\subset$ denotes a proper subset.

Then:

$\map g x \subseteq y$

Corollary 2

Let $g$ be a progressing mapping.

Let $x \subseteq y$.

Then:

$\map g x \subseteq \map g y$

Proof 1

We are given that:

for all $x, y \in A$, either $\map g x \subseteq y$ or $y \subseteq x$.

Let $x, y \in A$ such that:

$x \subseteq y \subseteq \map g x$

Aiming for a contradiction, suppose both $x \subset y$ and $y \subset \map g x$.

From $x \subset y$, it follows by definition of proper subset that:

$\exists a \in y: a \notin x$

and so it is not the case that $y \subseteq x$.

From $y \subset \map g x$, it follows by definition of proper subset that:

$\exists b \in \map g x: b \notin y$

and so it is not the case that $\map g x \subseteq y$.

Hence neither $y \subseteq x$ nor $\map g x \subseteq y$.

This contradicts the property of $g$.

Hence by Proof by Contradiction it follows that $y \subset \map g x$ and $x \subset y$ cannot both be true.

Therefore either $x = y$ or $y = \map g x$.

Hence the result.

$\blacksquare$

Proof 2

We are given that:

for all $x, y \in A$, either $\map g x \subseteq y$ or $y \subseteq x$.

Let $x, y \in A$ such that:

$x \subseteq y \subseteq \map g x$

Then either we have:

$\map g x \subseteq y$ and $y \subseteq \map g x$

in which case, by definition of set equality:

$y = \map g x$

or we have that:

$x \subseteq y$ and $y \subseteq x$

in which case, by definition of set equality:

$x = y$

Thus either $y = \map g x$ or $x = y$ and the result follows.

$\blacksquare$

Also see

• Sandwich Theorem or Sandwich Rule in the context of real analysis, also known as the Squeeze Theorem (preferred on $\mathsf{Pr} \infty \mathsf{fWiki}$)

Linguistic Note

The name Sandwich Principle for this lemma appears to have been coined by Raymond M. Smullyan and Melvin Fitting in their Set Theory and the Continuum Problem, revised ed.

As they explain, when $x \subset y \subset z$, we may consider $y$ to be sandwiched between $x$ and $z$.

Thus the Sandwich Principle tells us that, given the conditions constraining $x$, $y$ and $\map g x$, there can be no such $y$ sandwiched between $x$ and $\map g x$.

Sources

• 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $3$: The Natural Numbers: $\S 4$ A double induction principle and its applications: Lemma $4.9 \ (1)$