\documentclass{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage{tikz}
\usepackage{circuitikz}
\usepackage{mathrsfs}
\usepackage{hyperref}

\begin{document}
\flushleft\underline{Homework 8 --- MATH 2510 Spring 2018} \\
Consider the vocabulary $\mathcal{V}=\{\preceq\}$. Recall the following $\mathcal{V}$-sentences (called ``axioms") from Tuesday's class:
\begin{enumerate}
\item \textbf{Axiom 1} (reflexive) $\forall x (x \preceq x)$
\item \textbf{Axiom 2} (anti-symmetric). $\forall x \forall y (x \preceq y \wedge y \preceq x \rightarrow x=y)$
\item \textbf{Axiom 3} (transitive). $\forall x\forall y\forall z(x \preceq y \wedge y \preceq z \rightarrow x \preceq z)$
\item\textbf{Axiom 4} (total). $\forall x \forall y (x \preceq y \vee y \preceq x)$
\end{enumerate}
And recall the ``well-ordering principle": \textbf{every} nonempty subset of the universe contains a least element. (\textit{note: writing this in logic symbols necessitates something like ``$\forall S \subseteq \mathcal{U}$" which is not part of our language of first order logic --- it is ``second order logic"!})

We say that a structure $M=(S|\preceq)$ is a preorder on $S$ if it is reflexive and transitive. We say that a structure $M=(S|\preceq)$ is a partial order on $S$ if it is an anti-symmetric preorder. We say that a structure $M=(S|\preceq)$ is a total order on $S$ if it is a total partial order. We say that a structure $M=(S|\preceq)$ is a well-order on $S$ if it is a total order that also obeys the well-ordering principle. \\
\vspace{2cm}
\underline{Problems} \\
In every problem, determine which of the axioms that the structure models. If the structure is a preorder, partial order, total order, or well-order, then state so.
\begin{enumerate}[1.]
\item Consider the structure $M=(\{\emptyset, \{a\}, \{b\}, \{a,b\}\}|\preceq)$ where $x \preceq y$ is interpreted to mean $x \subseteq y$. \\
\textit{Solution}: Satisfies Axioms 1, 2, and 3. Not Axiom 4 because $\{a\} \not\subset \{b\}$ and $\{b\} \not\subset \{a\}$. It is well-ordered. This structure is a partial order (it is not a well order since it is not a total order). (Such a structure is called \href{https://en.wikipedia.org/wiki/Well-quasi-ordering}{well partial order}.)

\item Let $f \colon \mathbb{R} \rightarrow \mathbb{R}$ be the function $f(x)=x^2$. Consider the structure $M=(\mathbb{R}|\preceq)$, where $x \preceq y$ is interpreted to mean $f(x) \leq f(y)$ (where ``$\leq$" here is interpreted in the usual way). \\
\textit{Solution}: Satisfies Axioms 1, 3, and 4. Does not satisfy Axiom 2 since $f(-1)=f(1)=1$ and therefore $f(-1) \preceq f(1) \wedge f(1) \preceq f(-1)$ while $1 \neq -1$. Does not satisfy WO because the set $(0,1]$ does not have a $\preceq$-least element. This structure is a preorder. (In fact, a structure that satisfies Axioms 1, 3, and 4 is called a \href{https://en.wikipedia.org/wiki/Weak_ordering}{total preorder}.)

\item Consider the $xy$-plane $\mathbb{R}^2=\{(x,y) \colon x \in \mathbb{R}, y \in \mathbb{R}\}$. Consider the structure $M=(\mathbb{R}|\preceq)$ where $(x_1,y_1) \preceq (x_2,y_2)$ is interpreted to mean that $x_1 \leq x_2$ and $y_1 \leq y_2$ (where ``$\leq$" here is interpreted in the usual way). \\
(\textit{note: this is called the product order of $\leq$}) \\
\textit{Solution}: This structure satisfies Axioms 1, 2, and 3. It is not a total order because, for example neither $(1,0) \preceq (0,1)$ nor $(0,1) \preceq (1,0)$. It is not a well-order because the set $\{(x,y) \colon 0<x<1, y=0\}$ has no least element. This structure is a partial order.

\item Consider the $xy$-plane $\mathbb{R}^2$. Consider the structure $M=(\mathbb{R}|\preceq)$ where $(x_1,y_1) \preceq (x_2,y_2)$ is interpreted to mean that $x_1 < x_2$ OR $x_1=x_2$ and $y_1 \leq y_2$ (where ``$<$" and ``$\leq$" are interpreted in the usual way). So for example, $(-2,5) \leq (5,2000)$ because $-2 < 5$ and $(-2, 232) \leq (-2, 333)$ because $-2=-2$ and $232 \leq 333$. \\ 
(\textit{note: this is called ``lexicographic" or ``dictionary" order}) \\
\textit{Solution}: Satisfies Axioms 1, 2, 3, 4. It is not a well order because the set $\{(x,y) \colon 0<x<1, y=0\}$ has no $\preceq$-least element. This structure is a total order.

\item (Sharkovsky order) Consider the structure $M=(\mathbb{N}|\preceq)$, where $\preceq$ is interpreted to be the so-called Sharkovskii order: 
\begin{multline*}
1 \prec 2 \prec 2^2 \prec 2^3 \prec \dots \prec  ~2^n~ \prec
\dots \quad
\dots \prec ~7 \cdot 2^n~ \prec ~5 \cdot 2^n~ \prec ~3 \cdot 2^n~
\prec \dots \\
~\qquad \qquad \qquad \qquad~~~\dots \prec ~7 \cdot 2~ \prec ~5 \cdot 2~ 
\prec ~3 \cdot 2~ \prec
\dots \prec ~9~ \prec ~7~ \prec ~5~ \prec ~3~.
\end{multline*}
You can understand this interpretation by thinking of it as saying
\begin{center}
descending powers of $2$ (ascending) $\preceq \ldots \preceq$ (odd numbers)$\cdot 2^n \preceq$ (odd numbers)$\cdot 2^{n-1} \preceq \ldots \preceq$ (odd numbers)$\cdot 2 \preceq$ odd numbers (descending)
\end{center}
(\textit{note: this order is fundamental to \href{https://en.wikipedia.org/wiki/Sharkovskii\%27s_theorem}{Sharkovskii's theorem} from the 1960's}) \\
\textit{Solution}: Satisfies Axioms 1, 2, 3, 4. It is not a well-order because the set of odd numbers has no least element. The structure is a total order.

\hrule 
Recall that we defined the notation $A \subseteq B$ to abbreviate the formula $z \in A \rightarrow z \in B$. We write $A \cap B$ as and abbreviation for $z \in A \wedge z \in B$. 
\item Prove that that $X \cap Y \subseteq X$.  \\
\textit{Solution}: We need to show that $\forall z ((z \in X \cap Y) \rightarrow z \in X)$. \\
\textbf{General strategy for proving $P \rightarrow Q$}: Assume $P$ and try to prove $Q$ from it. (This is similar to ``$\rightarrow$-definition" from our proof system of propositional logic.)  \\
So assume $z \in X \cap Y$. From this we see from the definition of $\cap$ that $z \in X \wedge z \in Y$. Therefore we may conclude that $z \in X$. So, we have shown $z \in X \cap Y \rightarrow z \in X$. Since the variable ``$z$" did not come from removing an existential quantifier, we may place $\forall z$ in front to get
$$\forall z (z \in X \cap Y \rightarrow z \in X),$$
completing the proof. $\blacksquare$
\end{enumerate}
\end{document}