We proved this result in the section on sets. To review, recall that for $A,B\in \mathcal{P}(S)$, $A\subseteq B$ means that $x\in A$ implies $x\in B$. Also $A=B$ means that $x\in A$ if and only if $x\in B$. Thus

1. $A\subseteq A$
2. $A\subseteq B$ and $B\subseteq A$ if and only if $A=B$
3. $A\subseteq B$ and $B\subseteq C$ imply $A\subseteq C$

1. Clearly $n\mid n$ for $n\in {\mathbb{N}}_{+}$, since $n=1\cdot n$, so $\mid$ is reflexive. Suppose $m\mid n$ and $n\mid m$, where $m,n\in {\mathbb{N}}_{+}$. Then there exist $j,k\in {\mathbb{N}}_{+}$ such that $n=km$ and $m=jn$. Substituting gives $n=jkn$, and hence $j=k=1$. Thus $m=n$ so $\mid$ is antisymmetric. Finally, suppose $m\mid n$ and $n\mid p$, where $m,n,p\in {\mathbb{N}}_{+}$. Then there exists $j,k\in {\mathbb{N}}_{+}$ such that $n=jm$ and $p=kn$. Substituting gives $p=jkm$, so $m\mid p$. Thus $\mid$ is transitive.
2. If $m,n\in {\mathbb{N}}_{+}$ and $m\mid n$, then there exists $k\in {\mathbb{N}}_{+}$ such that $n=km$. Since $k\ge 1$, $m\le n$.

Suppose that $f,g,h\in \mathcal{S}$.

1. $f(x){⪯}_{T}f(x)$ for all $x\in S$, so $f⪯f$.
2. If $f⪯g$ and $g⪯f$ then $f(x){⪯}_{T}g(x)$ and $g(x){⪯}_{T}f(x)$ for all $x\in S$. Hence $f(x)=g(x)$ for all $x\in S$ so $f=g$.
3. If $f⪯g$ and $g⪯h$ then $f(x){⪯}_{T}g(x)$ and $g(x){⪯}_{T}h(x)$ for all $x\in S$. Hence $f(x){⪯}_{T}h(x)$ for all $x\in S$ so $f⪯h$.

Clearly the reflexive, antisymmetric and transitive properties hold for $⪰$.

The reflexive, antisymmetric, and transitive properties given above hold for all $x,y,z\in S$ and hence hold for all $x,y,z\in A$.

Suppose that $⪯$ is a partial order on $S$. Recall that $\prec$ is defined by $x\prec y$ if and only if $x⪯y$ and $x\ne y$. If $x\prec y$ and $y\prec z$ then $x⪯y$ and $y⪯z$, and so $x⪯z$. On the other hand, if $x=z$ then $x⪯y$ and $y⪯x$ so $x=y$, a contradiction. Hence $x\ne z$ and so $x\prec z$. Therefore $\prec$ is transitive. If $x\prec y$ then $x\ne y$ by definition, so $\prec$ is irreflexive.

Conversely, suppose that $\prec$ is a transitive and irreflexive relation on $S$. Recall that $⪯$ is defined by $x⪯y$ if and only if $x\prec y$ or $x=y$. By definition then, $⪯$ is reflexive: $x⪯x$ for every $x\in S$. Next, suppose that $x⪯y$ and $y⪯x$. If $x\prec y$ and $y\prec x$ then $x\prec x$ by the transitive property of $\prec$. But this is a contradiction by the irreflexive property, so we must have $x=y$. Thus $⪯$ is antisymmetric. Suppose $x⪯y$ and $y⪯z$. There are four cases:

1. If $x\prec y$ and $y\prec z$ then $x\prec z$ by the transitive property of $\prec$.
2. If $x=y$ and $y\prec z$ then $x\prec z$ by substitution.
3. If $x\prec y$ and $y=z$ then $x\prec z$ by substitution.
4. If $x=y$ and $y=z$ then $x=z$ by the transitive property of $=$.

