01. Sets

$\gdef \N{\mathbb{N}} \gdef \Z{\mathbb{Z}} \gdef \Q{\mathbb{Q}} \gdef \R{\mathbb{R}} \gdef \C{\mathbb{C}} \gdef \setcomp#1{\overline{#1}} \gdef \sseq{\subseteq} \gdef \pset#1{\mathcal{P}(#1)} \gdef \covariant{\operatorname{Cov}} \gdef \of{\circ} \gdef \p{^{\prime}} \gdef \pp{^{\prime\prime}} \gdef \ppp{^{\prime\prime\prime}} \gdef \pn#1{^{\prime\times{#1}}} $

Dec. 25

Sets¶

Definitions, Notations, and Symbols¶

• A set is a collection of distinct, unordered elements.
• \(\alpha\in A\) means that the element \(\alpha\) is contained within the set \(A\).
  • \(\alpha\not\in A\) is a negation of the above
• A set \(T\) is a subset of \(S\) if every element in \(T\) is also in \(S\)
  • Can be restated as If the statement “if \(x\in T\) then \(x\in S\)” is true, then…
  • Denoted \(T\subseteq S\)
  • \(T\not\subseteq S\) is a negation of the above
  • Both sides of the \(\subseteq\) symbol must be sets
  • Every set is a subset of itself
• A set \(T\) is a proper subset of \(S\) if \(T\subseteq S\) and \(T\not= S\)
  • Denoted as \(T\subset S\)
• The empty set is the set containing no elements.
  • Denoted as \(\set{}\) or \(\phi\) (Greek letter phi)
  • It is a subset of every set, other than itself

Important Sets to Know¶

• \(\N\)
  • The set of all natural numbers
  • Integers greater than and NOT equal to Zero
  • \(\set{1,2,3,\dots}\)
• \(\Z\)
  • The set of all integers
  • \(\set{\dots,-2,-1,0,1,\dots}\)
• \(\Q\)
  • The set of all rational numbers
  • \(\set{\frac mn\mid m,n\in\Z,\ n\neq0}\), if you’re fancy
• \(\R\)
  • The set of all real numbers

Set Operations¶

• Union — \(A\cup B\)
  • Returns a set containing elements that are in either or both sets
  • Commutative and associative
  • If \(A\subseteq B\) then \(A\cup B=B\)
  • For all sets \(A,B\): \(A\subseteq A\cup B\), and \(B\subseteq A\cup B\)
• Intersection — \(A\cap B\)
  • Returns a set containing elements that are strictly in both sets
  • Commutative and associative
  • If \(A\subseteq B\) then \(A\cap B=A\)
  • For all sets \(A,B\): \(A\cap B\subseteq A\), and \(A\cap B\subseteq B\)
  • Conclusion:
    • \(A\cap B\ \subseteq A\subseteq \ A\cup B\)
    • \(A\cap B\ \subseteq B\subseteq \ A\cup B\)
• Difference — \(A - B\) or \(A \setminus B\)
  • Returns a set containing all of the elements in \(A\) that were not found in \(B\)
  • Not commutative or associative
• Symmetric Difference — \(A\bigtriangleup B\) or \(A\oplus B\)
  • Returns a set containing all of the elements in either \(A\) or \(B\), but not both
  • Commutative and associative, surprisingly
  • \(A\oplus B = (A\cup B) - (A\cap B)\)
• Complement — \(\setcomp A\) or \(A^\mathsf{c}\)
  • Often, every set we consider is seen as a subset of a larger set, called the universal set, such as \(\N\) or \(\R\). We denote this universal set as \(U\).
  • For any set \(A\), \(\setcomp A\) is the set of all elements in \(U\) that are not in \(A\).
  • \(\setcomp A = U - A\)

Properties of Set Operators¶

1. \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\)
2. \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\)
3. \(\setcomp{A\cup B}=\setcomp A\cap\setcomp B\)
4. \(\setcomp{A\cap B}=\setcomp A\cup\setcomp B\)

