Ian Charlesworth | Teaching | Math 104

$$ \newcommand{\cis}{\operatorname{cis}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\paren}[1]{\left(#1\right)} \newcommand{\sq}[1]{\left[#1\right]} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \newcommand{\set}[1]{\left\{#1\right\}} \newcommand{\ang}[1]{\left\langle#1\right\rangle} \newcommand{\floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{\ceil}[1]{\left\lceil#1\right\rceil} \newcommand{\C}{\mathbb{C}} \newcommand{\D}{\mathbb{D}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\F}{\mathbb{F}} \newcommand{\T}{\mathbb{T}} \renewcommand{\S}{\mathbb{S}} \newcommand{\intr}{{\large\circ}} \newcommand{\limni}[1][n]{\lim_{#1\to\infty}} \renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cJ}{\mathcal{J}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cT}{\mathcal{T}} \newcommand{\cU}{\mathcal{U}} \newcommand{\cV}{\mathcal{V}} \newcommand{\cW}{\mathcal{W}} \newcommand{\cX}{\mathcal{X}} \newcommand{\cY}{\mathcal{Y}} \newcommand{\cZ}{\mathcal{Z}} \newcommand{\bA}{\mathbb{A}} \newcommand{\bB}{\mathbb{B}} \newcommand{\bC}{\mathbb{C}} \newcommand{\bD}{\mathbb{D}} \newcommand{\bE}{\mathbb{E}} \newcommand{\bF}{\mathbb{F}} \newcommand{\bG}{\mathbb{G}} \newcommand{\bH}{\mathbb{H}} \newcommand{\bI}{\mathbb{I}} \newcommand{\bJ}{\mathbb{J}} \newcommand{\bK}{\mathbb{K}} \newcommand{\bL}{\mathbb{L}} \newcommand{\bM}{\mathbb{M}} \newcommand{\bN}{\mathbb{N}} \newcommand{\bO}{\mathbb{O}} \newcommand{\bP}{\mathbb{P}} \newcommand{\bQ}{\mathbb{Q}} \newcommand{\bR}{\mathbb{R}} \newcommand{\bS}{\mathbb{S}} \newcommand{\bT}{\mathbb{T}} \newcommand{\bU}{\mathbb{U}} \newcommand{\bV}{\mathbb{V}} \newcommand{\bW}{\mathbb{W}} \newcommand{\bX}{\mathbb{X}} \newcommand{\bY}{\mathbb{Y}} \newcommand{\bZ}{\mathbb{Z}} $$

Due: September 4th, 2020

Math 104 Assignment 1

With this, and all future assignments, you should expect to have all necessary material to complete the assignment no later than the Monday before it is due.

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$.
Properties of ordered sets
Suppose $S$ is an ordered set with ordering $\preceq$.
1. Prove that if $E \subseteq S$, then $\inf 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$.)
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.
Some explicit extrema
1. Prove that $\sup\set{x + y - z \mid x, y, z \in \Q, 0 \gt x \geq y \gt -z} = 0$.
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{x + y + z \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.

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$ an 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
An 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?
Partial orders can be extended to orders
A partial order on a set $S$ is a relation $\preceq$ on $S$ which is transitive and antisymmetric (that is, if $x, y \in S$ with $x \preceq y$ and $y \preceq x$ then $x = y$, and if $x, y, z \in S$ with $x \preceq y$ and $y \preceq z$ then $x \preceq z$). In particular, note that $S$ may have incomparable elements: $x, y \in S$ so that neither $x \preceq y$ nor $y \preceq x$.

Prove that if $\preceq$ is a partial order on $S$, there is an order on $S$ which extends $\preceq$: that is, an order $\preceq'$ on $S$ so that if $x, y \in S$ with $x \preceq y$, then $x \preceq' y$.

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$.)

Math 104 Assignment 1

An example order

Properties of ordered sets

Suprema depend on the ordered set

Some explicit extrema

Ordering

Further musings on Problem 3

Well-orderings

Partial orders can be extended to orders