%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{graphicx}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}
 \theoremstyle{remark}    
 \newtheorem{notation}[thm]{Notation} 
 \theoremstyle{plain}    
 \newtheorem*{prop*}{Proposition} 
 \theoremstyle{plain}    
 \newtheorem*{thm*}{Théorème} 
 \theoremstyle{remark}
 \newtheorem*{rem*}{Remarque}
 \theoremstyle{plain}    
 \newtheorem*{lem*}{Lemme} %%Delete [thm] to re-start numbering
 \theoremstyle{remark}    
 \newtheorem{summary}[thm]{Résumé} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\usepackage[francais,american]{babel}
\makeatother
\begin{document}

\chapter{Sets (section 3.1 )}


\section{Introduction}

Problem p 161

Goal:

\begin{itemize}
\item Introduce the formalism of set theory
\item Use it to solve counting problems
\end{itemize}

\section{Sets and basic manipulations of sets}


\subsection{Definition }

\begin{defn*}
A \emph{set} $A$ is a collection of objects. 
\end{defn*}
Defining property: you can ask whether an object $a$ belongs to $A$
or not.

Objects or elements: $a,b,c,...$.

Sets: $A,B,C,...$.

Predicates:

\begin{itemize}
\item $a\in S$: $a$ belongs to $S$, or $a$ is an element of $S$, or
$S$ contains $a$;
\item $a\notin S$: $a$ does not belong to $S$.
\end{itemize}
Two sets $A$ and $B$ are \emph{equal} ($A=B$) if they contain the
same elements:\[
(\forall x)(x\in A)\Leftrightarrow(x\in B)\]



\subsection{How to define a set $S$?}

You have to describe which elements are in the set $S$ and which
are not.

\begin{itemize}
\item List the elements of the set $S$:\\
\[
S:=\{ a,b,c\}\]
 $a\in S$ is true, whereas $d\in S$ is false.\\
The order and the repetition are irrelevant:\[
\{ a,b,c\}=\{ a,b,b,b,c\}=\{ c,b,a\}\]
\\
Note that $a$ and $\{ a\}$ are two different things. The first is
the object $a$, whereas the second one is the set containing $a$,
and no other elements. 
\item Provide a predicate which determines which element are in $S$:\[
S:=\{ x\,|\, P(x)\}\]
\[
S:=\{ x\,|\, x\textrm{ is an integer and }3<x\leq7\}\]
 $5\in S$ is true, whereas $3\not\in S$, and no car belongs to A.
\item Use a \emph{recursive definition}, as for the set of well formed formulas:\\
$S$ contains basic propositions $A,B,C,...$\\
If $P$ and $Q$ belong to S, then $P'$, $P\wedge Q$, $P\vee Q$,
$P\rightarrow Q$, $P\leftrightarrow Q$ also belong to $S$. 
\end{itemize}
Some usual sets:

\begin{itemize}
\item The empty set: \[
\emptyset:=\{ x\,|\, false\}\]

\item Numbers: \[
\N:=\{ x\,|\, x\textrm{ is a non negative integer }\}\]
 \[
\Z:=\{ x\,|\, x\textrm{ is an integer }\}\]
 \[
\Q:=\{ x\,|\, x\textrm{ is a rational number }\}\]
 \[
\R:=\{ x\,|\, x\textrm{ is a real number }\}\]
 \[
\C:=\{ x\,|\, x\textrm{ is a complex number }\}\]
 \[
S^{*}:=\{ x\,|\, x\in S\textrm{ and }x\neq0\}\]
 \[
S^{+}:=\{ x\,|\, x\in S\textrm{ and }x\geq0\}\]

\end{itemize}

\subsection{Relationships between sets}

\begin{itemize}
\item A is a \emph{subset} of B ($A\subseteq B$) iff any element of $A$
is in $B$: \[
(\forall x)(x\in A)\Rightarrow(x\in B)\]
 
\item $A$ is a \emph{proper subset} of $B$ ($A\subset B$) iff $A$ is
a subset of $B$ but they are not equal :\[
(\forall x)(x\in A)\Rightarrow(x\in B)\textrm{ and }(\exists x)(x\in B)\wedge(x\notin A)\]
 
\end{itemize}
\begin{xca}
\cite[Exercise 10 p.~117]{Gersting.MSCS}\[
R:=\{1,3,\pi,4,1,9,10\},\, S:=\{\{1\},3,9,10\}\]


