\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{anyfontsize}
\usepackage[super]{nth}
\usepackage{ulem}
\usepackage{multicol}
\usepackage{phaistos}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage[all,arc]{xy}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{8: Operations on Sets}{Due Thursday, Week 4, at the start of class.}

Solve \textbf{one} of the following \textbf{three} problems.  As always, prove your claims!

The theme for these problems: \textbf{binary operations} on sets!  Specifically: a \textbf{binary operation} on a set $S$ is any map that takes elements of $S \times S$ to $S$; addition, multiplication, exponentiation, the binomial coefficient and other objects are all examples of such operations on $\mathbb{N}$, for example.  Often, we will want to study properties of such maps. 

For example, suppose that that I gave you a binary operation $\cdot$ on a set $S$ with the following two properties:
\begin{itemize}
\item \textbf{Identity}: There is a unique element $e \in S$ such that $e \cdot x = x \cdot e = x$, for all $x \in S$.
\item \textbf{Inverses}: For any $x \in S$, there is a unique $x^{-1} \in S$ such that $x \cdot x^{-1} = x^{-1} \cdot x = e$.
\item \textbf{Annihilator}:\footnote{I did not make this term up.} There is a unique element $n \in S$ such that $n \cdot x = x \cdot n = n$, for all $n \in S$.
\end{itemize}

What could you tell me about $S$?  Well: look at our annihilating element $n$.  By inverses, we know that there is an element $n^{-1}$ such that $n^{-1} n = n n^{-1} = e$.  But, by definition, we also know that $n^{-1} n = n$, because $n$ is an annihilating element.  Therefore, we have $n = e$.  But we know that for any $x \in S$, we have $e \cdot x = x$, and that for any $x \in S$, we have $n = n \cdot x$; consequently, because $n = e$, we have $n = x$ for any $x$.  In other words, our group $S$ consists of only one element, $n$!

This is the kind of thing these problems study: given an operation with some simple properties, what can you conclude?
\begin{enumerate}
\item[0.] Solve any un-signed-up-for problems from HW\#6!
\item Let $\star$ be a binary operation on the set $S$ that satisfies the following three properties:
\begin{itemize}
\item \textbf{Commutative}: $\forall a, b \in S$, $a \star b = b \star a$.
\item \textbf{Associative}: $\forall a,b,c \in S$, $a \star (b \star c) = (a \star b) \star c$.
\item \textbf{Delicious}\footnote{I did make this term up!}: $\forall a, b \in S, \exists z \in S$ such that $a \star z = b$.
\end{itemize}

Prove that $\star$ satisfies the following \textbf{cancellation} property: 
\begin{itemize}
\item \textbf{Cancellation}: if $a,b,c \in S$ and $a \star c = b \star c$, then $a = b$.
\end{itemize}

\item Take any set $S$ and any binary operation $\clubsuit$ on $S$.  Suppose that $\clubsuit$ satisfies the following property:
\begin{itemize}
\item \textbf{Tartan}\footnote{I also made this term up!}: For all $a, b\in S$, we have $(a \clubsuit b) \clubsuit a = b$.
\end{itemize}
Prove that $\clubsuit$ also satisfies the following property:
\begin{itemize}
\item \textbf{Plaid}\footnote{Really, if it looks ridiculous, I probably made it up.}: For all $a, b\in S$, we have $a \clubsuit (b \clubsuit a) = b$.
\end{itemize}

\item Take any set $S$ and any binary operation $\ast$ on $S$ that satisfies the following properties:
\begin{itemize}
\item \textbf{Associative}: $\forall a,b,c \in S$, $a \ast (b \ast c) = (a \ast b) \ast c$.
\item \textbf{Dubious}: For any $a, b \in S$, we have $a \ast b = b \ast a \Rightarrow a = b.$ 
\end{itemize}
Show that it satisfies the following property:
\begin{itemize}
\item \textbf{Poisonous}: For any $a, b,c \in S$, we have $a \ast (b \ast c) =a \ast c.$ 
\end{itemize}
Can you find an example of such an operation on $\mathbb{N}$?

\end{enumerate}





\end{document}


