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 ${𝒫}(A)$ denotes the power set (i.e. ${𝒫}(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: $|{𝒫}(X)|=|2^X|$ since the bijection is given by the characteristic function:

1. $\mathrm{\varnothing }\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|\le |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|<|{𝒫}(S)|$

Proof

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

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

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

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

• $s\in T⟹s\in ̸f(s)$ by definition of $T$, so $T\ne f(s)$.
• $s\in ̸T⟹s\in f(s)$ by definition of $T$, so $T\ne f(s)$.

Therefore

$f$

is not surjective. This proves the claim.

Q.E.D.

Countable Sets

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

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

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

An Uncountable Set

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

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

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

$|\mathbb{\mathbb{N}}|<|{𝒫}(\mathbb{\mathbb{N}})|=|2^{\mathbb{\mathbb{N}}}|\le |{\mathbb{\mathbb{N}}}^{\mathbb{\mathbb{N}}}$

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