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

a_1=b_1 \\ a_2=b_2 \\ \vdots \\ a_n=b_n \end{align}$$ 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\limits_{i=1}^{n}A_i$ ## Functions ### Increasing/Decreasing Functions if $x<y$ then $f(x)\leq f(y)$ this is increasing $f(x)<f(y)$ this is strictly increasing if $x>y$ then $f(x)\geq f(y)$ this is decreasing if $x>y$ then $f(x)>f(y)$ this is strictly decreasingLink to original