Math 104 Assignment 1

With this, and all future assignments, you should expect to have all necessary material to complete the assignment by the end of the week when it is posted.

1. Partial orders

   Suppose that $(S, \preceq)$ is a partially ordered set; recall that for $a, b \in S$ we write $a \prec b$ if $a\preceq b$ and $a\neq b$. Let $\not\prec$ be the relation on $S$ defined by setting $a \not\prec b$ if and only if $a \prec b$ is false.

   1. Show that $\not\prec$ is not necessarily the same as $\succeq$.
   2. Prove that $\preceq$ is a total order if and only if both $\preceq$ and $\not\prec$ are partial orders.
   3. Suppose that $S$ is finite. Prove that there is a total order $\sqsubseteq$ on $S$ which extends $\preceq$, in the sense that whenever $a \preceq b$ we have $a \sqsubseteq b$ too.

2. Properties of ordered sets

   Suppose $(S, \preceq)$ is an ordered set.

   1. Prove that if $E \subseteq S$, then $\sup E$ is unique if it exists.
   2. Prove that if $e \in S$ is an upper bound for $E \subseteq S$ and $e \in E$, then $e = \sup E$.
   3. Suppose that $E \subseteq S$ is non-empty, that $x\in S$ is a lower bound for $E$, and that $y \in S$ is an upper bound for $E$. Prove that $x \preceq y$. Must it be true that $x \prec y$?
      (A word on notation: the statement "$E \subseteq S$ is non-empty" here means "$E$ is non-empty and a subset of $S$"; it does not mean "$E$ is a subset of $S$ and $S$ is non-empty".)
   4. Prove that if $E \subseteq S$ is finite and non-empty, then $\sup E$ exists in $S$ (hint: use induction). As a result, show that if $S$ is finite then it has the Least Upper Bound Property.
   5. Show that $\emptyset$ has a greatest lower bound if and only if $S$ has a maximum element. (An element $y \in S$ is the maximum of $S$ if $x \preceq y$ for every $x \in S$.)

3. Suprema depend on the ordered set

   1. Give an example of sets $E \subseteq S_1 \subseteq S_2 \subseteq S_3 \subseteq \Q$ such that $E$ has a least upper bound in $S_1$ and in $S_3$, but not in $S_2$.
   2. Prove that for any example with the properties above (not only the one you happened to write down), the least upper bound of $E$ in $S_1$ must be different from the least upper bound of $E$ in $S_3$.
   3. Does there exist an example with the above properties such that $E = S_1$? Provide an example or prove that it is impossible.

4. Some explicit extrema

   1. Prove that $\inf\set{xy \mid x, y \in \Q, 2 \lt x \lt y} = 4$.
   2. Determine which of the following extrema exist in $\Q$, and find their values. You need not supply proofs, but you should convince yourself that you could produce a proof if you were asked to do so.
      1. $\inf\set{xyz \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$
      2. $\inf\set{x - y + z \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$
      3. $\inf\set{x + y - z \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$
      4. $\sup\set{x + y - z \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$
      5. $\sup\set{x + y - 2z \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.

• An example order

  Suppose that $\mathcal{N}$ is a set with the following properties:

  1. $\emptyset \in \mathcal{N}$;
  2. if $n \in \mathcal{N}$, then $\sigma(n) := n \cup \set{n} \in \mathcal{N}$; and
  3. for any statement $P(x)$ so that $P(\emptyset)$ is true and so that for all $n \in \mathcal{N}$, $P(n)$ implies $P(\sigma(n))$, we have $P(n)$ is true for all $n \in \mathcal{N}$.
  Some elements of $\mathcal{N}$ are $$\emptyset, \set{\emptyset}, \big\{\emptyset, \set{\emptyset}\big\}, \Big\{\emptyset, \set{\emptyset}, \big\{\emptyset, \set{\emptyset}\big\}\Big\}, \bigg\{\emptyset, \set{\emptyset}, \big\{\emptyset, \set{\emptyset}\big\}, \Big\{\emptyset, \set{\emptyset}, \big\{\emptyset, \set{\emptyset}\big\}\Big\}\bigg\}, ... $$ Let $\preceq$ be a relation defined on $\mathcal{N}$ by, for $n, m \in \mathcal{N}$, setting $n \preceq m$ if and only if $n \subseteq m$ and either $n = m$ or $n \in m$. (Let us also write $n \prec m$ if $n \preceq m$ and $n \neq m$; note that this means $n \subseteq m$ and $n \in m$.) Notice that for all $n \in \mathcal{N}$, $n \prec \sigma(n)$.
  1. Prove that $\preceq$ is transitive and antisymmetric. You may assume that $\subseteq$ has these properties.
  2. Given $n \in \mathcal{N}$, let $$A(n) = \set{t \in \mathcal{N} \mid t \prec n}.$$ Prove that for all $n \in \mathcal{N}$, $A(n) = n$.
  3. Prove that $\preceq$ is total, and so an order on $\mathcal{N}$.
     Click for a hint.

     First prove that if $n \prec t$ then $\sigma(n) \preceq t$.

  The set $\mathcal{N}$ is a model of the natural numbers proposed by von Neumann (cf. Wikipedia). That is to say, $\mathcal{N}$ satisfies the Peano axioms for arithmetic, but can be defined directly from the axioms of set theory without needing to introduce any new objects.

• Ordering

  Let $\mathcal{P}$ be the set of polynomial functions from $\Q \to \Q$. Define a relation on $\mathcal{P}$ by $p \sqsubseteq q$ if and only if $p(10) \leq q(10)$. Is $\sqsubseteq$ a partial order? Is it a total order?

• Further musings on Problem 3

  1. Is there an infinite chain of sets as in 2.A.? That is, is there a sequence of sets $S_n$ so that $E \subseteq S_n \subseteq S_{n+1} \subseteq \Q$ holds for every $n \in \N$, and $E$ has a supremum in $S_n$ if and only if $n$ is odd?
  2. Is there a set $E \subseteq \Q$ so that $E$ has a supremum in $\Q$ which is different from its supremum in $\R$?

• Well-orderings

  A (total) order $\preceq$ on a set $S$ is said to be a well-order if every $T \subseteq S$ contains a minimum element.

  1. Show that every finite set admits a well-ordering.
  2. Show that the standard order on $\N$ is a well-order.
  3. Show that the standard order on $\Z$ is not a well-order.
  4. Show that $\Z$ admits a well-ordering.
  5. Show that the standard order on $\Q$ is not a well-order.
  6. Does every set admit a well-ordering?

• Division and ordering

  Recall that for $a, b \in \N$ we write $a \mid b$ if $a$ divides $b$, i.e., if there is some $k \in \N$ so that $b = ak$.

  1. Verify that $\mid$ is a partial order.

• Partial orders can be extended to orders

  Prove that any partial order may be extended to a total order, regardless of whether or not the underlying set is finite. To prove this, you may assume the following:

  Zorn's Lemma. Suppose that $Z$ is a set and $\preceq$ is a partial order on $Z$ with the property that every totally-ordered subset of $Z$ is bounded above in $Z$. Then $Z$ contains a maximal element. (A subset $W \subseteq Z$ is totally ordered if $\preceq$ restricted to $W$ is an order, i.e., if whenever $x, y \in W$ we have either $x \preceq y$ or $y \preceq x$. An element $x \in Z$ is maximal if whenever $y \in Z$ with $x \preceq y$, we have $y = x$.)