Sets

Definition

Sets are an unordered collection of objects.

When we say $a\in A$ we mean $a$ in/belongs to $A$.

Roster Method

When you list out every object, similar to a literal sports roster.

i.e.:

$V=\{a,e,i,o,u\}$ > $E=\{2,4,6,8,\dots ,98\}$

Set Builder

$O=\{x|x\text{is odd and }x<10\}$ "$x\text{is odd and }x<10$" is referred to as the predicate.

Notation

If we say ”$A$ is a subset of $B$” or that ”$B$ is a superset of $A$,” we are saying

$(\forall x|x\in A:x\in A\to x\in B)$

Theorem

for every set $S$

1. $\varnothing \le S$
2. $S\le S$

Proof:

let $S$ be a set.

1. We need to show that $\varnothing \le S$. In other words, for an arbitrary $x$, if $x\in \varnothing$, we must show that $x\in S$. However, $\varnothing$ is the empty set $\therefore x\in \varnothing$ is false. $\therefore$ Vacuously, if $x\in \varnothing \to x\in S$ is true, $\therefore \varnothing \le S$
2. We need to show that $S\le S$. We need to show that for every element in $S$ if $x\in S\to x\in S$, $x\in S$ is always true. $\therefore$ $x\in S$ is always true. $\therefore S\le S$

Definitions of Sets

Natural Numbers

$De{f}^n$: The set of natural numbers is defined to be

$\mathbb{N}=\{0,1,2,3,\dots \}$

Note that $0$ exists in this set. This is debated heavily, but for the purposes of this class, we assume it is a natural number.

Integers

$De{f}^n$: The set of integer numbers is defined to be

$Z=\{\dots ,-2,-1,0,1,2,\dots \}$

Rationals

$De{f}^n$: The set of rational numbers is defined to be $Q=\{\frac{p}{q}|p\in z\wedge q\in z\wedge q\ne 0\}$

Real

$\mathbb{R}$

Empty Set/Null Set

Is simply $\{\}$ or $\varnothing$

Singleton Set

A set with exactly one element.

$\{\varnothing \}$: singleton (we are saying that we have a Set with a null set within it)

U: Universal

Refers to all the elements that are in the currently referenced scope.

Ordered $n$-tuple

$De{f}^n$: $(a_1,a_2,\dots ,a_n)$ is an ordered collection of $n$ objects.

Note that there are parentheses instead of curly brackets. When this is the case, order does matter.

$(a_1,a_2,\dots ,a_n)=(b_1,b_2,\dots ,b_n)$ as long as

$$\begin{array}{r}{a}_1=b_1\\ a_2=b_2\\ ⋮\\ a_n=b_n\end{array}$$

If $n=2$, then we have an ordered pair.

Union

$A\cup B$ is defined as

$x\in A\vee x\in B$

Intersection

$A\cap B$

is defined as $x\in A\wedge x\in B$

Difference

$A-B$ is defined as

$x\in A\wedge \neg x\in B$

Complement

$\overline{A}\text{or}{A}^{\complement }$ is defined as

$x\in U\wedge \neg x\in A$ Complement of $B$ with respect to $A$ is the difference

Set Identities

Cardinality of Combined Sets (Principle of Inclusion-Exclusion)

$|A\cup B|=|A|+|B|-|A\cap B|$

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$

$$|A\cup B\cup C\cup D|=|A|+|B|+|C|+|D|-|A\cap B|-|B\cap C|-|C\cap D|-|C\cap D|-|A\cap B|-|A\cap C|+|A\cap B\cap C|+|A\cap C\cap D|+|B\cap C\cap D|+|A\cap B\cap D|-|A\cap B\cap C\cap D|$$

$A_1\cup A_2$

$\bigcup _{i=1}^n{A}_i$

Link to original