CSCE 411 Lecture 34

Lecture Slides

« previous | Friday, November 16, 2012 | next »

Homework 9 posted on course web page (read through all textbook NPC problems carefully)

Undecidability

Models of Computation

Clearly and unambiguously specify how computation takes place.

• Turing machines
• Random Access machines (more realistic, but with infinite memory)
• ...

They are all equivalent!

Church-Turing Thesis

Anything we reasonably think of as an algorithm can be computed by a Turing Machine

Set Theory Concepts

If $A$ and $B$ are sets, then the set of all functions from $A$ to $B$ is denoted by $B^{A}$.

If $A$ is a set, then ${\mathcal {P}}(A)$ denotes the power set (i.e. ${\mathcal {P}}(A)$ is the set of all subsets of $A$)

Cardinality

Two sets $A$ and $B$ are said to have the same cardinality iff there exists a bijective function from $A$ onto $B$. (See CSCE 222 Lecture 11 and MATH 302 Lecture 8#Function)

How do set theorists count?

• $0=\{\}$
• $1=\{0\}=\{\{\}\}$
• $2=\{0,1\}=\{\{\},\{\{\}\}\}$
• Keep including all previously created sets as elements of the next set

Power set cardinality: $|{\mathcal {P}}(X)|=|2^{X}|$ since the bijection is given by the characteristic function:

1. $\emptyset \mapsto f(a)=f(b)=0$
2. $\{a\}\mapsto f(a)=1,f(b)=0$
3. $\{b\}\mapsto f(a)=0,f(b)=1$
4. $\{a,b\}\mapsto f(a)=f(b)=1$

We say $|A|\leq |B|$ if there is an injective function from $A$ to $B$

We say $|A|<|B|$ if there is no biective function from $A$ to $B$

Cantor's Theorem

Let $S$ be any set. Then $|S|<|{\mathcal {P}}(S)|$

Proof

Since function $i$ from $S$ to ${\mathcal {P}}(S)$ given by $i(s)=\{s\}$ is injective, we have $|S|\leq |{\mathcal {P}}(S)|$.

Claim. There does not exist any function $f$ from $S$ to $P(S)$ that is surjective.

$T=\{s\in S~:~s\not \in f(s)\}$ is not contained in $f(S)$.

An element $s\in S$ is either contained in $T$ or not:

• $s\in T\implies s\not \in f(s)$ by definition of $T$, so $T\neq f(s)$.
• $s\not \in T\implies s\in f(s)$ by definition of $T$, so $T\neq f(s)$.

Therefore $f$ is not surjective. This proves the claim.

Q.E.D.

Countable Sets

Let $\mathbb {N}$ be the set of natural numbers.

A set $X$ is called countable iff there exists a surjective function from $\mathbb {N}$ onto $X$.

Thus finite sets are countable, $\mathbb {N}$ is countable, but the set of real numbers is not countable.

An Uncountable Set

The set $\mathbb {N} ^{\mathbb {N} }=\{f~\mid ~f:\mathbb {N} \to \mathbb {N} \}$ is not countable.

Proof. We have $|\mathbb {N} |<|{\mathcal {P}}(\mathbb {N} )|$ by Cantor's theorem.

Since $|{\mathcal {P}}(\mathbb {N} )|=|2^{\mathbb {N} }|$ and $2^{\mathbb {N} }$ is a subset of $\mathbb {N} ^{\mathbb {N} }$ we can conclude that

$|\mathbb {N} |<|{\mathcal {P}}(\mathbb {N} )|=|2^{\mathbb {N} }|\leq |\mathbb {N} ^{\mathbb {N} }$

The cardinality of computer programs is countable ($|\mathbb {N} |$), but the cardinality of problems is not ($|\mathbb {N} ^{\mathbb {N} }|$)