In all cases we have $x⪯z$ so $⪯$ is transitive. Hence $⪯$ is a partial order on $S$.

1. $A$ is increasing if and only if $x\in A$ and $x⪯y$ implies $y\in A$ if and only if ${\mathbf{1}}_A(x)=1$ and $x\le y$ implies ${\mathbf{1}}_A(y)=1$ if and only if ${\mathbf{1}}_A$ is increasing.
2. $A$ is decreasing if and only if $y\in A$ and $x⪯y$ implies $x\in A$ if and only if ${\mathbf{1}}_A(y)=1$ and $x\le y$ implies ${\mathbf{1}}_A(x)=1$ if and only if ${\mathbf{1}}_A$ is decreasing.

We need to show that for $x,y\in S$, $x{\prec }_{S}y$ if and only if $f(x){\prec }_{T}f(y)$. If $x{\prec }_{S}y$ then by definition, $f(x){⪯}_{T}f(y)$. But if $f(x)=f(y)$ then $x=y$ since $f$ is one-to-one. This is a contradiction, so $f(x){\prec }_{T}f(y)$. Similarly, if $f(x){\prec }_{T}f(y)$ then by definition, $x{⪯}_{S}y$. But if $x=y$ then $f(x)=f(y)$, a contradiction. Hence $x{\prec }_{S}y$.

For each $x\in S$, let $A_x=\{u\in S:u⪯x\}$, and then let $\mathcal{S}=\{A_x:x\in S\}$, so that $\mathcal{S}\subseteq \mathcal{P}(S)$. We will show that the function $x\mapsto A_x$ from $S$ onto $\mathcal{S}$ is one-to-one, and satisfies $$x⪯y⟺A_x\subseteq A_y$$ First, suppose that $x,y\in S$ and $A_x=A_y$. Then $x\in A_x$ so $x\in A_y$ and hence $x⪯y$. Similarly, $y\in A_y$ so $y\in A_x$ and hence $y⪯x$. Thus $x=y$, so the mapping is one-to-one. Next, suppose that $x⪯y$. If $u\in A_x$ then $u⪯x$ so $u⪯y$ by the transitive property, and hence $u\in A_y$. Thus $A_x\subseteq A_y$. Conversely, suppose $A_x\subseteq A_y$. As before, $x\in A_x$, so $x\in A_y$ and hence $x⪯y$.

Suppose that $a,b$ are minimum elements of $A$. Since $a,b\in A$ we have $a⪯b$ and $b⪯a$, so $a=b$ by the antisymmetric property. The proof for the maximum element is analogous.

1. First, $\bigcap \mathcal{A}\subseteq A$ for every $A\in \mathcal{A}$ and hence $\bigcap \mathcal{A}$ is a lower bound of $\mathcal{A}$. If $B$ is a lower bound of $\mathcal{A}$ then $B\subseteq A$ for every $A\in \mathcal{A}$ and hence $B\subseteq \bigcap \mathcal{A}$. Therefore $\bigcap \mathcal{A}$ is the greatest lower bound.
2. First, $A\subseteq \bigcup \mathcal{A}$ for every $A\in \mathcal{A}$ and hence $\bigcup \mathcal{A}$ is an upper bound of $\mathcal{A}$. If $B$ is an upper bound of $\mathcal{A}$ then $A\subseteq B$ for every $A\in \mathcal{A}$ and hence $\bigcup \mathcal{A}\subseteq B$. Therefore $\bigcup \mathcal{A}$ is the least upper bound.

Let $A=\{x\in S:x⪯f(x)\}$ and let $z=sup(A)$. If $x\in A$ then $x⪯z$ so $x⪯f(x)⪯f(z)$. Hence $f(z)$ is an upper bound of $A$ so $z⪯f(z)$. But then $f(z)⪯f(f(z))$ so $f(z)\in A$. Hence $f(z)⪯z$. Therefore $f(z)=z$.

Note that the hypotheses of the theorem require that $sup(\mathrm{\varnothing })=min(S)$ exists. The set $A=\{x\in S:x⪯f(x)\}$ is nonempty since $min(S)\in A$.

