CSCE 222 Lecture 32

« previous | Monday, April 25, 2011 | next »

More about cardinality

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A| \le |B|} iff injective function from A to B.

Cantor's Theorem

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |S| < |P(S)|}

Function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i: S \to P(S)} given by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i(s) = \{s\}} is injective, therefore Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |S| \le |P(S)|}

Claim that there does not exist any surjective function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f: S \to P(S)}

Indeed, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = \{s \in S: s \notin f(s) \}} is not contained in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(S)}

Countability vs. Uncountability

A set X is countable iff Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |X| \le |\mathbb{N}|}

Function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f: \mathbb{N} \to \mathbb{N}} is not countable since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{N}| < |P(\mathbb{N})|} , which is equivalent to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{N}| < |2^{\mathbb{N}}|} Therefore, the function's cardinality is not countable

Diagonalization

Given a function that maps an input to a given value, define a function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^d(n) = f_n(n)+1} , therefore Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^d(n) \ne f_n(n)}

The Halting Problem

Input for Halt program: Program P and input X for P Output: 1 if P terminates (halts) when executed on X, and 0 if P goes into an infinite loop on input X.

Note: A compiler is a program that takes as input the code for another program.

X could be the program for P itself.

What if we call Halt(P, P) and modify it a little? (diagonalize) This result leads to a paradox and is undecidable.

bool halt(Program P, void* Input X)
  if (P.run(X).terminates()) return true;
  else return false;
}

bool pSelf(Program P) {
  return halt(P,P)
}

bool pDiag(Program P) {
  if (pSelf(P)) while(true) {}
  else return false;
}

???

If an input from Language 1 returned YES for the Halting problem, than a slight modification (Language 2) must also return YES

Functional property: a property that refers to the language accepted by the program and not the specific code of the program.

EX: Program terminates in 10 steps: (not functional); the program accepts 0 or more inputs (functional).

Nontrivial property: functional property about programs if some programs have the property and some do not.

Rice's Theorem

Every nontrivial functional property about programs is undecidable.