Equinumerous Ordering

We have used the concept of equinumerosity to tell when two sets A and B are the same size, now we will define what it means for a set B to be larger than A.

Definition

A set A is dominated by a set B (written A \preceq B) if there exists C such that A \approx C and C \subseteq B.

We may also say A is less then or equal to B, like we would for standard numbers.

Example

Let A = \{1,2\} and B = \{3,4,5\}. Then there exists a subset C = \{3,4\} \subseteq B such that A \approx C under the function

f = \{(1,3),(2,4)\}.

Therefore we say A is dominated by B, or A \preceq B.

The following properties naturally follow from the definition.

Theorem

Let A,B,C be sets, then

(a) If A \approx B, then A \preceq B.

(b) If A \subseteq B, then A \preceq B.

(c) If A \preceq B and B \preceq C then A \preceq C.

(a)

Since B is a subset of itself, and we have A \approx B by our hypothesis, we have that A \preceq B.


(b)

By the reflexivity of equinumerosity, we have A \approx A. Since A is a subset of B by our hypothesis, we have A \preceq B.


(c)

Since B \preceq C there exists E \subseteq C and g \colon B \to E such that B \approx E, similarly since A \preceq B, there exists D \subseteq B and f \colon A \to D such that A \approx D.

Let F = g(D) and h be the restriction of g to the domain D, that is

h \colon D \to g(D).

Since g is bijective, its restrictions are bijective. Then A \approx F under {h \circ f}. Since F is a subset of C, we have A \preceq F.

The proof for part (c)