1. If $(x,y)\in S\times T$ then $x{⪯}_{S}x$ and $y{⪯}_{T}y$ and therefore $(x,y)⪯(x,y)$. Hence $⪯$ is reflexive. Suppose that $(u,v),(x,y)\in S\times T$ and that $(u,v)⪯(x,y)$ and $(x,y)⪯(u,v)$. Then $u{⪯}_{S}x$ and $x{⪯}_{S}u$, and $v{⪯}_{T}y$ and $y{⪯}_{T}v$. Hence $u=x$ and $v=y$, so $(u,v)=(x,y)$. Hence $⪯$ is antisymmetric. Finally, suppose that $(u,v),(x,y),(z,w)\in S\times T$, and that $(u,v)⪯(x,y)$ and $(x,y)⪯(z,w)$. Then $u{⪯}_{S}x$ and $x{⪯}_{S}z$, and $v{⪯}_{T}y$ and $y{⪯}_{T}w$. Hence $u{⪯}_{S}z$ and $v{⪯}_{S}w$, and therefore $(u,v)⪯(z,w)$. Hence $⪯$ is transitive.
2. Suppose that $(S,{⪯}_S)=(T,{⪯}_T)$, and that $x,y\in S$ are distinct. If $(x,y)⪯(y,x)$ then $x{⪯}_{S}y$ and $y{⪯}_{S}x$ and hence $x=y$, a contradiction. Similarly $(y,x)⪯(x,y)$ leads to the same contradiction $x=y$. Hence $(x,y)$ and $(y,x)$ are unrelated in the partial order $⪯$.

In spite of the abstraction, the proof is perfectly straightforward. Suppose that $x,y,z\in \prod _{i\in I}{S}_i$.

1. $x_i{⪯}_i{x}_i$ for every $i\in I$, and hence $x⪯x$. Thus $⪯$ is reflexive.
2. Suppose that $x⪯y$ and $y⪯x$. Then $x_i{⪯}_i{y}_i$ and $y_i{⪯}_i{x}_i$ for each $i\in I$. Hence $x_i=y_i$ for each $i\in I$ and so $x=y$. Thus $⪯$ is antisymmetric
3. Suppose that $x⪯y$ and $y⪯z$. Then $x_i{⪯}_i{y}_i$ and $y_i{⪯}_i{z}_i$ for each $i\in I$. Hence $x_i{⪯}_i{z}_i$ for each $i\in I$, so $x⪯z$. Thus $⪯$ is transitive.

1. If $(x,y)\in S\times T$, then $x=x$ and $y{⪯}_{T}y$. Hence $(x,y)⪯(x,y)$ and so $⪯$ is reflexive. Suppose that $(u,v),(x,y)\in S\times T$, and that $(u,v)⪯(x,y)$ and $(x,y)⪯(u,v)$. There are four cases, but only one can actually happen.
   • If $u{\prec }_{S}x$ and $x{\prec }_{S}u$ then $u{\prec }_{S}u$. This is a contradiction since ${\prec }_S$ is irreflexive, and so this case cannot happen.
   • If $u{\prec }_{S}x$, $x=u$, and $y{⪯}_{T}v$, then $u{\prec }_{S}u$. This case also cannot happen.
   • If $u=x$, $v{⪯}_{T}y$, and $x{\prec }_{S}u$, then $u{\prec }_{S}u$. This case also cannot happen
   • if $u=x$, $v{⪯}_{T}y$, $x=u$, and $y{⪯}_{T}v$, then $u=x$ and $v=y$, so $(u,v)=(x,y)$.
   Hence $⪯$ is antisymmetric. Finally, suppose that $(u,v),(x,y),(z,w)\in S\times T$ and that $(u,v)⪯(x,y)$ and $(x,y)⪯(z,w)$. Again there are four cases:
   • If $u{\prec }_{S}x$ and $x{\prec }_{S}z$ then $u{\prec }_{S}z$, and hence $(u,v)⪯(z,w)$.
   • If $u{\prec }_{S}x$, $x=z$, and $y{⪯}_{T}w$ then $u{\prec }_{S}z$ and hence $(u,v)⪯(z,w)$.
   • If $u=x$, $v{⪯}_{T}y$, and $x{\prec }_{S}z$ then $u{\prec }_{S}z$ and hence $(u,v)⪯(z,w)$.
   • If $u=x$, $v{⪯}_{T}y$, $x=z$, and $y{⪯}_{T}w$, then $u=z$ and $v{⪯}_{T}w$, and hence $(u,v)⪯(z,w)$.
   Therefore $⪯$ is transitive.
