Set Notation

Operations

Cartesian Product

$A\times B$ (pronounced $A$ cross $B$) It is the set of all ordered pairs $(a,b)$, where $a$ is in $A$ and $b$ is in $B$ $A\times B=\{(a,b):a\in A\wedge b\in B\}$ $A_1\times A_2\times \cdots \times A_n$ is the set of all ordered $n$-tuples $(a_1,a_2,\dots ,a_n)$ where $a_1\in A_1,a_2\in A_2\dots$ $A^n=A\times A\times A\dots$ $n$ times Note: $(A_1\times A_2)\times A_3$ is different from $A_1\times A_2\times A_3$

Union

$A\cup B$ is the set of all elements that are in at least one of $A$ or $B$ $A\cup B=\{x\in U:x\in A\vee x\in B\}$

Intersection

$A\cap B$ is the set of all elements that are common to both $A$ and $B$ $A\cap B=\{x\in U:x\in A\wedge x\in B\}$

Union or Intersection of Indexed Collection of Sets

Given sets $A_0,A_1,\cdots ,A_n$ ${\bigcup }_{i=0}^n{A}_i=A_0\cup A_1\cup \cdots \cup A_n$ ${\bigcap }_{i=0}^n{A}_i=A_0\cap A_1\cap \cdots \cap A_n$

Difference (Relative Complement)

$B-A$ or $B\backslash A$ is the set of all elements that are in $B$ but not $A$ $B\backslash A=\{x\in U:x\in B\wedge x\notin A\}$

Complement

$\bar{A}$ or $A^c$ is the set of all elements that are in $U$ that are not in $A$ $\bar{A}=\{x=inU|x\notin A\}$

Partitions

Sets can be divided into mutually disjoint pieces. Such a division is called a partition, which is also a set e.g. $A=\{1,2,3\}$, then $\{\{1\},\{2,3\}\}$ is a partition of $A$ Elements of a partition are called components of the partition Formally, either: $\mathcal{C}$ is a partition of a set $A$ if the following hold

1. $\mathcal{C}$ is a set of which all elements are non-empty subsets of $A$
   • $\varnothing \ne S\subseteq A$ for all $S\in \mathcal{C}$
2. Every element of $A$ is in exactly one element of $\mathcal{C}$
   • $\forall x\in A\exists S\in \mathcal{C}(x\in S)$ and $\forall x\in A\forall S_1,S_2\in \mathcal{C}(x\in S_1\wedge x\in S_2\Rightarrow S_1=S_2)$ or: A partition of set $A$ is a set $\mathcal{C}$ of non-empty subsets of $A$ such that $\forall x\in A\exists !S\in \mathcal{C}(x\in S)$ (note: $\exists !$ means there exists a unique)

Power Sets

$\mathcal{P}(A)$ is the set of all subsets of $A$. It includes $\varnothing$ $\mathcal{P}(\{1,2\})=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$ Cardinality of power set: $|A|=n$, then $|\mathcal{P}(A)|=2^n$

Representing Sets

Set Roster Notation

Write all elements between braces Order and duplicates do not matter $\{1,2,3\}$

Set Builder Notation

the set of all $x$ in $A$ such that $P(x)$ is true: $\{x\in A|P(x)\}$ or $\{x\in A:P(x)\}$

Replacement Notation

The set of all $t(x)$ where $x\in A$: $\{t(x)|x\in A\}$ or $\{t(x):x\in A\}$

Interval Notation

Notation for subsets of real numbers that are intervals $(a,b]=\{x\in \mathbb{R}:a<x\le b\}$

Comparing Sets

Subset

$A$ is a subset of $B$, every element of $A$ is also an element of $B$ $A\subseteq B$

Proper Subset

$A$ is a proper subset of $B$ if $A\subseteq B$ AND $A\ne B$ $A⊊B$

Others

Cardinality of a Set

$|S|$ denotes the cardinality of a set The number of elements in the set e.g. $|\{a,b,c\}|=3$

Membership

$x\in S$ means $x$ is an element of $S$ $x\notin S$ means $x$ is not an element of $S$

Empty Set

Set containing no elements is $\varnothing$ NOTE: For all sets $A$, $\varnothing \subseteq A$

Singleton

A set with exactly one element

Disjoint

Disjoint: $A\cap B=\varnothing$ Mutually Disjoint: for $A_1,A_2,...$ : For $i\ne j,A_i\cap A_j=\varnothing$

Set of Equivalence Classes

For set $A$ and equivalence relation $\sim$ on $A$, the set of all equivalence classes with respect to $\sim$ is denoted $A/\sim$ (“the quotient of $A$ by $\sim$“) $A/\sim =\{[x{]}_{\sim }:x\in A\}$ see Equivalence Relations