\[
T:=\{1,3,\pi\},\, U:=\{\{1,3,\pi\},1\}\]

\begin{enumerate}
\item $S\subseteq R$?
\item $1\in R$?
\item $1\in S$?
\item $1\subseteq U$?
\item $\{1\}\subseteq T$?
\item $\{1\}\subseteq S$?
\item $T\subset R$?
\item $\{1\}\in S$?
\item $\emptyset\subseteq S$?
\item $T\subseteq U$?
\item $T\in U$?
\item $T\notin R$?
\item $T\subseteq R$?
\item $S\subseteq\{1,3,9,10\}$?
\end{enumerate}
\end{xca}

\subsection{The powerset of a set}

The powerset $\wp(S)$ of a set $S$ is the set of all subsets of
$S$.

\begin{example*}
What are the elements of the following powersets ?
\end{example*}
\begin{enumerate}
\item $\wp(\{1,2\})=$ 
\item $\wp(\{1\})=$
\item $\wp(\emptyset)=$
\end{enumerate}
\begin{xca}
What is the size of $\wp(S)$ if $S$ has $n$ elements ? 
\end{xca}

\subsection{Binary and unary operations}

\begin{defn*}
$\bullet$ is a \emph{unary operation} on a set $S$ if for every
element $x$ of $S$, $\bullet x$ exists, is unique and is a member
of $S$.

$\bullet$ is a \emph{binary operation} on a set $S$ if for every
ordered pair $(x,y)$ of elements of $S$, $x\bullet y$ exists, is
unique and is a member of $S$.
\end{defn*}
Examples: 

\begin{enumerate}
\item is $+$a binary operation on $\N$ ?
\item is $+$a binary operation on $\{0,1,2\}$?
\item is $\times$a binary operation on $\{0,1\}$
\item is $-$a binary operation on $\N$ ?
\item is $/$a binary operation on $\Z$ ?
\item are $+$,$-$, and $\times$binary operations on $\Q$ ?
\item are $+$,$-$, $\times$and $/$binary operations on $\Q^{*}$?
\item is $\sqrt{x}$ a unary operation on $\R^{+}$ ?
\item are $\wedge$, $\vee$, $\rightarrow$, $'$, \ldots{} operations
on $\{ true,false\}$? on wff ?
\end{enumerate}
A binary operation can be defined by its \emph{multiplication} table.

\begin{example*}
$(\{ true,false\},\wedge)$
\end{example*}
\vspace{0.3cm}
\begin{center}\begin{tabular}{|c||c|c|}
\hline 
$\wedge$&
$false$&
$true$\tabularnewline
\hline
\hline 
$false$&
$false$&
$false$\tabularnewline
\hline
$true$&
$false$&
$true$\tabularnewline
\hline
\end{tabular}\end{center}
\vspace{0.3cm}

An operation does not necessarily need to have a particular meaning.

\begin{example*}
$(\{2,5,9\},\bullet)$ 

\vspace{0.3cm}
\begin{center}\begin{tabular}{|c||c|c|c|}
\hline 
$\bullet$&
$2$&
$5$&
$9$\tabularnewline
\hline
\hline 
$2$&
$2$&
$5$&
$2$\tabularnewline
\hline
$5$&
$2$&
$9$&
$5$\tabularnewline
\hline
$9$&
$9$&
$2$&
$5$\tabularnewline
\hline
\end{tabular}\end{center}
\vspace{0.3cm}

$5\bullet9=?$

\end{example*}

\section{Operations on sets}


\subsection{The universe of discourse}

We have seen operations on numbers, or other objects. 

We can also define operations on sets (union, intersection, \ldots{}).

We need a set that contains all the sets we want to deal with.

It would be tempting to consider the set of all sets.

\begin{problem}
Let $S$ be the set of all sets that does not contain themselves.

Does $S$ contain itself ?

%

%

%

%

%

%

%
\begin{itemize}
\item if $S$ does not contain itself, then it contains itself ! 
\item if $S$ contains itself, then it does not contain itself !
\end{itemize}
\end{problem}
There is a strange loop here which yields a contradiction: S cannot
exist.

For a similar reason, \emph{the set of all sets cannot exist}.

See \emph{Gödel Esher Bach\cite{Hofstadter.GEB}} for a lot of similar
fun stuff with strange loops.

