3. Sets

3.1 Sets and subsets

Set: a collection of objects (may contain elements of different varieties)
Element: each object in a set
Roster notation definition: a list of the elements enclosed in curly braces with the individual elements separated by commas (order is unimportant, repeating an element does not change the set)
$A=\{2,4,6,10\}$

$\in$: indicates an element is in a set
$\notin$: indicates an element is not in a set

Typical:
Capital letters are used as variables denoting sets
Lowercase letters are used for elements in set
Variables can be used to indicate an unspecified member of a set

Empty set (null set, $\{\}$, $\varnothing$): set with no elements
Finite set: a set that is either empty or whose elements can be numbered 1 through $n$ for some positive integer $n$.
Infinite set: a set that is not finite
Cardinality of a finite set of set $A$ ($|A|$): the number of distinct elements in $A$
Ellipses ($...$): used to denote a long (possibly infinite) sequence of numbers (the sequence’s pattern should be clear)

$\mathbb{N}$: natural numbers (all integers that are greater than or equal to 0)
$\mathbb{Z}$: integers
$\mathbb{Q}$: rational numbers (real numbers that can be expressed as $\frac{a}{b}$, where $a$ and $b$ are integers and $b\ne 0$)
$\mathbb{P}$: irrational numbers (real numbers that cannot be expressed as $\frac{a}{b}$, where $a$ and $b$ are integers and $b\ne 0$)
$\mathbb{R}$: real numbers

Superscript $+$: positive elements of a particular set
Superscript $-$: negative elements of a particular set

Set builder notation: by specifying that the set includes all elements in a larger set that also satisfy certain conditions
$A=\{x\in S:P(x)\}$

Universal set (usually $U$): a set that contains all elements metioned in a particular context
Subset ($A\subseteq B$): if every element in $A$ is also an element in $B$
$A⊈B$: there is an element in $A$ that is not an element of $B$
Proper subset: $A$ is a subset of $B$ and there is an element of $B$ that is not an element of $A$

$\varnothing \subseteq A\subseteq U$
$A=B⟺A\subseteq B\wedge B\subseteq A$
$A\subset B⟺A\subseteq B\wedge \exists x(x\in B\wedge x\notin A)⟺A\subseteq B\wedge A\ne B$

3.2 Union and intersection

Intersection ($A\cap B$): the set of all elements that are elements of both $A$ and $B$
Union ($A\cup B$): the set of all elements that are elements of $A$ or $B$

Intersection operation and union operation can also apply to infinite sets

Muliple set operations: Ex., $A\cup (B\cap C)$, $A\cap B\cap C$

$$\bigcap _{i=1}^n{A}_i=A_1\cap A_2\cap \cdots \cap A_n=\{x:\forall i\in \{1,\dots ,n\},x\in A_i\}$$ $$\bigcup _{i=1}^n{A}_i=A_1\cup A_2\cup \cdots \cup A_n=\{x:\exists i\in \{1,\dots ,n\},x\in A_i\}$$

3.3 More set operations

Difference between two sets $A$ and $B$ ($A-B$): the set of elements that are in $A$ but not in $B$
Symmetric difference between two sets $A$ and $B$ ($A\oplus B$): the set of elements that are in either $A$ or $B$, but not both
$A\oplus B=(A-B)\cup (B-A)$

Determining the complement of a set requires that the universal set be well-defined
Complement of a set $A$ ($\overline{A}$): the set of all elements in $U$ that are not elements of $A$
$\overline{A}=U-A$

Operation	Notation	Definition
Intersection	$A\cap B$	$\{x:x\in A\wedge x\in B\}$
Union	$A\cup B$	$\{x:x\in A\vee x\in B\}$
Difference	$A-B$	$\{x:x\in A\wedge x\notin B\}$
Symmetric difference	$A\oplus B$	$\{x:x\in (A-B)\vee x\in (B-A)\}$
Complement	$\overline{A}$	$\{x:x\notin A\}$

