\documentclass[10pt,addpoints]{exam}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{enumerate}
\pagestyle{head}
\usepackage{mathrsfs}
\usepackage{tikz}
\usepackage{cancel}
\usepackage{hyperref}
\renewcommand*{\arraystretch}{2}
%\headrule
%\header{MATH 11}{Exam 1}{Fall 2016}
\begin{document}
\begin{coverpages}
\begin{center}\huge MATH 2510 - EXAM 3 - SPRING 2018 \\
SOLUTION
\end{center}
\begin{flushleft}\vspace{0.5in}
19 April 2018\\
Instructor: Tom Cuchta
\end{flushleft}
\textbf{Instructions:}
\begin{itemize}
	\item  Show all work, clearly and in order, if you want to get full
	credit. If you claim something is true \textbf{you must show work backing up your claim}. I reserve the right to take off points if I cannot see how you arrived at your answer (even if your final answer is correct).
	\item Justify your answers algebraically whenever possible to ensure full credit. 	
	\item  Circle or otherwise indicate your final answers.
	\item  Please keep your written answers brief; be clear and to the point.
	\item  Good luck!
\end{itemize}
\vspace*{10pt}
\end{coverpages}

\begin{questions} 
\question[16] Consider the vocabulary $\mathcal{V}=\{\preceq\}$. Recall the following $\mathcal{V}$-sentences (called ``order axioms"):
\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.

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. \\

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{parts}
\part[5] The structure $(\mathbb{R},\preceq)$ where $x \preceq y$ is interpreted as the ``usual" $\leq$ ordering. \\
\textit{Solution}: Axioms 1-4 hold. The well-ordering principle does not hold because, for example, $(0,1) \subset \mathbb{R}$ does not contain a least element.
\part[5] The structure $(\mathbb{N},\preceq)$ where $x \preceq y$ is interpreted as $y \leq x$ in the ``usual" ordering (note: this \textbf{is not} the usual ordering...read it carefully!). \\
\textit{Solution}: Axioms 1-4 hold, but it is not well-ordered because $\{2,4,6,8,\ldots\}$ does not contain a $\preceq$-least element.
\part[6] Consider $X=\{1,2,3,4,6,12,24\}$. Consider the structure $(X,\preceq)$, where $x \preceq y$ is interpreted to mean $x$ divides evenly into $y$. \\
\textit{Solution}: Axioms 1-3 hold but Axiom 4 does not hold because $2 \not{|} 3$ and $3 \not{|} 2$, meaning $2 \not\preceq 3$ and $3 \not\preceq 2$. It cannot be well-ordered because $\{2,3\}$ does not contain a $\preceq$-least element. 
\end{parts}

\question[10] Is the function one-to-one? If it is not, then explain why not. If it is, then draw a sketch of the function.
\begin{parts}
\part[5] $f \colon \mathbb{Z} \rightarrow \mathbb{R}$ defined by $f(x)=x^3$ \\
\textit{Solution}: It is one-to-one.
\begin{tikzpicture}
\draw[->] (-3,0) -- (4.2,0) node[right] {$x$};
\draw[->] (0,-3) -- (0,4.2) node[above] {$y$};
\draw[scale=0.5,domain=-2:2,smooth,variable=\x,blue] plot ({\x},{\x*\x*\x});
\end{tikzpicture}
\part[5] $f \colon \{-1,0,1,2\} \rightarrow \mathbb{N}$ defined by $f(x)=x^2+x=0$ \\
\textit{Solution}: It is not one-to-one, because $f(-1)=0=f(0)$ but $-1 \neq 0$.
\end{parts}

\question[16] In this problem you will prove $X \cap X = X$.  \\
\begin{parts}
\part[5] Prove $X \cap X \subseteq X$. \\
\textit{Solution}: If $x \in X \cap X$, then $x \in X \wedge x \in X$, hence $x \in X$. Therefore we have shown $x \in X \cap X \rightarrow x \in X$, in other words, $X \cap X \subseteq X$. 
\part[5] Prove $X \subseteq X \cap X$. \\
\textit{Solution}: If $x \in X$ then $x \in X \wedge x \in X$, hence $x \in X \cap X$, i.e. $X \subseteq X \cap X$. 
\part[6] Prove that $X \cap X = X$ using an axiom of naive set theory and parts (a) and (b). \\
\textit{Solution}: We know from (a) and (b) that $x \in X \rightarrow x \in X \cap X$ and that $x \in X \cap X \rightarrow x \in X$. Thus we can write $x \in X \leftrightarrow x \in X \cap X$. By the axiom of extensionality, removing the $\forall z$ by replacing $z$ with $x$, removing the $\forall x$ by replacing $x$ with $X \cap X$, and remoing the $\forall y$ by replacing $y$ with $X$ yields 
$$(x \in X \cap X \leftrightarrow x \in X) \rightarrow X \cap X = X.$$
Since we already knew $x \in X \cap X \leftrightarrow x \in X$, we may conclude via $\rightarrow$-elimination that $X=X\cap X$. 
\end{parts}


\question[16] Find appropriate one-to-one function(s) that demonstrate the following.
\begin{parts}
\part[5] $|\mathbb{N}| = |\{2,4,6,8,10,\ldots\}$ \\
\textit{Solution}: The function $f \colon \mathbb{N} \rightarrow \{2,4,6,8,\ldots\}$ defined by $f(n)=2n$ is one-to-one, showing $|\mathbb{N}| \leq |\{2,4,6,8,\ldots\}|$. Conversely, the function $g \colon \{2,4,6,\ldots\} \rightarrow \mathbb{N}$ defined by $g(n) = \dfrac{n}{2}$ is one-to-one and shows that $|\{2,4,6,8,\ldots\}| \leq |\mathbb{N}|$. 
\part[5] $|\mathbb{N}| \leq |\mathbb{R}|$ \\
\textit{Solution}: Define $f \colon \mathbb{N} \rightarrow \mathbb{R}$ by $f(n)=n$. This function is one-to-one, proving that $|\mathbb{N}| \leq |\mathbb{R}|$. 
\part[6] $|\omega+\omega| = |\omega+\omega+\omega|$ \\
\textit{hint:} we can draw $\omega+\omega$ as 
\begin{tikzpicture}
\draw (0,-1) -- (0,1); 
\draw (0.25,-0.8) -- (0.25,0.8);
\draw (0.45,-0.6) -- (0.45,0.6);
\draw (0.6,-0.4) -- (0.6,0.4);
\draw (0.7,-0.2) -- (0.7,0.2);
\draw (0.75,-0.15) -- (0.75,0.15);
\draw (0.8,-0.1) -- (0.8,0.1);

\draw (1,-1) -- (1,1); 
\draw (1.25,-0.8) -- (1.25,0.8);
\draw (1.45,-0.6) -- (1.45,0.6);
\draw (1.6,-0.4) -- (1.6,0.4);
\draw (1.7,-0.2) -- (1.7,0.2);
\draw (1.75,-0.15) -- (1.75,0.15);
\draw (1.8,-0.1) -- (1.8,0.1);
\end{tikzpicture} 
and we can draw $\omega+\omega+\omega$ as 
\begin{tikzpicture}
\draw (0,-1) -- (0,1); 
\draw (0.25,-0.8) -- (0.25,0.8);
\draw (0.45,-0.6) -- (0.45,0.6);
\draw (0.6,-0.4) -- (0.6,0.4);
\draw (0.7,-0.2) -- (0.7,0.2);
\draw (0.75,-0.15) -- (0.75,0.15);
\draw (0.8,-0.1) -- (0.8,0.1);

\draw (1,-1) -- (1,1); 
\draw (1.25,-0.8) -- (1.25,0.8);
\draw (1.45,-0.6) -- (1.45,0.6);
\draw (1.6,-0.4) -- (1.6,0.4);
\draw (1.7,-0.2) -- (1.7,0.2);
\draw (1.75,-0.15) -- (1.75,0.15);
\draw (1.8,-0.1) -- (1.8,0.1);

\draw (2,-1) -- (2,1); 
\draw (2.25,-0.8) -- (2.25,0.8);
\draw (2.45,-0.6) -- (2.45,0.6);
\draw (2.6,-0.4) -- (2.6,0.4);
\draw (2.7,-0.2) -- (2.7,0.2);
\draw (2.75,-0.15) -- (2.75,0.15);
\draw (2.8,-0.1) -- (2.8,0.1);

\end{tikzpicture}  \\
\textit{Solution}: Define $f \colon \omega+\omega \rightarrow \omega+\omega+\omega$ by $f(n)=n$. This function is one-to-one, proving that $|\omega+\omega| \leq |\omega+\omega+\omega$. Define $g \colon \omega+\omega+\omega \rightarrow \omega+\omega$ for $n \in \mathbb{N}$ by $g(n)=3n$, for $\omega+n$ by $g(\omega+n)=3n+1$ and for $\omega+\omega+n$ by $g(\omega+\omega+n)=3n+2$. This maps $\omega+\omega+\omega$ into $\omega$ and is one-to-one, proving that $|\omega+\omega+\omega| \leq |\omega+\omega|$. Thus we may conclude that $|\omega+\omega| = |\omega+\omega+\omega|$. 

\end{parts}

\question[15] Consider the set $X=\{2, 4, 6\}$ with the standard order relation $\leq$. \\
\begin{parts}
\part[5] List all subsets of $X$ (i.e. find $\mathscr{P}(X)$). \\
\textit{Solution}: $\mathscr{P}(X)=\{\emptyset, \{2\}, \{4\}, \{6\}, \{2,4\}, \{2,6\}, \{4,6\}, \{2,4,6\}\}$. 
\part[5] Cross out all subsets of $X$ in part (a) that are \textbf{not cofinal} with $X$. \\
\textit{Solution}: $\{\cancel{\emptyset}, \cancel{\{2\}}, \cancel{\{4\}}, \{6\}, \cancel{\{2,4\}}, \{2,6\}, \{4,6\}, \{2,4,6\}\}$ 
\part[2] Write down the cardinalities of all cofinal subsets of $X$.\\
\textit{Solution}: $|\{6\}|=1$, $|\{2,6\}|=2$, $|\{4,6\}|=2$, and $|\{2,4,6\}|=3$
\part[3] Write $\mathrm{cf}(X)$. \\
\textit{Solution}: $\mathrm{cf}(X)=1$
\end{parts}

\question[15] Show full details in computing the following cardinal arithmetic problems. \textbf{Not showing all sets (or functions) involved will not yield full credit.}
\begin{parts}
\part[4] $1 \oplus 2$ \\
\textit{Solution}: Calculate
$$\begin{array}{ll}
1 \oplus 2 &= \Big|\{ 0\} \times \{0\} \bigcup \{0,1\} \times \{1\}\Big| \\
&= \Big| \{ (0,0), (0,1), (1,1) \} \Big| \\
&=3
\end{array}$$
\part[5] $3 \otimes 3$ \\
\textit{Solution}: Calculate
$$\begin{array}{ll}
3 \otimes 3 &= \Big| \{0,1,2\} \times \{0,1,2\} \Big| \\
&= \Big| \{ (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2) \} \Big| \\
&= 9
\end{array}$$
\part[6] $5^1$ \\
\textit{Solution}: We need to count all functions $f \colon 1 \rightarrow 5$, i.e. $f \colon \{0\} \rightarrow \{0,1,2,3,4\}$. Since the domain only contains $0$, specifying where $0$ goes completely defines the function. So we have $f(0)=0, f(0)=1, f(0)=2, f(0)=3, f(0)=4,$ and $f(0)=5$ as possible ways to define the function $f$ (not all at the same time!!!!). Therefore there are a total of $5$ functions in the set ${}^15$. Thus we have
$$5^1 = \big| {}^15 \big| = 5.$$
\end{parts}

\question[12] Consider a new theory called ``differential algebra theory" which has a unary function $\partial$ and two binary functions $+$ and $\cdot$ along with the following axioms: \\
\textbf{Axiom 1:} $(\forall x)(\forall y)(\partial(x \cdot y)=(\partial x)\cdot y + x \cdot (\partial y))$ \\
\textbf{Axiom 2:} $(\forall x)(\forall y)(\partial(x+y)=\partial(x)+\partial(y))$

Prove 
$$\partial((f \cdot g)\cdot h) =((\partial f)\cdot g+f \cdot(\partial g))\cdot h + (f \cdot g)\cdot (\partial h)$$
in differential algebra theory. (\textit{hint: when you ``remove $\forall$" in Axiom 1, let $x=f \cdot g$ and let $y=h$}) \\
\textit{Solution}: By Axiom 1, remove $\forall x$ by replacing $x$ with $f \cdot g$ and remove $\forall y$ by replacing $y$ with $h$ to get
$$(*) \hspace{35pt} \partial((f \cdot g) \cdot h) = \Big(\partial (f \cdot g) \cdot h + (f \cdot g) \cdot (\partial h) \Big) + (f \cdot g) \cdot (\partial h).$$
To complete the proof, we must take care of $\partial (f \cdot g)$. To do this, in Axiom 1, remove $\forall x$ by replacing $x$ with $f$ and remove $\forall y$ by replacing $y$ with $g$ to get
$$\partial (f \cdot g) = (\partial f) \cdot g + f \cdot (\partial g).$$
Replacing $\partial (f \cdot g)$ in $(*)$ yields the desired result.
\question[4] (\textbf{Bonus}):
\begin{parts}
\part What is $\mathrm{cf}(\omega+\omega)$? (\textit{hint}: recall that $\omega+\omega=\{0,1,2,\ldots,\omega,\omega+1,\omega+2,\ldots\}$) \\
\textit{Solution}: We know $\mathrm{cf}(\omega+\omega)=\omega$ because any  cofinal subset of $\omega+\omega$ must be unbounded and $X=\{\omega,\omega+1,\omega+2,\ldots\}$ is cofinal (no finite subset of it is confinal!! Why is that?).
\vfill
\part Compute the cardinal exponentiation $2^0$ and show all the details. \\
\textit{Solution}: To compute this, we must count the number of functions in ${}^02$, i.e. the number of functions whose domain is $\emptyset$ and whose codomain is $\{0,1\}$. The only possible function that does this is the ``empty function" $\emptyset$ (same as empty set...). Thus $2^0=|{}^02|=1$.

\end{parts}
\end{questions}
\iffalse
\newpage

\noindent\underline{Axioms of Naive Set Theory} \\
\textbf{Axiom S1} (Extensionality): $\forall z \forall x \forall y ((z \in x \leftrightarrow z \in y) \rightarrow x=y)$ \\
\textbf{Axiom S2} (Unrestricted comprehension): for any formula $\phi(x)$ with one free variable, 
$$\exists x \forall z (z \in x \leftrightarrow \phi(z))$$
\underline{Definitions}:
\begin{itemize}
\item $A \cap B$ abbreviates $x \in A \wedge x \in B$ 
\item $A \subseteq B$ abbreviates $\forall z(z \in A \rightarrow z \in B)$
\item We say that a function $f \colon A \rightarrow B$ is one-to-one provided that whenever $f(x)=f(y)$ it follows that $x=y$
\item We say that $|A| \leq |B|$ provided that there is a one-to-one functions $f \colon A \rightarrow B$.
\item The ordinal numbers are $0=\emptyset; 1 = \{0\}; 2=\{0,1\}; 3=\{0,1,2\}; \ldots ; \omega = \{0,1,2,3,4,\ldots\}; \omega+1=\{0,1,2,\ldots,\omega\}; \omega+2=\{0,1,2,\ldots,\omega,\omega+1\}; \ldots ; \omega+\omega = \{01,2,3,\ldots,\omega,\omega+1,\omega+2,\ldots\}$
\item A cardinal number is an ordinal number $\beta$ with the property that if $\alpha \leq \beta$ (here: ``$\leq$" means ``earlier ordinal number" and is interpreted as $\alpha \in \beta$), then $|\alpha| \leq |\beta|$ (here: this ``$\leq$" is interpreted as cardinality)
\item cardinal addition: $\alpha \oplus \beta = |\alpha \times \{0\} \cup \beta \times \{0\}|$
\item cardinal multiplication: $\alpha \otimes \beta = |\alpha \times \beta|$
\item set of functions: ${}^A B = \{f \colon A \rightarrow B \colon f \text{ is a function}\}$
\item cardinal exponentiation: $\alpha^{\beta} = |{}^{\beta} \alpha|$
\item To ``remove a $\forall x$" you may replace $x$ with anything. To ``remove $\exists x$" you should replace $x$ with $x_0$ or $x_1$ or $\ldots$
\item You can ``add a $\forall x$" if you are replacing a variable that was not previously introduced by ``removing a $\exists x$". You can ``add a $\exists x$" to replace any variable.
\end{itemize}
\fi
\end{document}