Venn Diagrams¶

I found this material to be useful but not worth me drawing up my diagrams. If you would like to send me a diagram to put in here, create a diagram using Excalidraw, and send me the link to the diagram. I will add it to the notes and credit you.

Proofs¶

How to formally prove that \(A=B\)?
Proofs must use 2-directional inclusion, i.e:
\(A=B\) iff \(A\sseq B\) and \(B\sseq A\).
We must show that both of the following are true:

• If \(x\in A\), then \(x\in B\)
• If \(x\in B\), then \(x\in A\).

Dec. 31

Power Set¶

Definition: The power set of a set \(S\) (denoted \(\pset S\)) is the set of all subsets of \(S\).

For any set \(S\), \(\phi\in\pset S\) and \(S\in\pset S\).

Power Set Theorem¶

For any finite set \(S\), \(|\pset S|=2^{|S|}\), where \(|S|\) is the number of elements in \(S\).

This means that the number of elements in the power set of a set is equal to \(2\) raised to the number of elements in the set.

Infinite Unions and Intersections¶

• Unions: \(\bigcup_{i=1}^\infty A_i\)
  • The union of all sets \(A_i\) for \(i=1,2,3,\dots\)
  • The set of all elements that are in at least one of the sets \(A_i\)
  • In English: “The union of \(A_i\) for all \(i\)”
  • Example: \(\bigcup_{i=1}^\infty\set{i}=\N\)
  • Example: \(\bigcup_{i=1}^\infty[\frac1i,\frac1{i+1})=(0,1]\)
    • Explanation: The union of all intervals \([\frac1i,\frac1{i+1})\) for \(i=1,2,3,\dots\) is the interval \((0,1]\) (open on the left, closed on the right)
• Intersections: \(\bigcap_{i=1}^\infty A_i\)
  • The intersection of all sets \(A_i\) for \(i=1,2,3,\dots\)
  • The set of all elements that are in every one of the sets \(A_i\)
  • In English: “The intersection of \(A_i\) for all \(i\)”
  • Example: \(\bigcap_{i=1}^\infty\set{i}=\set{1}\)
  • Example: \(\bigcap_{i=1}^\infty[\frac1i,\frac1{i+1})=\set{0}\)
    • Explanation: The intersection of all intervals \([\frac1i,\frac1{i+1})\) for \(i=1,2,3,\dots\) is the set \(\set{0}\) because the only number that is in every interval is \(0\).

Cartesian Products¶

Definition: An ordered pair is a pair of elements \((a,b)\) in which the order of the elements matters. \((a,b)\not=(b,a)\).

Definition: An ordered n-tuple is an ordered list of \(n\) elements \((a_1,a_2,\dots,a_n)\) in which the order of the elements matters. \((a_1,a_2,\dots,a_n)\not=(a_2,a_1,\dots,a_n)\).

Familiar examples of ordered pairs and ordered n-tuples:

• Point in the plane: \((x,y)\)
• Point in space: \((x,y,z)\)

Definition:
Let \(A, B\) be sets. The Cartesian product of \(A\) and \(B\) (denoted \(A\times B\)) is the set of all ordered pairs \((a,b)\) where \(a\in A\) and \(b\in B\).

Formally, \(A\times B=\set{(a,b)\mid a\in A,\ b\in B}\)

Properties of Cartesian Products¶

• Unlike previous set operations (\(\cup,\cap,\setcomp\ , \setminus\) ), the elements of \(A\times B\) are new elements, not elements of \(A\) or \(B\).
  • \(A\cap (A\times B)=\phi\)
• The product is not commutative
  • In general, \(A\times B\not=B\times A\)
• For finite sets \(A,B\), \(|A\times B|=|A|\cdot|B|\)

Distributivity of Cartesian Products¶

1. \(A\times(B\cup C)=(A\times B)\cup(A\times C)\)
2. \(A\times(B\cap C)=(A\times B)\cap(A\times C)\)