2. Suppose that ${⪯}_S$ and ${⪯}_T$ are total orders. Let $(u,v),(x,y)\in S\times T$. Then either $u{⪯}_{S}x$ or $x{⪯}_{S}u$ and either $v{⪯}_{T}y$ or $y{⪯}_{T}v$. Again there are four cases
   • If $u{\prec }_{S}x$ then $(u,v)⪯(x,y)$
   • If $x{\prec }_{S}u$ then $(x,y)⪯(u,v)$
   • If $u=x$ and $v{⪯}_{T}y$ then $(u,v)⪯(x,y)$
   • If $u=x$ and $y{⪯}_{T}v$ then $(x,y)⪯(u,v)$
   Hence $⪯$ is a total order.

1. By [12], we need to show that $\prec$ is irreflexive and transitive. First, no $x\in \prod _{i\in I}{S}_i$ satisfies $x\prec x$ since $x_i=x_i$ for all $i\in I$. Hence $\prec$ is irreflexive. Next, suppose that $x,y,z\in \prod _{i\in I}{S}_i$ and that $x\prec y$ and $y\prec z$. Then there exists $j\in I$ such that $x_i=y_i$ if $i<j$ and $x_j{\prec }_j{y}_j$. Similarly, there exists $k\in I$ such that $y_i=z_i$ if $i<k$ and $y_k{\prec }_k{z}_k$. Again, since $I$ is totally ordered, either $j<k$ or $k<j$ or $j=k$. If $j<k$, then $x_i=y_i=z_i$ if $i<j$ and $x_j{\prec }_j{y}_j=z_j$. If $k<j$, then $x_i=y_i=z_i$ if $i<k$ and $x_k=y_k{\prec }_k{z}_k$. If $j=k$, then $x_i=y_i=z_i$ if $i<j$ and $x_j{\prec }_j{y}_j{\prec }_j{z}_j$. In all cases, $x\prec z$ so $\prec$ is transitive.
2. Suppose now that ${⪯}_i$ is a total order on $S_i$ for each $i\in I$ and that $I$ is well ordered by $\le$. Let $x,y\in \prod _{i\in I}{S}_i$ with $x\ne y$. Let $J=\{i\in I:x_i\ne y_i\}$. Then $J\ne \mathrm{\varnothing }$ by assumption, and hence has a minimum element $j$. If $i<j$ then $i\notin J$ and hence $x_i=y_i$. On the other hand, $x_j\ne y_j$ since $j\in J$ and therefore, since ${⪯}_j$ is totally ordered, we must have either $x_j{\prec }_j{y}_j$ or $y_j{\prec }_j{x}_j$. In the first case, $x\prec y$ and in the second case $y\prec x$. Hence $⪯$ is totally ordered.

Every $x\in \mathbb{R}$ can be uniquely expressed in the form $x=n+t$ where $n=\lfloor x\rfloor \in \mathbb{Z}$ is the integer part and $t=x-n\in [0,1)$ is the remainder. Thus $x\mapsto (n,t)$ is a one-to-one function from $\mathbb{R}$ onto $\mathbb{Z}\times [0,1)$. For example, $5.3$ maps to $(5,0.3)$, while $-6.7$ maps to $(-7,0.3)$. Suppose that $x=m+s,y=n+t\in \mathbb{R}$, where of course $m,n\in \mathbb{Z}$ are the integer parts of $x$ and $y$, respectively, and $s,t\in [0,1)$ are the corresponding remainders. Then $x<y$ if and only if $m<n$ or $m=n$ and $s<t$. Again, to illustrate with real real numbers, we can tell that $5.3<7.8$ just by comparing the integer parts: $5<7$. We can ignore the remainders. On the other hand, to see that $6.4<6.7$ we need to compare the remainders: $0.4<0.7$ since the integer parts are the same.

