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{array}{rl}A-B& =\{x|x\in A\wedge x\notin B\}\\ & =\{x\in A|x\notin B\}\end{array}$

Let $U$ be a universal set.

Let $A\subseteq U$, then $\overline{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{\mathbb{N}}\to \mathbb{ℝ}|f(n)=O(g(n))\}$ ?

$=\{f:\mathbb{\mathbb{N}}\to \mathbb{ℝ}|\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\exists }C>0\mathrm{\forall }n\ge n_0:|f(n)|\le 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\to B$:

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

Example

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

$\begin{array}{rl}range& =\{0,1,4,9,16,\dots \}\\ & =\{y\in \mathbb{\mathbb{Z}}|\mathrm{\exists }x\in \mathbb{\mathbb{Z}}:y=x^2\}& =\{y\in {\mathbb{\mathbb{N}}}_0|\text{y is a perfect square}\}\end{array}$

Injective Functions

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

Surjective Functions

Range of A is B