3.4 Cartesian products

Ordered pair of items: $(x,y)$
First entry in $(x,y)$: $x$
Second entry in $(x,y)$: $y$

Parentheses around an ordered pair indicates that the order of entries is significant
$(x,y)=(y,x)⟺x=y$

Cartesian product of $A$ and $B$ ($A\times B$): the set of all ordered pairs in which the first entry is in $A$ and the second entry is in $B$
$A\times B=\left\{(a,b):a\in A\wedge b\in B\right\}$
$A\times B=B\times A⟺A=B\vee A=\varnothing \vee B=\varnothing$
If $A$ and $B$ are finite sets, then $|A\times B|=|A|\cdot |B|$

Ordered triple ($(x,y,z)$): an ordered list of three items
Ordered $n$-tuple: an ordered list of $n$ items for $n\ge 4$

$$A_1\times A_2\times \cdots \times A_n=\left\{(a_1,a_2,\dots ,a_n):a_i\in A_i,\forall i\in \{1,2,\dots ,n\}\right\}$$

$A\times A=A^2$

$$A^k=\underset{k}{\underbrace{A\times A\times \cdots \times A}}$$

If $A$ is a set of symbols or characters, the elements in $A^2$ can be written without the usual punctuation (parentheses and commas) used for ordered $n$-tuples

String: a sequence of characters
Alphabet: the set of characters used in a set of strings
Length: the number of characters in the string
Binary string: a string with alphabet $\{0,1\}$
Bit: a character in a binary string
$n$-bit string: a binary string of length $n$
The set of binary strings of length $n$: $\{0,1{\}}^n$
Empty string: the unique string with a length of 0 and is usually denoted by the symbol $\lambda$
$\{0,1{\}}^0=\{\lambda \}\ne \varnothing$
Concatenation of two strings $s$ and $t$ ($st$): the string obtained by putting $s$ and $t$ together (a string and a sing symbol can also be concatenated)
$s=010,t=11,st=01011,t0=110$
$x\lambda =x$

3.5 Set identities

Assume universal set $U$:
$x\in A\cap B⟺(x\in A)\wedge (x\in B)$
$x\in A\cup B⟺(x\in A)\vee (x\in B)$
$x\in \overline{A}⟺\neg (x\in A)$
$x\in \varnothing ⟺F$
$x\in U⟺T$

Set identity: an equation involving sets that is true regardless of the contents of the sets in the expression

Name	Identities
Idempotent laws	$A\cup A=A$	$A\cap A=A$
Associative laws	$(A\cup B)\cup C=A\cup (B\cup C)$	$(A\cap B)\cap C=A\cap (B\cap C)$
Commutative laws	$A\cup B=B\cup A$	$A\cap B=B\cap A$
Distributive laws	$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$	$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
Identity laws	$A\cup \varnothing =A$	$A\cap U=A$
Domination laws	$A\cap \varnothing =\varnothing$	$A\cup U=U$
Double complement law	$\overline{\overline{A}}=A$
Complement laws	$A\cap \overline{A}=\varnothing ,\overline{U}=\varnothing$	$A\cup \overline{A}=U,\overline{\varnothing }=U$
De Morgan’s laws	$\overline{A\cup B}=\overline{A}\cap \overline{B}$	$\overline{A\cap B}=\overline{A}\cup \overline{B}$
Absorption laws	$A\cup (A\cap B)=A$	$A\cap (A\cup B)=A$

3.6 Sets of sets

Power set of set $A$ ($P(A)$): the set of all subsets of $A$
$A=\{1,2,3\},P(A)=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

Let $A$ be a finite set of cardinality $n$:
$|P(A)|=2^n$

3.7 Partitions

Two sets are disjoint: the intersection of the two sets is empty ($A\cap B=\varnothing$)
A sequence of sets is pairwise disjoint: every pair of distinct sets in the sequence is disjoint ($A_i\cap A_j=\varnothing ,\forall i,j\in \{1,2,\dots ,n\},i\ne j$)
Parition of non-empty set $A$: a collection of non-empty subsets of $A$ such that each element of $A$ is in exactly one of the subsets