To show that $\mathcal{U}$ is a subspace, we just have to note that it is closed under addition and scalar multiplication. That is, if $f,g:S\to \mathbb{R}$ are bounded, and if $c\in \mathbb{R}$, then $f+g$ and $cf$ are bounded. Next we show that $\parallel \cdot \parallel$ satisfies the axioms of a norm. Again, let $f,g\in \mathcal{U}$ and $c\in \mathbb{R}$

1. Clearly $\parallel f\parallel \ge 0$ and $\parallel f\parallel =0$ if and only if $f(x)=0$ for all $x\in S$ if and only if $f=\mathbf{0}$, the zero function on $S$.
2. $\parallel cf\parallel =sup\{|cf(x)|:x\in S\}=\left|c\right|sup\{|f(x)|:x\in S\}=\left|c\right|\parallel f\parallel$
3. By the usual triangle inequality on $\mathbb{R}$, $|f(x)+g(x)|\le |f(x)|+|g(x)|$ for $x\in S$. Hence $$sup\{|f(x)+g(x)|:x\in S\}\le sup\{|f(x)|+|g(x)|:x\in S\}\le sup\{|f(x)|:x\in S\}+sup\{|g(x)|:x\in S\}$$ That is, $\parallel f+g\parallel \le \parallel f\parallel +\parallel g\parallel$.

Recall that part (a) is the positive property, part (b) is the scaling property, and part (c) is the triangle inequality.

1. $\{a\}$
2. $\mathrm{\varnothing }$
3. $a$
4. Does not exist
5. $(-\mathrm{\infty },a]$
6. $[b,\mathrm{\infty })$
7. $a$
8. $b$

1. $\{2,3\}$
2. $\{12\}$
3. Does not exist
4. $12$
5. $\{1\}$
6. $\{12,24,36,\dots \}$
7. $1$
8. $12$

1. $\mathcal{P}(S)=\{\mathrm{\varnothing },\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},S\}$
2. For $A\in \mathcal{P}(S)$ and $x\in S\setminus A$, there is a directed edge from $A$ to $A\cup \{x\}$

Note that the covering graph of $\supseteq$ looks the same as the graph of $\subseteq$, except for the labels on the vertices. This symmetry is because of the complement relationship.

1. $\mathcal{P}(S)=\{\mathrm{\varnothing },\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,b,c\},\{a,b,d\},\{a,c,d\},\{b,c,d\},S\}$
2. For $A\in \mathcal{P}(S)$ and $x\in S\setminus A$, there is a directed edge from $A$ to $A\cup \{x\}$

Note again that the covering graph of $\supseteq$ looks the same as the graph of $\subseteq$, except for the labels on the vertices. This symmetry is because the complement relationship.

Let $a=A\cap B$, $b=A\cap B^c$, $c=A^c\cap B$, $d=A^c\cap B^c$. Our basic assumption is that $A$ and $B$ are in general position, so that $a,b,c,d$ are distinct and nonempty. Note also that $\{a,b,c,d\}$ partitions $S$. Now, map each subset $\mathcal{S}$ of $\{a,b,c,d\}$ to $\bigcup \mathcal{S}$. This function is an isomorphism from $\mathcal{S}$ to $\mathcal{A}$. That is, for $\mathcal{S}$ and $\mathcal{T}$ subsets of $\{a,b,c,d\}$, $\mathcal{S}\subseteq \mathcal{T}$ if and only if $\bigcup \mathcal{S}\subseteq \bigcup \mathcal{T}$.