That's been a major source of trouble and work a century ago, when
mathematicians tried to define a strong basis for set theory.

To be safe, we always work inside a set big enough to contain all
the sets we need, but small enough to avoid the strange loop above. 

\begin{defn*}
This set is the \emph{universal set}, or the \emph{universe of discourse}.
\end{defn*}
We define operations on the powerset of the universal set.


\subsection{Union, intersection, complement and Cartesian product}

We define operations on subsets of the universe of discourse.

\begin{defn*}
The \emph{union} of $A$ and $B$ is the set:

\[
A\cup B:=\{ x\,|\, x\in A\textrm{ or }x\in B\}\]

\end{defn*}
%

\begin{defn*}
The \emph{intersection} of $A$ and $B$ is the set:

\[
A\cap B:=\{ x\,|\, x\in A\textrm{ and }x\in B\}\]

\end{defn*}
%

\begin{defn*}
The \emph{complement} of $A$ is the set: \[
A':=\{ x\,|\, x\notin A\}\]
 
\end{defn*}
%

\begin{defn*}
The \emph{set difference} of $A$ and $B$ is the set:

\[
A-B:=\{ x\,(x\in A)\textrm{ and }(x\notin B)\}\]

\end{defn*}
%

\begin{defn*}
The \emph{Cartesian product} (or \emph{cross product}) of $A$ and
$B$ is the set:

\[
A\times B:=\{(x,y)\,|\, x\in A,y\in B\}\]

\end{defn*}
\begin{notation}
$A^{2}=A\times A$ is the set of all ordered pairs of elements of
$A$;

$A^{n}=A\times\cdots\times A$ is the set of all $n$-uples of elements
of $A$.
\end{notation}
\begin{defn*}
\emph{Venn diagrams.}
\end{defn*}
\begin{xca}
\emph{Let $A:=\{1,2\}$ and $B:=\{2,3,4\}$. }
\begin{enumerate}
\item $A\cup B=$, 
\item $A\cap B=$, 
\item $A-B=$,
\item $A'=$ (assuming that the universe of discourse is $\{1,2,3,4\}$),
\item $A\times B=$,
\item $A^{3}=$.
\end{enumerate}
\end{xca}
%

\begin{xca}
Let $A$ be a set of size $n$, and $B$ a set of size $m$.
\begin{enumerate}
\item what is the size of $A\cup B$: 
\item what is the size of $A\cap B$: 
\item what is the size of $A'$ ? 
\item what is the size of $A\times B$ : 
\end{enumerate}
\end{xca}

\subsection{Set identities}

\begin{prop*}
Let $A$ and $B$ be to sets. Then,

$A\cap B=B\cap A$ (commutative property)
\end{prop*}
\begin{proof}
$x\in A\cap B$ 

$\Leftrightarrow(x\in A)\wedge(x\in B)$ by definition of $\cap$

$\Leftrightarrow(x\in B)\wedge(x\in A)$ by commutativity of $\wedge$

$\Leftrightarrow x\in B\cap A$ by definition of $\cap$
\end{proof}
The commutativity of $\cap$derives directly from the commutativity
of $\wedge$.

All identities on logic operators induce identities on set operators.

\begin{prop*}
Let $A$, $B$, and $C$ be two sets. Then,

$A\cup B=B\cup A$ (commutative property)

$A\cap B=B\cap A$ (commutative property)

$(A\cup B)\cup C=A\cup(B\cup C)=A\cup B\cup C$ (associative property)

$(A\cap B)\cap C=A\cap(B\cap C)=A\cap B\cap C$ (associative property)

$A\cup A'=S$ (complement, $S$ is the universe of discourse)

$A\cap A'=\emptyset$ (complement)

$(A\cup B)'=A'\cap B'$ (de Morgan's)

$(A\cap B)'=A'\cup B'$ (de Morgan's)

$A-B=A\cap B'$
\end{prop*}

\section{Countable and uncountable sets}


\subsection{Enumerations}

If a set $S$ has $k$ elements, these can be listed one after the
other:

\[
s_{1},s_{2},\ldots,s_{k}\]


