CSCE 222 Lecture 10

« previous | Friday, February 11, 2011 | next »

Truth Sets

Let $P$ be a predicate with domain $D$.

The set of all elements x in D such that P(x) is true is denoted by:

$\{x\in D|P(x)\}$

Set operations

${\begin{aligned}A-B&=\{x|x\in A\wedge x\notin B\}\\&=\{x\in A|x\notin B\}\end{aligned}}$

Let $U$ be a universal set.

Let $A\subseteq U$, then ${\bar {A}}=U-A$

Fun with Sets

(Oh boy!)

Suppose that $A$ and $B$ are finite sets.

How many elements are in their union?

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

Big O — Redefined

Big O is actually a set of all functions asymptotically less than a given function (read as a subset of O(n)) What is the set $\{f:\mathbb {N} \rightarrow \mathbb {R} |f(n)=O(g(n))\}$ ?

$=\{f:\mathbb {N} \rightarrow \mathbb {R} |\exists n_{0}\in \mathbb {N} \exists C>0\forall n\geq n_{0}:|f(n)|\leq C|g(n)|\}$

Functions

Let $A$ and $B$ be nonempty sets. A function $f$ that maps from $A$ to $B$ is an assignment of exactly one element of $B$ to each element of $A$.

$f:A\rightarrow B$:

• $A$ is domain (input type)
• $B$ is codomain (output type; superset of range)
• $\{f(a)|a\in A\}$ is range

Example

$f:\mathbb {Z} \rightarrow \mathbb {Z} ,\ f(x)=x^{2}$

${\begin{aligned}range&=\{0,1,4,9,16,\ldots \}\\&=\{y\in \mathbb {Z} |\exists x\in \mathbb {Z} :y=x^{2}\}&=\{y\in \mathbb {N} _{0}|{\mbox{y is a perfect square}}\}\end{aligned}}$

Injective Functions

Function is one-to-one (A maps uniquely to B)

Surjective Functions

Range of A is B