# 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):

- ${2,4,6,8}$
- ${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 $β$ as the symbol.

Remark: ${β}ξ=β$
*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βRβ£x_{3}β3x+1>0}$

### Set Operations

Union

The

unionof two sets $S$ and $T$, written $SβͺT$, is the set of all elements belonging to either set $S$ or set $T$ (or both). Symbolically we write $SβͺT={x:xβSΒORΒxβT}={x:(xβS)β¨(xβT)}$

Intersection

The

intersectionof two sets $S$ and $T$, written $Sβ©T$, is the set of all elements belonging to both set $S$ and set $T$. Symbolically we write$Sβ©T={x:xβSΒANDΒxβT}={x:(xβS)β§(xβT)}$

Set-difference

The

set-differenceof two sets $S$ and $T$, written $SβT$ (or $SβT$), is the set of all elements belonging to set $S$ but not $T$. Symbolically we write$SβT={x:xβSΒANDΒxβ/T}={x:(xβS)Ββ§Β(xβ/T})$

Complement

The

complementof a set $S$, written $S$, is the set of all elements not in $S$. Symbolically we write$S={x:xβ/S}$

### Prove Subset

To prove that $SβT$, prove the universally quantified implication: $βΒxβU,(xβS)βΉ(xβT)$

### Prove Equal Subsets

To prove that $S=T$, we prove that $SβT$ and $TβS$.

### SE212

#### Axioms

Types as sets: if $βxβxβB$ $(βx:BβP(x))βΊ(βxβxβBβΉP(x))$ $(βx:BβP(x))βΊ(βxβxβBβ§P(x))$

**Set Comprehension**
$xβ{yβy:Sβ£P(y)}βΊxβSβ§P(x)$
$xβ{f(y)βy:Sβ£P(y)}βΊβyβyβSβ§P(y)β§(x=f(y))$

**Empty Set**
$βxβΒ¬(xββ)$

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

**Set Equality**
$D=BβΊ(βxβxβDβΊxβB)$
$D=BβΊDβBβ§BβD(DerivedΒ LawΒ forΒ SetΒ Equality)$

**Subset**
$DβBβΊ(βxβxβDβΉxβB)$

**Proper Subset**
$DβBβΊDβBβ§Β¬(D=B)$

**Power Set**
The power set of a set is the set of all of its subsets. $P(β)$ is the function that returns the power set of a set.

$P(D)={Bβ£BβD}$

#### Other

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

#### Axioms for Set Functions

**Set Union**
$AβͺB={xβ£xβAβ¨xβB}$
**Set Intersection**
$Aβ©B={xβ£xβAβ§xβB}$

Two sets, $A$ and $B$, are disjoint if their intersection is empty, i.e. $Aβ©B=β$ . Serendipity -> Disjoint Set Union

**Absolute Complement**
$U$ is the universal set.
$compl(A)={xβ£xβUβ§Β¬(xβA)}$
$compl(A)={xβ£Β¬(xβA)}$

**Set Difference**
$AβB={xβ£xβAβ§Β¬(xβB)}$
Note that for set difference, the order of operands MATTERS, i.e. $AβBξ=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βB={(c,b)β£cβCβ§bβ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