\documentclass{amsart} \usepackage[parfill]{parskip} \usepackage{graphicx} \usepackage{amssymb, latexsym} \usepackage{epstopdf} \usepackage{color} \DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png} \textwidth = 6.5 in \textheight = 9 in \oddsidemargin = 0.0 in \evensidemargin = 0.0 in \topmargin = 0.0 in \headheight = 0.0 in \headsep = 0.0 in \parskip = 0.2in \parindent = 0.0in \pagestyle{plain} \newsavebox{\savepar} \newenvironment{xbox}{\begin{lrbox}{\savepar} \begin{minipage}[c]{\textwidth}} {\end{minipage}\end{lrbox}\fcolorbox{black}{green}{\usebox{\savepar}}} \renewcommand{\baselinestretch}{1.3} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem*{defn}{Definition} \newtheorem{example}{Example}[section] \theoremstyle{remark} \newtheorem*{notation}{Notation} \newtheorem*{note}{Note} \begin{document} \section{Naive Set Theory: Basic Definitions} \begin{defn} A \emph{set} is a collection of objects, called the \emph{elements} or \emph{members} of the set. \end{defn} \begin{note} For now, the terms `set' and `collection' will be treated as synonymous. \end{note} \begin{xbox} The empty set is a collection of no objects, denoted either $\emptyset$ or $\{ \}$. (Be careful: $\{ \emptyset \}$ denotes....) \end{xbox} \begin{xbox} \begin{defn} Set $B$ is a \emph{subset} of set $A$ iff ..... The \emph{power set} of a set $A$, denoted $\wp (A)$, is.... \end{defn} \end{xbox} \begin{xbox} \begin{note} To show that two sets $A$ and $B$ are equal, ..... \end{note} \end{xbox} \begin{xbox} \begin{defn} The \emph{union} of sets $A$ and $B$ is given by $A \cup B =$..., and the \emph{intersection} is $A \cap B = $... The \emph{relative complement} of $B$ in $A$ is $A \backslash B =$... \end{defn} \end{xbox} \begin{defn} The \emph{Cartesian product} of two sets $A$ and $B$ is given by \[ A \times B = \{(a,b) \mid a \in A, b \in B \}. \] More generally, for a finite collection of sets $A_1, A_2, \dots , A_n$, \[ \prod_{i=1}^n A_i = A_1 \times A_2 \times \dots \times A_n =\{ (a_1, a_2, \dots ,a_n) \mid a_i \in A_i \}. \] \end{defn} \begin{defn}If A and B are sets, a \emph{relation from $A$ to $B$} is a subset $R$ of $A \times B$. \end{defn} \begin{notation} For all $a \in A, b \in B$, $a\, R \, b \iff (a,b) \in R$ . \end{notation} \begin{xbox} \begin{example} Let $A= \{1, 2, 3, 4\}$ and $B=\{10, 11, 12, 13\}$ and define a relation by $a \, D\, b$ $\iff$ $a$ divides $b$. Then $D = $... \end{example} \end{xbox} \begin{xbox} \begin{defn} An \emph{equivalence relation} is a relation $R$ from a set $S$ to itself that is reflexive, symmetric and transitive; that is, ...... \end{defn} \end{xbox} \begin{defn} If $R$ is an equivalence relation on a set $S$ and $x \in S$ , then \emph{the equivalence class of $x$ in $S$ under $R$} is given by $[x] = \{y \in S \, | \, (x, y) \in R\} = \{y \in S \, | \, x \, R \, y\}$. \end{defn} \begin{xbox} \begin{example} Let $S = \mathbb{Z}$, and define $ x \, R \, y \iff x - y$ is divisible by 3; that is, $x-y=3k$ for some $k \in \mathbb{Z}$. Then $R$ is an equivalence relation on $\mathbb{Z}$ because ... . Moreover, $[0] = ...$. \end{example} \end{xbox} \begin{theorem} An equivalence relation $R$ partitions a set $S$ into equivalence classes. \end{theorem} \begin{xbox} \begin{proof} We must show that every $x \in S$ belongs to one and only one equivalence class. Since $R$ is reflexive, $x \in [x]$. Now suppose that we also have $x \in [y]$ for some $y \in S$. Then we must show that $[x]=[y]$. ..... \end{proof} \end{xbox} \begin{xbox} \begin{defn} A \emph{function} $f:A \to B$ is a relation $f \subseteq A \times B$ such that for each $a \in A$, there exists exactly one ordered pair in $f$ whose first coordinate is $a$. An \emph{injection} or \emph{one-to-one} function is...; a \emph{surjection} or \emph{onto} function is....; and a \emph{bijection} is.... [Phrase these in terms of this new definition of a function as a set of ordered pairs.] \end{defn} \end{xbox} \begin{xbox} \begin{note} If $A \neq \emptyset$, [ are there any functions $A \to \emptyset$ or $\emptyset \to A$? What about $\emptyset \to \emptyset$?] \end{note} \end{xbox} \begin{notation} If $f:A \to B$ is a function, then for all $a \in A$ and $b \in B$, $f(a) = b \iff (a,b) \in f$. \end{notation} \begin{defn} If $f:A \to B$ is a function and $C \subset A$, then the \emph{restriction of $f$ to $C$} is the function $g:C \to B$ defined by $g(c) = f(c)$ for all $c \in C$. \end{defn} \begin{notation} The restriction of $f$ to $C$ is sometimes denoted $f |_C$. \end{notation} \begin{xbox} \begin{note} Any restriction of an injective function is injective. This is not the case for surjectivity. \end{note} \end{xbox} \begin{xbox} \begin{note} If $f:A \to B$ is a function, then $f:A \to f(A)$ will be a surjective function. \end{note} \end{xbox} \begin{defn} Let $\{A_i \mid i \in I \}$ be an arbitrary collection of sets. Then the union and intersection of the collection are respectively \[ \bigcup \{A_i \mid i \in I \} = \{x \mid x \in A_i \text{ for some } i \in I \} \text { and } \bigcap \{A_i \mid i \in I \} = \{x \mid x \in A_i \text{ for all } i \in I \}. \] \end{defn} \begin{defn} Let $\{A_i \mid \in I \}$ be a nonempty collection of nonempty sets; that is, the index set $I$ could be finite, countably infinite or uncountable. A \emph{choice function} is any function $f: \{A_i \mid i \in I \} \to \bigcup \{A_i \mid i \in I \}$ satisfying $f(A_i) \in A_i$. That is, a choice function `chooses' exactly one element from each set in the collection. \end{defn} \begin{defn}The \emph{Cartesian product} of a nonempty collection of nonempty sets $\{A_i \mid i \in I \}$, denoted by $\prod \{A_i \mid i \in I\}$, is the set of all choice functions defined on $\{A_i \mid i \in I \}$. \end{defn} \begin{xbox} \begin{note} This generalizes the definition of Cartesian products of finitely many sets because... \end{note} \end{xbox} \framebox[\textwidth][c]{ \parbox{.9\textwidth}{ \vspace{8pt} \textbf{AXIOM OF CHOICE.} \emph{The Cartesian product of a nonempty collection of nonempty sets is nonempty. Equivalently, a choice function exists for any nonempty collection of nonempty sets.} \vspace{8pt} } } \begin{note} This is an \emph{axiom}, not a theorem. We do not \emph{prove} it is true, we \emph{accept} it as true. \end{note} \end{document}