\begin{defn*}
$s_{1},s_{2},\ldots,s_{k}$ is called an \emph{enumeration} of the
set $S$.
\end{defn*}
\begin{example*}
$1,5,4,3$, $5,1,3,4$, and $4,1,3,5$ are enumerations of the set
$\{1,5,4,3\}$.
\end{example*}
When a set $S$ is infinite, you can not enumerate all of it's elements
at once. 

However, some times, you can still pickup a first element $s_{1}$,
then a second $s_{2}$, and so on forever. This process is an enumeration
of the elements of $S$ if:

\begin{itemize}
\item Any element of $S$ gets enumerated eventually;
\item No element is enumerated twice.
\end{itemize}
\begin{example*}
$0,1,2,3,4,\ldots$ is an enumeration of the non-negative integers.
\end{example*}

\subsection{Denumerable and Countable sets}

\begin{defn*}
A infinite set $S$ is \emph{denumerable} if it has an enumeration
\[
s_{1},s_{2},\ldots,s_{n},\ldots\]


A set $S$ is \emph{countable} if it's either finite or denumerable.
\end{defn*}
\begin{example*}
Are the following sets countable ?
\end{example*}
\begin{enumerate}
\item The set of all students in this class.
\item The set $\N$ of the non-negative integers (enumeration: $0,1,2,3,4,\ldots$);\\
Actually, the order does not need to be logical.\\
This is a perfectly legal enumeration: $0,10,5,11,4,2,17,2,1,28,3$
\item The set of the even integers (enumeration: ;
\item The set of the prime integers (enumeration: ;
\item The set $\Z$ of the integers (enumeration: );
\item The set $\N\times\N$ 


(e.g. all points in the plane with non-negative integer coordinates):

\includegraphics[%
  width=1\textwidth]{NxN}

%

%

%%

\includegraphics[%
  width=1\textwidth]{NxNenum}

\item Enumeration: $(0,0),(0,1),(1,0),(2,0),(1,1),(0,2),(3,0),\ldots$ 
\item The set $\Z\times\Z$ of all points in the plane with integer coordinates:


\includegraphics[%
  width=1\textwidth]{ZxZ}

%

%

%

%%

\includegraphics[%
  width=1\textwidth]{ZxZenum}

Enumeration: $(0,0),(0,1),(1,0),(0,-1),(-1,0),(2,0),\ldots$

\item The set $\Q$ of rational numbers:


\includegraphics[%
  width=1\textwidth]{rational}

\end{enumerate}
\begin{thm*}
The following sets are countable:
\begin{enumerate}
\item Any subset $A\subset B$ of a countable set $B$.
\item The union $A\cup B$ of two countable sets $A$ and $B$ is countable.
\item The union $A_{1}\cup A_{2}\cup\cdots\cup A_{i}$ of a finite number
$i$ of countable sets $A_{1},\ldots,A_{i}$.
\item The union $A_{1}\cup A_{2}\cup\cdots\cup A_{i}\cup\cdots$of a countable
number of countable sets.
\item The cross product $A\times B$ of two countable sets $A$ and $B$
is countable.
\item The cross product $A_{1}\times\cdots\times A_{i}$ of a finite number
of countable sets $A_{1},\ldots,A_{i}$.
\end{enumerate}
\end{thm*}
\begin{proof}
Enumerations of those sets can be constructed in the following way:
\end{proof}
\begin{enumerate}
\item Enumerate the elements of $B$, and ignore those that are not in $A$.
\item Enumerate the elements of $A$ and $B$ alternatively ($a_{1},b_{1},a_{2},b_{2},\ldots$).
\item Induction, using 2.
\item As for $\N\times\N$: $a_{1,1},a_{2,1},a_{1,2},a_{3,1},a_{2,2},a_{1,3},\ldots$
($a_{i,j}$ is the $j$th element of $A_{i}$).
\item As for $\N\times\N$: $(a_{1},b_{1}),(a_{1},b_{2}),(a_{2},b_{1}),(a_{1},b_{3}),(a_{2},b_{2}),(a_{3},b_{1}),\ldots$.
\item Induction, using 5.
\end{enumerate}

\subsection{Uncountable sets ?}

\begin{rem*}
All the sets we have seen so far are countable.
\end{rem*}
\begin{problem}
Are there any uncountable sets ?
\end{problem}
\begin{thm*}
(Cantor) $\R$ is uncountable.
\begin{lem*}
Any real number $x\in[0,1)$ can be written uniquely in decimal form:
\[
x=0.d_{1}d_{2}d_{3}d_{4}\cdots d_{i}\cdots,\]
where the $d_{i}$ are digits between $0$ and $9$, and the sequence
does not end by an infinite number of $9$.
\end{lem*}
\end{thm*}
\begin{example*}
Here is how some classical numbers can be written:
\begin{itemize}
\item $0=0.0000\cdots$
\item $0.5=0.50000\cdots$
\item $0.5=0.49999\cdots$ (Same number as above, we don't use this form)
\item $\frac{1}{3}=0.333333\cdots$
\item $\pi=3.141592653\cdots$
\end{itemize}
\end{example*}
Let's jump to the proof of the theorem, without detailing the proof
of this lemma.

\begin{proof}
(Of the theorem): \emph{Cantor diagonalization method}.

It's sufficient to prove that $[0,1)$ is not countable.

Let's do this by contradiction: assume $[0,1)$ is countable.

Let $s_{1},s_{2},\ldots,s_{i},\ldots$ be an enumeration of $[0,1)$.

Goal: construct an element which is not in this enumeration.

Using the lemma, we can write the $s_{i}$ as follow:

\[
\begin{array}{ccccccccc}
s_{1} & = & 0, & \underline{d_{1,1}} & d_{1,2} & d_{1,3} & d_{1,4} & d_{1,5} & \cdots\\
s_{2} & = & 0, & d_{2,1} & \underline{d_{2,2}} & d_{2,3} & d_{2,4} & d_{2,5} & \cdots\\
s_{3} & = & 0, & d_{3,1} & d_{3,2} & \underline{d_{3,3}} & d_{3,4} & d_{3,5} & \cdots\\
s_{4} & = & 0, & d_{4,1} & d_{4,2} & d_{4,3} & \underline{d_{4,4}} & d_{4,5} & \cdots\\
s_{5} & = & 0, & d_{5,1} & d_{5,2} & d_{5,3} & d_{5,4} & \underline{d_{5,5}} & \cdots\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\]


We want to construct an element $x$ which is not in this enumeration.

Let's look at an example:

\[
\begin{array}{cccccccc}
s_{1} & = & 0, & \underline{1} & 5 & 7 & 3 & 5\cdots\\
s_{2} & = & 0, & 0 & \underline{0} & 4 & 7 & 3\cdots\\
s_{3} & = & 0, & 4 & 5 & \underline{7} & 0 & 3\cdots\\
s_{4} & = & 0, & 9 & 7 & 3 & \underline{5} & 7\cdots\\
s_{5} & = & 0, & 4 & 3 & 8 & 1 & \underline{0}\cdots\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\ddots\\
\textrm{ } & \textrm{ } & \textrm{ } & \textrm{ } & \textrm{ } & \textrm{ } & \textrm{ } & \textrm{ }\\
x & = & 0, & 0 & 1 & 0 & 0 & 1\cdots\end{array}\]


\emph{The trick} : let $x_{i}=1$ if $d_{i,i}=0$ and $x_{i}=1$ else.

Then, $x\neq s_{1}$. But also, $x\neq s_{2}$, $x\neq s_{3}$, \ldots{}
 

Therefore $x$ is indeed never enumerated! Contradiction!

Conclusion: $[0,1)$ is not countable.
\end{proof}
\begin{rem*}
We can deduce that many sets like $\C$, or $[5.3,10)$ are uncountable.

A similar proof can be used to prove that many other sets are uncountable.

This includes the set of all infinite strings, or the set $\wp(\N)$
of all subsets of $\N$.
\end{rem*}
\begin{summary}
We have a hierarchy of bigger and bigger sets:
\end{summary}
\begin{enumerate}
\item The empty set
\item Finite sets (the empty set, sets with $1$ element, sets with $2$
elements, \ldots{})
\item Denumerable sets: $\N$, $\Z$, $\Q$, \ldots{}
\item Uncountable sets: $\R$, $\C$, \ldots{}
\item \ldots{}
\end{enumerate}
\begin{problem}
Is there any set bigger than $\N$ and smaller that $\R$? Nobody
knows!
\end{problem}

\section{Conclusion}

We are now done with basic properties of sets. We have seen enough
formalism

to go on to the next section, \emph{Combinatorics}: 

\begin{center}How to count the objects in a finite set ?\end{center}
\end{document}
