\documentclass[11pt]{article}
\def\lecnumber{1}
\def\lectopic{Jargon I : Sets}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{starter}
\newcommand{\solution}[1]{\ignore{#1}}


\def\header{
\begin{center}
	{\bf \Large \Coursename: Lecture \lecnumber}\\ 
%	Date: \lecdate\\
	Topic: \lectopic \\
	{\em Disclaimer: These notes have not gone through scrutiny and in all probability contain errors. \\
		Please discuss in Piazza/email errors to deeparnab@dartmouth.edu}
\end{center}
\hrule height 2pt
}

\begin{document}
\header

\section{Basics}

\begin{itemize}
	\item {\bf Definition.}
	A set is an {\em unordered} collection of {\em distinct} objects. 
	These objects are called \hl{\em elements} of the set. These elements could be {\em anything}, for instance, the element of a set could be a number, could be a string, could be tuples of numbers, and in fact can be other sets!
	

	
	\item {\bf Roster Notation.} 
	A set can be described by explicitly writing down the elements, such as 
	\[
	S = \{1,3,5,7,9\} ~~~~ \textrm{or} ~~~~ T = \{\textrm{apple, banana, volcano}, 100\} ~~~ \textrm{or}~~~ W = \{S, T\}
	\]
	This is called the \hl{\em roster notation}. 
	Note that the {\em elements} of the set $W$ are the sets $S$ and $T$.
	
	\item {\bf The $\in$ and $\notin$ notation.}
	We use the notation ``element'' $\in$ ``set'' to indicate that the ``element'' is in the ``set''. We use $\notin$ to denote that the element is not in the set.
	In the above example, $3\in S$ and $\textrm{apple} \in T$ and $S \in W$. But be wary : $3 \notin W$. When figuring out if an element is in a set, we don't ``keep opening'' the sets inside.	
	
	
	\item {\bf Set Builder Notation.}
	A set can also be described {\em implicitly} by stating some rule which the elements follow. For example, 
	\[
	S = \{n: n \textrm{ is a positive odd integer less than}~ 10\} ~~~~ \textrm{or} ~~~~ V= \{x^2: x \textrm{ is an integer and} ~1\leq x\leq 5\}
	\]
	This is called the \hl{\em set-builder notation.}
	
	The sets $S$ described in the above two examples correspond to the same set. 
	The set $V$, written explicitly in the roster notation, is
	$V = \{1, 4, 9, 16, 25\}$. 
	
	\remark{Caution: Unless otherwise explicitly mentioned, duplicate items are removed from a set. For example, consider the set $A = \{x^2: -2 \leq x \le 2\}$ in the set-builder notation. In the roster notation, this set is $\{0,1,4\}$ and {\bf not} $\{4, 1, 0, 1, 4\}$. 
	}
	
	
	\item {\bf Cardinality of a set.} The \hl{\em  cardinality} of a set $S$ is denoted as $|S|$ is the number of elements in the set. 
	For example if $A = \{\textrm{apple, banana, avocado}\}$, then $|A| = 3$.
	
	\todo{
		What is $|A|$ when $A = \{x^2 : -3 \leq x \leq 3, ~~x\in \ZZ\}$?
	}


	If the set $S$ has only finitely many elements, then $|S|$ is a finite number, and $S$ is called a \hl{\em  finite} set. $|S|$ could be $\infty$ in which case the set is called an infinite set. 
	
	
	\item {\bf Famous examples of Infinite Sets.} 
	$\NN$, the set of all natural numbers; $\ZZ$, the set of all integers; $\QQ$, the set of all rational numbers, $\RR$, the set of all real numbers; and $\mathbb{P}$, the set of all computer programs written in Python. 
	This course will mostly talk about finite sets. We will visit infinite sets (perhaps) in the very end of this course. 
	

	
	
	\item {\bf Empty Set.} There is only one set which contains no elements and that set is called the \hl{\em  empty set} or sometimes the \hl{\em  null set}. It is denoted as $\emptyset$ or $\{\}$.
	
	\item {\bf Subsets and Supersets.} 	A \hl{\em  subset} $P$ of a set $S$ is another set such that every element of $P$ is an element of $S$. In that case, the notation used is $P \subset S$ or $P\subseteq S$. 
	Note that $S \subseteq S$ as well, that is, a set is always a subset of itself.
	In case $P$ is a subset and not equal to $S$, it is called a \hl{\em  proper subset}. It is denoted as $P\subsetneq S$.
	
	For example, if $A = \{1,2,3\}$ and $B = \{1,2\}$, then $B \subsetneq A$. 
	
	\remark{
		The empty set $\emptyset$ is a subset of {\em all} sets. This is a convention.
	}
	
	
	
	If $A \subset B$, then $B$ is called a \hl{\em  superset} of $A$. This is denoted as $B \supset A$.

	\item {\bf Power Set.} Given any set $S$, the \hl{\em power set} $\cP(S)$ is the set of {\em all} subsets of the set $S$.
	It is a set of sets. Note by the above convention, for any set $S$, the empty set $\emptyset \subseteq S$ and therefore, $\emptyset \in \cP(S)$.
	
	\todo{
		Write down {\em all} subsets of the sets $S = \{1,2\}$, $T = \{1,2,3\}$ and $U = \{1,2,3,4\}$. Do you see a pattern in the number of subsets?
}	

	

\end{itemize}
\section{Set Operations.}

\begin{itemize}
		\item {\bf Union.} Given two sets $A$ and $B$, the \hl{\em  union} $A\cup B$ is the set containing all elements which are either in  $A$, or in $B$, or both. For example, if
		\[
		A = \{1,3,4,7, 10\} ~~ \textrm{and} ~~ B = \{2,4,7,9,10\}, ~~~ \textrm{then}  ~~A \cup B = \{1,2,3,4,7,9,10\}
		\]

		\item {\bf Intersection.} Given two sets $A$ and $B$, the \hl{\em  intersection} $A\cap B$ is the set containing all elements which are in {\em both} in $A$ and in $B$.  For example, if
		\[
		A = \{1,3,4,7, 10\} ~~ \textrm{and} ~~ B = \{2,4,7,9,10\}, ~~~ \textrm{then}  ~~A \cap B = \{4,7,10\}
		\]
		Two sets $A$ and $B$ are called \hl{\em  disjoint} if $A\cap B = \emptyset$.
		

		\item {\bf Distributive Property}
	\begin{thm}
		For any three sets $A, B, C$, we have 
		\begin{enumerate}
			\item[(a)] $(A\cup B) \cap C = (A\cap C) \cup (B\cap C)$.
			\item[(b)] $(A\cap B) \cup C = (A\cup C) \cap (B\cup C)$.
		\end{enumerate}
	\end{thm}
	\begin{proof}
		We prove (a) and leave (b) as an exercise.
		
		To show equality of two sets, we need to show two things. For every $x$ in the LHS set, we need to show it lies in the RHS set. And vice-versa.
		
		Pick any $x\in (A\cup B)\cap C$. Therefore, $x\in C$ and $x\in A$ or $x\in B$.
		If $x\in A$, then since $x\in C$, we have $x\in A\cap C$, and therefore $x$ is in the RHS set. If $x\in B$, then a similar argument shows $x\in B\cap C$ and therefore $x$ is in the RHS set.
		
		Now the vice-versa. Pick any $x\in (A\cap C) \cup (B\cap C)$.
		$x$ is either in $A\cap C$ or in $B\cap C$. Suppose $x\in A\cap C$. Then, $x\in A$ which implies $x\in A\cup B$, and therefore, since $x\in C$, we have $x\in (A\cup B) \cap C$. 
		The other possibility, that is if $x\in B\cap C$ also symmetrically implies $x\in (A\cup B)\cap C$.
	\end{proof}
	
	
		\todo{ True or False: If $A$ and $B$ are disjoint sets, and $C\subset A$, then are $C$ and $B$ disjoint?}
		
		
		\item {\bf Difference.} Given two sets $A$ and $B$, the \hl{\em  set difference} $A\setminus B$ are all the elements in $A$ which are {\em not in $B$} and $B\setminus A$ are the elements in $B$ which are not in $A$. For example, if
		\[
		A = \{1,3,4,7, 10\} ~~ \textrm{and} ~~ B = \{2,4,7,9,10\}, ~~~ \textrm{then}  ~~A \setminus B = \{1, 3\} ~~~ \textrm{and}~~~ B\setminus A = \{2,9\}
		\]
		\todo{ Can $A\setminus B = B\setminus A$ for any two sets $A$ and $B$?}
		\remark{Some useful observations:
			\begin{enumerate}[noitemsep]
				\item $A$ and $B\setminus A$ are \emph{\bf disjoint} since $B\setminus A$ doesn't contain elements of $A$.
				\item In particular, this implies $(A\cap B)$ and $B\setminus A$ are disjoint since $A\cap B \subseteq A$.
				\item $A \cup (B\setminus A) = A\cup B$. 
				This is because every element of $A\cup B$ is either in $A$, and if not in $A$, must be in $B\setminus A$.
				\item $(A\cap B) \cup (B\setminus A) = B$. This is because every element of $B$ is either in $A$ (in which case it is in $A\cap B$) or
				in $B\setminus A$.
			\end{enumerate}
		}
	
		\item {\bf Cartesian Product.} 
		
		Given any two sets $A$ and $B$, the \hl{\em Cartesian product} $A\times B$ is another set whose elements are {\em tuples} (that is, \underline{ordered}  pairs)
		whose first entry comes from $A$ and the second entry comes from $B$. Therefore, in the set-builder notation
		\[
		A \times B = \{(a,b): a\in A ~\textrm{and}~ b \in B \}
		\]
		
		For example, if $A = \{1,2,3\}$ and $B = \{a,b\}$, then 
		\[
		A\times B = \{(1,a), (1,b), (2,a), (2,b), (3,a), (3,b) \}
		\]
		\remark{ Note that $A \times B$ is in general not equal to $B \times A$. In particular, in the above example, the elements of $B\times A$ are
		$\{(a,1), (b,1), (a,2), (b,2), (a,3), (b,3)\}$. The element $(a,1)$ is not the same as $(1,a)$ for the order matters. A tuple is {\bf not} a set.}

		\todo{ Can you figure out the cardinality of $|A\times B|$ in terms of $|A|$ and $|B|$?}
	\end{itemize}

\section{Baby Inclusion-Exclusion}

\begin{itemize}
	\item We now meet the first non-trivial (but simple) statement in the course. It is the ``baby'' inclusion-exclusion identity/equation/formula. 
	It is ``baby'' because we will meet the grown-up version later in the course. But the baby is strong enough for many things. 
	
	\item Before we go to the inclusion-exclusion, we start with a simpler but key claim.
	\begin{claim}\label{clm:disjunion}
				If $A$ and $B$ are two disjoint finite sets, then $|A\cup B| = |A| + |B|$.
	\end{claim}
	\begin{proof}
		Since $A$ and $B$ are finite, they have well-defined cardinalities which are non-negative integers.
		Let $|A| = k$ and let $|B| = \ell$; note that these can be $0$. 		
		
		We are now going to {\em name} the elements of our sets. This will be very helpful in our reasoning. Indeed naming objects is a key thing to learn in this course.
		There is fantastic power in this simple sounding step. And so, to this end, let $A = \{a_1, a_2, \ldots, a_k\}$ and let $B = \{b_1, b_2, \ldots, b_\ell\}$. Note that if either $k$ or $\ell$ or both are $0$, then the corresponding set would be $\{\}$ that is, the empty set $\emptyset$. So this notation is well defined.
		
		Now for the key observation : since $A$ and $B$ are disjoint, we know that
		$a_i \neq b_j$ for any indices $i$ and $j$. Therefore, $A\cup B = \{a_1, a_2, \ldots, a_k, b_1, b_2, \ldots, b_\ell\}$ since it must contain all items of $A$ and $B$. Thus, by inspection now, $|A\cup B| = k + \ell = |A| + |B|$.		
\end{proof}


	\item Now we are ready for stating and proving the baby inclusion-exclusion theorem.
		\begin{thm}[Baby Inclusion-Exclusion]
			For any two finite sets $A$ and $B$, we have
			\[
			|A\cup B| = |A| + |B| - |A\cap B|
			\]
		\end{thm}
		\begin{proof}
			Since $A\cup B = A \cup (B\setminus A)$ and since $A$ and $B\setminus A$ are disjoint,  we get
			\begin{equation}\label{eq:1}
			|A\cup B| = |A| + |B\setminus A|
			\end{equation}
			Since $B = (A\cap B) \cup (B\setminus A)$ and since $(A\cap B)$ and $B\setminus A)$ are disjoint,  we get
			\begin{equation}\label{eq:2}
			|B| = |A\cap B| + |B\setminus A|
			\end{equation}
			Subtracting \eqref{eq:2} from \eqref{eq:1}, we get
			\[
			|A\cup B| - |B| = |A| - |A\cap B|
			\]
			The theorem follows by taking $|B|$ to the other side.
		\end{proof}
	

\end{itemize}
\pagebreak
\emph{Answers to exercises}
\begin{itemize}
	\item Note that $A = \{9, 4, 1, 0\}$, and thus the answer is $4$. Although $-3$ and $+3$ are distinct, their squares are not, and in the set $A$ they are counted only once.
	\item The set of  subsets of $S$ are $\{\emptyset, \{1\}, \{2\}, \{1,2\}\}$, and there are {\bf four} of them.  The set of subsets of $T$ are 
	\[
	\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}
	\]
	and there are {\bf eight} of them.
	I will let you write all the subsets of $U$. Do you see the pattern now?
	\item True. If $A$ and $B$ are disjoint, then no element of $A$ is present in $B$. Since $C$ is a subset of $A$, no element of $C$ is present in $B$ either.
	Conversely, no element of $B$ is present in $A$ (since they are disjoint), and thus no element of $B$ can be present in $C$ either. 
	
	In general, $C\subseteq A$ implies $C\cap B \subseteq A\cap B$. If the second set is $\emptyset$, then $C\cap B$ has to be $\emptyset$ since that is the {\bf only} subset of an empty set.
	Thus, $C$ and $B$ are disjoint too.
	
	\item It can! If $A = B$, then both $A\setminus B$ and $B\setminus A$ are $\emptyset$. Is that the only possibility?
	
	\item It is simply $|A\times B| = |A| \cdot |B|$, the product of the two cardinalities. In the ``combinatorics'' module, this will be called the ``product principle''.
	Do you see why this is true? For each of the $|A|$ choices of the ``first entry'' in the tuple of $A\times B$, there are precisely $|B|$ choices for the ``second entry''.

\end{itemize}

\end{document}