Order

The relations $\le$ on the numbers, $\subseteq$ on sets and "divides" on the positive integers do not sort things into groups of equals; they rank them, and ranking needs its own definitions of what comes first, what sits on top, and when a collection has a top at all.

The previous lesson picked out the equivalence relations, those that are reflexive (every element is related to itself), symmetric (a relation one way gives it the other way) and transitive (related along a chain means related end to end), and showed that they group things. This lesson turns to the relations that rank. It assumes relations as sets of pairs, power sets, the quantifiers, and divisibility: $a\mid b$ when $b=ak$ for some integer $k$. As throughout the course, $\mathbb{N}=\{1,2,3,\dots \}$.

Antisymmetry

An order cannot be symmetric: if $x\le y$ forced $y\le x$, then $1\le 2$ would give $2\le 1$. What an order has instead is that two things each ranked below the other are the same thing. A relation $⪯$ on a set $A$ is antisymmetric when

The symbol $⪯$ stands for an abstract relation of this kind, read "precedes or equals"; $\le$ is kept for numbers.

Antisymmetric is not the negation of symmetric. Equality is both, since whenever $a=b$ and $b=a$, certainly $a=b$. And "$x+y$ is even" on $\mathbb{Z}$ is symmetric without being antisymmetric, since it relates $1$ and $3$ both ways.

To prove antisymmetry, take arbitrary $a$ and $b$, assume both $a⪯b$ and $b⪯a$, and deduce $a=b$. To refute it, exhibit two different elements related both ways.

Partial orders

A relation on $A$ that is reflexive, antisymmetric and transitive is a partial order, and $A$ with it is a partially ordered set, or poset. Three examples carry the lesson.

The first is $\le$ on $ℝ$, with the ordering facts of school algebra taken as known. Reflexivity is $x\le x$. For antisymmetry, suppose $x\le y$ and $y\le x$; if $x\ne y$ then $x<y$ and $y<x$, and adding gives $x+y<y+x$, which is false, so $x=y$. For transitivity, $x\le y$ and $y\le z$ mean $y-x\ge 0$ and $z-y\ge 0$, and adding gives $z-x\ge 0$.

Example. Let $X$ be a set. Prove that $\subseteq$ is a partial order on the power set $\mathcal{P}(X)$, the set of all subsets of $X$.

Reflexive: for every $A\in \mathcal{P}(X)$, every element of $A$ is an element of $A$, so $A\subseteq A$. Antisymmetric: let $A\subseteq B$ and $B\subseteq A$. Each set is a subset of the other, which is exactly the double inclusion that proves two sets equal, so $A=B$. Transitive: let $A\subseteq B$ and $B\subseteq C$, and let $x\in A$. Since $A\subseteq B$, $x\in B$, and since $B\subseteq C$, $x\in C$. As $x$ was arbitrary, $A\subseteq C$. All three properties hold, so $\subseteq$ is a partial order on $\mathcal{P}(X)$.

Now you. Prove that divisibility is a partial order on $\mathbb{N}$.

The positivity is doing real work. On $\mathbb{Z}$, divisibility is still reflexive and transitive, but $2\mid -2$ since $-2=2\cdot (-1)$, and $-2\mid 2$ since $2=(-2)(-1)$, while $2\ne -2$. The broken step is the last: $km=1$ also has the integer solution $k=m=-1$. So divisibility is not a partial order on $\mathbb{Z}$.

Total orders and strict orders

Two elements $a$ and $b$ of a poset are comparable when $a⪯b$ or $b⪯a$. A partial order in which every pair is comparable is a total order, or linear order, because its elements line up in a single row. The order $\le$ on $ℝ$ is total: for any two reals, either $x\le y$ or $y\le x$.

The other two examples are not. Neither of $2$ and $3$ divides the other, so they are incomparable under divisibility, and so are $4$ and $6$. In $\mathcal{P}(\{1,2\})$ the sets $\{1\}$ and $\{2\}$ are incomparable, since neither is a subset of the other. This is what "partial" means: the order ranks some pairs and is silent about others.

Each partial order has a strict version: $a\prec b$ means $a⪯b$ and $a\ne b$, which turns $\le$ into $<$, $\subseteq$ into "is a proper subset of", and divisibility into "divides and is different from".