$A_1,A_2,\dots ,A_n$ is a partition of a non-empty set $A$ if all of the following holds:
$\forall i\in \{1,2,\dots ,n\},A_i\subseteq A$
$\forall i\in \{1,2,\dots ,n\},A_i\ne \varnothing$
$\forall i,j\in \{1,2,\dots ,n\},i\ne j⟹A_i\cap A_j=\varnothing$
$A=\bigcup _{i=1}^n{A}_i$

3.8 Infinite sets

Finite set of $A$: $A$ is empty or if there is a non-negative integer $n$ such that there is a bijection from $A$ to the set $\{1,\dots ,n\}$. Then the cardinality of set $A$ ($|A|$) is $n$.
Infinite set: the set is not finite

NOTE: $f:X\to Y$ means that $f$ is a function with domain $X$ and codomain $Y$. If $f$ is one-to-one and onto, then $f$ is a bijection

A set $A$ has the same cardinality as $B$ if there exists a bijectioin from $A$ to $B$
If $f:X\to Y$ is a bijection, then its inverse $f^{-1}:Y\to X$ is also a bijection. Therefore $|X|=|Y|$

Ex., $E\subset \mathbb{Z}$, but $f(x)=2x$ is a bijection from $\mathbb{Z}$ to $E$, so $|E|=|\mathbb{Z}|$

Injective and surjective:
Ex., to prove $f(x)=2x$ is one-to-one, assume $f(x)=f(y)$. Then $2x=2y$, so $x=y$. Therefore, $f$ is one-to-one.
Ex., to prove $f(x)=2x$ is onto, let $y\in E$. Since $y$ is even, $y=2x$ for some $x\in \mathbb{Z}$. Thus $f(x)=2x=y$. Therefore, $f$ is onto

Countably infinite: there is a bijection from the set of positive integers (${\mathbb{Z}}^{+}$) to a set $A$
Countable: a set $A$ is finite or countably infinite
Uncountable: the set is not countable

Ex., let $S=\{(a,b)\in {\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}:\gcd (a,b)=1\}$. Define $f:S\to {\mathbb{Q}}^{+}$ by $f(a,b)=\frac{a}{b}$. Then $f$ is a bijection

3.9 Uncountable sets

Cantor diagonalization uses proof by contradiction

Assume $f:{\mathbb{Z}}^{+}\to (0,1)$ is a bijection. Let $d_j$ be the $j$-th decimal digit of $f(j)$. Define $x=0.x_1{x}_2\cdots$, where

$$x_j=\{\begin{array}{ll}2,& d_j=1,\\ 1,& d_j\ne 1.\end{array}$$

Then $x\in (0,1)$ and $x\ne f(j)$ for every $j$, since their $j$-th digits differ. Thus $f$ is not onto, a contradiction. Hence $(0,1)$ is uncountable

Theorem 3.9.1: Countability and subsets
Let $A$ and $B$ be two sets such that $A\subseteq B$. If $B$ is countable then $A$ is also countable
Corollary 3.9.1
Let $A$ and $B$ be two sets such that $A\subseteq B$. If $A$ is uncountable then $B$ is also uncountable

The power set of finite set contains elements that are finite sets and elements that are inifinite sets

Assume $f:{\mathbb{Z}}^{+}\to P({\mathbb{Z}}^{+})$ is a bijection. Define

$$S=\{j\in {\mathbb{Z}}^{+}:j\notin f(j)\}.$$

Then $S\in P({\mathbb{Z}}^{+})$. For every $j$, $j\in S$ iff $j\notin f(j)$, so $S\ne f(j)$. Thus $S$ is not in the range of $f$, so $f$ is not onto, a contradiction. Hence $P({\mathbb{Z}}^{+})$ is uncountable