\documentclass{article}
\input{preamble.tex}
\title{Day 8}
\date{Thursday May 31, 2012}
\newcommand{\df}{\textbf}
\def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut \else {\color{blue} #2} \fi }
\newcounter{clm}[thm]
\renewcommand{\theclm}{\arabic{clm}}
\def\claim{\par\medskip\noindent\refstepcounter{clm}\hbox{\bf Claim \arabic{clm}.}
\it\ %\ignorespaces
}
\def\endclaim{
\par}
\newenvironment{clm}{\begin{changemargin}{1.75cm}{1.5cm}\claim}{\endclaim\end{changemargin}}
\newenvironment{clmpf}{ \renewcommand{\qedsymbol}{\subqed} \begin{changemargin}{2cm}{1.5cm}\begin{proof}}{\end{proof}\end{changemargin}}
\def\changemargin#1#2{\list{}{\rightmargin#2\leftmargin#1}\item[]}
\let\endchangemargin=\endlist
\begin{document}
\maketitle
\section{Sets}
Today, we begin a big chunk of the course which will stretch about $2$ weeks. We begin to learn \df{set theory}
\subsection{A Bit on History}
Set theory is a branch of mathematics that has its origins in the late 19th century. The ``Father of Set Theory'' was Georg Cantor. We will see a couple of results from Cantor in this course. In the current mathematical world, mathematicans have chosen set theory to be the language of mathematics; if you imagine mathematics are a software suite, the current version is coded in set theory.
This makes set theory very important for people who want to do mathematics. Set appear in every branch of mathematics. Besides that, the techniques that came from the rich re-formaization of mathematics into set theory and logic that came at the turn of the 19th to 20th century still reside in the culture, techniques, and styles of mathematicians today.
\subsection{A Definition}
The first question is: how do you define a set? Although this may seem like an over-formality, or perhaps obvious, this question occupied mathematicians during the first 20 years of the 20th century. As you would expect, when you write down a definition which is supposed to be good enough to define all the mathematics that we do, one must be careful.
In the beginning, people were hesitant to write down a definition for what a set should be. This led to, what we call today, \df{na\"ive set theory}. Na\"ive set theory is the system of set theory, where we say that a set is simply a collection of objects, and we never formalize exactly what we can do with these collections. We will see later last week, na\"ive set theory fails to be a sound system that we want to work in, which led to greater rigor.
The contemporary system of set theory is called \df{ZFC}, which stands for {\bf Z}ermelo-{\bf F}raenkel Set Theory with {\bf C}hoice.
Despite na\"ive set theory not being a good system to formalize mathematics, it is still the system which guides the intuition of mathematicians today. Because of this, for a course like this, it is not necessary to work in the strong system of ZFC, and we will ignore the problem with na\"ive set theory, excepting some passing comments at the end.
\subsection{Collections}
So, a set to us is a collection of objects, and objects are the things that we are already accustomed with: numbers, functions, and even sets themselves. When we explicitly write a set, we write the objects in curly braces $\s{\;}$ separated by commas.
\subsubsection{Some Examples We Already Know}
There are lots of sets we already know. For example
\begin{itemize}
\item $\N$ is the set of natural numbers. We would write the natural numbers as
\[
\N = \s{0,1,2,3,\ldots}
\]
\item $\Z$ is the set of integers. We would write the integers as
\[
\Z = \s{\ldots,-2,-1,0,1,2,\ldots}
\]
\item $\Q$ is the set of rationals.
\item $\R$ is the set of reals.
\item $\mathbb{C}$ is the set of complex numbers.
\end{itemize}
We will define one new set of numbers that we haven't yet seen. For every natural number $n$ we have the following set of natural numbers less than $n$
\[
[n] := \s{0,1,2,\ldots,n-1}
\]
\subsection{Membership}
The hallmark of being in a set is being able to ask the yes/no question: is $x$ a member of you? In fact we have the following principle:
\begin{dfn}[Principle of Extensionality]
Two sets $A$ and $B$ are the same if they have exactly the same members.
\end{dfn}
If $A$ is a set and $x$ is some object, asking the question ``Is $x$ a member of $A$?'' is denoted:
\[
x\in A
\]
This is an atom, like we talked about before. It is either true or false, and it's truth can be checked independently from all other claims.
\begin{rmk}
An important remark is that exenstionality says nothing about the number of a particular element in the set, just that they have the same members. Therefore, we have
\[
\s{1,1} = \s{1}
\]
Since both sets answer the yes/no questions about member exactly the same, ie. they say yes to $1$ and no to everything else.
\end{rmk}
\begin{rmk}
Also plain is that the order of a set obviously shouldn't matter either, since the answers to the yes/no question ``Is $x$ a member?'' doesn't depend on the order. So, in particular we have
\[
\s{1,2} = \s{2,1}
\]
\end{rmk}
\subsection{The Empty Set}
We have a special set which has absolutely no items in it. This is called the \df{empty set}, and is written $\emptyset$. The empty set can be thought of as the set which answers `No' to any question about whether an element belongs to it, that is the atom
\[
x\in \emptyset
\]
is always false, without even knowing anything about $x$. stated in a more logicy way with quantifiers:
\[
\A x \st \neg (x\in \emptyset)
\]
\subsection{Subset}
One question that we might have is is every member of $A$ a member of $B$? Stated in terms of logic:
\[
\A x \st x\in A \to x\in B
\]
In this case we have that $A$ is a \df{subset} if $B$, and we write
\[
A\sbs B
\]
What are some examples we know?
\Hide{1in}{
\begin{itemize}
\item $\N \sbs \Z \sbs \Q \sbs \R$
\item Evens are a subset of the naturals.
\item Irrationals are a subset of the reals
\end{itemize}
}
Let's write some code to see exactly what checking to see if $A$ is a subset of $B$.
\begin{verbatim}
foreach ( x in A ) {
if (x in B) {
next;
}
else {
return false;
}
}
return true;
\end{verbatim}
So, asking the question of whether $A$ is a subset of $B$, the default behavior is it is true, unless it can find a counterexample. Therefore, What do you think the truth value of:
\[
\emptyset \sbs A
\]
\Hide{1cm}{
It is true, since it won't find a counterexample since there is nothing that is in $\emptyset$ that is not in $A$...because there's nothing in the empty set!
}
On the homework, I ask you to answer some questions about $A$. Think a lot about the code each time.
\subsection{Equality}
We already talked about the principle of extensionality which is supposed to guide what it means for two sets to be equal. Another way to state it is
\[
\A x \st x\in A \bimp x\in B
\]
Notice, we can rewrite this as
\[
(x\sbs A) \oand (x\sbs B)
\]
So, checking whether two sets are not equal is the matter of finding a counterexample: is there an element which is in one of the sets and not in the other?
\begin{eg}
The set $\s{1,2}$ is a subset of $\s{1,2,3}$ since every element of $\s{1,2}$ is in $\s{1,2,3}$.
On the other hand, $\s{1,2,3}$ is not a subset of $\s{1,2}$ since $3$ is in the former but not the latter.
\end{eg}
\section{Operations on Sets}
If we have two sets, we have several operations we can perform on them.
\subsection{Unions}
Given two collections of objects, we can perform a \df{union}, which joins the sets together. So, the union of $A$ and $B$ is just the things that is in $A$ and the things that are in $B$. We write
\[
A \cup B
\]
as the union of $A$ and $B$ (in \LaTeX, this symbol is \textbackslash cup).
Another way to define an operation is to say exactly what the answer to $x\in A\cup B$ is, given you know the answers that $A$ and $B$ give. In this case, the definition looks like
\[
\A x \st x\in A\cup B \bimp (x \in A \oor x\in B)
\]
\begin{eg}
The union of $\s{2,4,74}$ and $\s{4,7, 12}$ is
\Hide{1cm}{
\[
\s{2,4,7,12,74}
\]
}
\end{eg}
\subsection{Intersections}
Given two collection of objects, we can perform a \df{intersection}, which meets the sets. The intersection of $A$ and $B$ is the things that are in both $A$ and $B$. We write this
\[
A\cap B
\]
(in \LaTeX, this symbol is \textbackslash cap)
Speaking logically, the definition looks like
\[
\A x \st x\in A \cap B \bimp (x \in A \oand x\in B)
\]
\begin{eg}
The intersection of $\s{2,4,74}$ and $\s{4,7, 12}$ is
\Hide{1cm}{
\[
\s{4}
\]
}
The intersection of $\s{2,4,6}$ and $\s{1,3,5}$ is
\Hide{1cm}{
\[
\emptyset
\]
}
\end{eg}
\subsection{Relative Complements}
So, one may ask the question: What is the compliment of a set, ie. the set of all elements not in that set? What is the problem with asking this?
\Hide{1in}{
Well, the color blue is an object, and it is not a natural number, so would the color blue be in the complement on $\N$? It's hard to peg down exactly the larger universe we are dealing with here, so it's not natural to take a compliment of a set.
}
To fix this problem we talk about the \df{relative complement} or \df{set difference}. The set difference, which we say $A$ take away $B$ or $A$ minus $B$, is the things which are in $A$ but not in $B$. We write this is
\[
A \minus B
\]
(in \LaTeX, this is \textbackslash setminus)
Logically, we write
\[
\A x \st (x\in A\minus B) \bimp ( (x\in A) \oand (x\notin B))
\]
Note: I used some `slang' notation here. If $\neg(x\in B)$ we usually write $x\notin B$.
\subsection{Comprehension}
Say we have some logical stuff, and we wish to form a new set by taking all thing things that satisfy this. For instance, maybe I want to take all the natural numbers $n$ that are even, ie. satisfy $\E m\in\N \stt 2m = n$.
This is called \df{comphrension}, \df{seperation}, or \df{specification} depending on who you talk to. The notation that we use for this is called \df{set builder notation}. In this instance, we would write
\[
\set{ x \in \N \mid \E m\in \N \stt 2m = n }
\]
We read this as ``the set of all natural numbers such that there exists an $m$ in the naturals such that $2m$ equal $n$.''
Note, in this case we are carving a smaller set out of a larger set. When doing this comphrension, as with relative complements, it doesn't make sense without specifying a larger set.
In general, set builder notation looks like
\[
B = \set{ x \in A \mid P(x) }
\]
where $P(x)$ is some formula with only $x$ free. Then, to check membership in this set, one ``loops through'' the member of $A$,
\begin{verbatim}
New Set B = \emptyset;
foreach(x in A) {
if ( P(x) ) {
Put x in B;
next;
}
else {
next;
}
}
\end{verbatim}
\end{document}