Hasse diagrams

A finite poset can be drawn economically, leaving reflexivity and transitivity for the reader to fill in. Say that $b$ covers $a$ when $a\prec b$ and there is no $c$ with $a\prec c\prec b$. The Hasse diagram puts each element as a point, places $b$ higher on the page than $a$ whenever $a\prec b$, and draws a line only for covering pairs. Then $a⪯b$ exactly when $a=b$ or a path climbs from $a$ to $b$.

Take the eight divisors of $30$, namely $1,2,3,5,6,10,15,30$, under divisibility. The number $1$ is covered by the primes $2$, $3$ and $5$. Then $2$ is covered by $6$ and $10$, $3$ by $6$ and $15$, and $5$ by $10$ and $15$. Finally $6$, $10$ and $15$ are each covered by $30$. That is twelve lines, drawn as the edges of a cube standing on the corner $1$, with $30$ at the opposite corner. The poset has nineteen strict pairs in all (for instance $2\prec 30$), but the other seven follow by climbing.

The cube is no accident. A divisor of $30$ is a product of some of the primes $2$, $3$ and $5$, and $a\mid b$ exactly when the primes of $a$ are among those of $b$. So the divisors of $30$ under divisibility have the same diagram as $\mathcal{P}(\{2,3,5\})$ under $\subseteq$.

The divisors of $12$ give a different shape. They are $1,2,3,4,6,12$. Here $1$ is covered by $2$ and $3$; $2$ is covered by $4$ and $6$; $3$ by $6$; and $4$ and $6$ are covered by $12$. Note that $12$ does not cover $2$, because $4$ and $6$ lie between. Those seven lines draw two squares sharing an edge, from $2$ to $6$, rather than a cube.

Maximal against greatest

"Top" has two meanings in a poset, and they come apart as soon as the order is not total. An element $g$ of $A$ is greatest when everything lies below it: $a⪯g$ for every $a\in A$. An element $m$ is maximal when nothing lies strictly above it: there is no $a\in A$ with $m\prec a$. Least and minimal are the same definitions turned upside down.

Take the divisors of $12$ other than $12$, the set $\{1,2,3,4,6\}$ under divisibility. Nothing in it is a proper multiple of $4$ or of $6$, so both are maximal. Neither is greatest, since neither divides the other, and nothing else could be, since a greatest element would be a multiple of both. So there are two maximal elements and no greatest. At the bottom, $1$ divides everything and is least. In a Hasse diagram the maximal elements are the points with no line going up.

Greatest is a statement about every element; maximal is a statement about none. That is why a greatest element is always maximal (anything above it would also be below it, and antisymmetry makes the two equal), while a maximal element may simply be incomparable with the rest. In a total order every pair is comparable, and the two notions coincide.

Infinite posets can lack both: under $\le$, $\mathbb{N}$ has no maximal element, since $n<n+1$.

Example. Prove that a poset has at most one greatest element.

Let $g$ and $g^{\prime }$ both be greatest elements of $A$. Since $g$ is greatest and $g^{\prime }\in A$, we have $g^{\prime }⪯g$. Since $g^{\prime }$ is greatest and $g\in A$, we have $g⪯g^{\prime }$. By antisymmetry, $g=g^{\prime }$.

Antisymmetry supplies the equality, and it is why one may speak of "the greatest element", written $\max A$ when it exists.

Now you. Prove that if a poset $A$ has a greatest element $g$, then $g$ is the only maximal element of $A$.

The poset $\{1,2,3,4,6\}$ is the contrapositive at work: it has two maximal elements, so it cannot have a greatest one.

Upper bounds and the least upper bound

Maximal and greatest look inside a set. Bounds look at it from outside, within a larger poset. Let $S$ be a subset of a poset $A$. An element $u\in A$ is an upper bound of $S$ when $s⪯u$ for every $s\in S$, and $S$ is bounded above when it has one. Lower bounds are defined the other way up. An upper bound need not belong to $S$: in $ℝ$, the upper bounds of $[0,1)$ are exactly the numbers $u\ge 1$, and none of them is in the set.

