Set

A set is a well-defined, unordered collection of distinct objects. Each object that appears in this collection is called an element (or member) of the set.

Examples (using set enumeration):

1. $\{2,4,6,8\}$
2. $\{1,2,\{1,2,3\}\}$ is a set that contains three elements.

Empty Set

The set $\{\}$ contains no elements and is known as the empty set. We often use $\varnothing$ as the symbol.

Remark: $\{\varnothing \}\ne \varnothing$ Cardinality of $S$: Number of elements in a finite set $S$, denoted by $|S|$ Ex: $|\{2,4,6,8,10\}|=5$

Set-builder Notation (Set Comprehension)

The idea is to define a set using a predicate; in particular, the set consists of all values that make the predicate true.

$B=\{x\in \mathbb{R}\mid x^3-3x+1>0\}$

Set Operations

Union

The union of two sets $S$ and $T$, written $S\cup T$, is the set of all elements belonging to either set $S$ or set $T$ (or both). Symbolically we write $S\cup T=\{x:x\in S\text{OR}x\in T\}=\{x:(x\in S)\vee (x\in T)\}$

Intersection

The intersection of two sets $S$ and $T$, written $S\cap T$, is the set of all elements belonging to both set $S$ and set $T$. Symbolically we write

$S\cap T=\{x:x\in S\text{AND}x\in T\}=\{x:(x\in S)\wedge (x\in T)\}$

Set-difference

The set-difference of two sets $S$ and $T$, written $S-T$ (or $S\setminus T$), is the set of all elements belonging to set $S$ but not $T$. Symbolically we write

$S-T=\{x:x\in S\text{AND}x\notin T\}=\{x:(x\in S)\wedge (x\notin T\})$

Complement

The complement of a set $S$, written $\overline{S}$, is the set of all elements not in $S$. Symbolically we write

$\overline{S}=\{x:x\notin S\}$

Prove Subset

To prove that $S\subseteq T$, prove the universally quantified implication: $\forall x\in U,(x\in S)⟹(x\in T)$

Prove Equal Subsets

To prove that $S=T$, we prove that $S\subseteq T$ and $T\subseteq S$.

SE212

Axioms

Types as sets: if $\exists x\cdot x\in B$ $(\forall x:B\cdot P(x))⟺(\forall x\cdot x\in B⟹P(x))$ $(\exists x:B\cdot P(x))⟺(\exists x\cdot x\in B\wedge P(x))$

Set Comprehension $x\in \{y\cdot y:S\mid P(y)\}⟺x\in S\wedge P(x)$ $x\in \{f(y)\cdot y:S\mid P(y)\}⟺\exists y\cdot y\in S\wedge P(y)\wedge (x=f(y))$

Empty Set $\forall x\cdot \neg (x\in \varnothing )$

Universal Set The universal set consists of all the values of concern in any discussion (domain) $\forall x\cdot x\in U$

Set Equality $D=B⟺(\forall x\cdot x\in D⟺x\in B)$ $D=B⟺D\subseteq B\wedge B\subseteq D\text{(Derived Law for Set Equality)}$

Subset $D\subseteq B⟺(\forall x\cdot x\in D⟹x\in B)$

Proper Subset $D\subset B⟺D\subseteq B\wedge \neg (D=B)$

Power Set The power set of a set is the set of all of its subsets. $\mathbb{P}(\cdot )$ is the function that returns the power set of a set.

$\mathbb{P}(D)=\{B\mid B\subseteq D\}$

Other

A singleton set is a set consisting only of one element.

Axioms for Set Functions

Set Union $A\cup B=\{x\mid x\in A\vee x\in B\}$ Set Intersection $A\cap B=\{x\mid x\in A\wedge x\in B\}$

Two sets, $A$ and $B$, are disjoint if their intersection is empty, i.e. $A\cap B=\varnothing$ . Serendipity → Disjoint Set Union

Absolute Complement $U$ is the universal set. $compl(A)=\{x\mid x\in U\wedge \neg (x\in A)\}$ $compl(A)=\{x\mid \neg (x\in A)\}$

Set Difference $A-B=\{x\mid x\in A\wedge \neg (x\in B)\}$ Note that for set difference, the order of operands MATTERS, i.e. $A-B\ne B-A$

For example, let , $X=\{a,b,c\}$ and $Y=\{a,c,e\}$.

• $X-Y=\{b\}$
• $Y-X=\{e\}$

Cartesian product (Set Product) $C\ast B=\{(c,b)\mid c\in C\wedge b\in B\}$

Also see Binary Relation for the list of other properties.

See Transformational Proof on Transformational Proof on Set Theory.

Related

• Set for using them in programming