Among the upper bounds, the one that matters is the lowest. An element $u$ is the least upper bound, or supremum, of $S$, written $\sup S$, when two conditions hold:

Condition (i) says $u$ is an upper bound; condition (ii) says it lies below every other one. Together they say $u$ is the least element of the set of upper bounds, so by the upside-down version of the Example above there is at most one, and "the" is earned. The greatest lower bound, or infimum, $\inf S$, is defined the other way up.

The definition works in any poset. Under divisibility on $\mathbb{N}$ the upper bounds of $\{4,6\}$ are the common multiples, and each is a multiple of $12$ (if $n=6b$ and $4\mid 6b$, then $3b$ is even, so $b$ is even). So $\sup \{4,6\}=12$, the least common multiple. Under $\subseteq$, $\sup \{A,B\}=A\cup B$, since any set containing $A$ and $B$ contains their union.

In $ℝ$, where $\le$ is total, condition (ii) has a working form: no number below $u$ is an upper bound, that is, for every $b<u$ some $s\in S$ has $s>b$. If $\sup S$ belongs to $S$, it is the greatest element: $\sup [0,1]=1=\max [0,1]$. But it need not belong.

Example. Prove that $S=\{1-\frac{1}{n}:n\in \mathbb{N}\}$ has $\sup S=1$, and that $1\notin S$.

The set is $\{0,\frac{1}{2},\frac{2}{3},\frac{3}{4},\dots \}$. For (i), each element satisfies $1-\frac{1}{n}<1$ because $\frac{1}{n}>0$, so $1$ is an upper bound. For (ii), let $b<1$; we show $b$ is not an upper bound. Since $1-b>0$, choose a natural number $n>\frac{1}{1-b}$, which exists because $\mathbb{N}$ has no upper bound in $ℝ$, a fact a later lesson proves. Then $\frac{1}{n}<1-b$, so $1-\frac{1}{n}>b$, and an element of $S$ lies above $b$. Every upper bound is therefore at least $1$, and $\sup S=1$. Finally $1-\frac{1}{n}=1$ would force $\frac{1}{n}=0$, which no $n$ allows, so $1\notin S$, and $S$ has a supremum but no greatest element.

Now you. Prove that $\sup (0,1)=1$ without using any fact about $\mathbb{N}$.

A supremum can also fail to exist. The empty set has every real as an upper bound and so no least one, and $\mathbb{N}$ has no upper bound in $ℝ$ at all.

A gap in the rationals

Whether a least upper bound exists depends on the poset the bounds are drawn from, just as surjectivity depended on the codomain. Work in $\mathbb{Q}$ under $\le$, and let

The set is nonempty, since $1\in T$, and bounded above in $\mathbb{Q}$ by $2$, since a rational $q>2$ has $q^2>4$. In fact any positive rational $u$ with $u^2>2$ is an upper bound: if some $q\in T$ had $q>u$, then $q^2>u^2>2$, contradicting $q\in T$.

So the rational upper bounds can be pushed down, and the elements of $T$ pushed up. The decimals $1.5$, $1.42$, $1.415$ and $1.4143$ have squares $2.25$, $2.0164$, $2.002225$ and $2.00024449$, all above $2$, so each is an upper bound. The decimals $1.4$, $1.41$, $1.414$ and $1.4142$ have squares $1.96$, $1.9881$, $1.999396$ and $1.99996164$, all below $2$, so each is in $T$. The two sides close in on a number whose square is $2$, and an earlier lesson proved that no rational has square $2$.

That suggests a fact, stated here and proved in a later lesson: $T$ is nonempty and bounded above in $\mathbb{Q}$, yet has no least upper bound in $\mathbb{Q}$, because below every rational upper bound lies a smaller one. Inside $ℝ$ the same set has supremum $\sqrt{2}$. The rationals are totally ordered, as the reals are, yet something the reals have is missing from them, and least upper bounds are where the absence shows.

Whether every nonempty set of reals bounded above has a least upper bound is a question about what sets of real numbers look like, and it is where the course is heading. A prior question comes first: how many real numbers are there? Both $\mathbb{Q}$ and $ℝ$ are infinite, and it is not yet clear that one infinity can be larger than another. The next lesson settles it by comparing the sizes of infinite sets.