Loading...

​​Discussion 6A

​​Cardinality

​​For two sets ​​$A$​ and ​​$B$​, ​​$|A| = |B|$​ if and only if there exists a bijection between ​​$A$​ and ​​$B$​.

​​Examples

• ​​The set ​​$\{ 1, ``a" \}$​ has the same cardinality as the set ​​$\{ ``f", ``g" \}$​

• ​​The set of natural numbers ​​$\mathbb{N}$​ has the same cardinality as the set of even numbers ​​$2 \mathbb{N} = \{ 0, 2, 4, \cdots \}$​

• ​​The set of natural numbers ​​$\mathbb{N}$​ has the same cardinality as the set of positive integers ​​$\{ 1, 2, \cdots \}$​

• ​​The set of natural numbers ​​$\mathbb{N}$​ has the same cardinality as the set of integers ​​$\mathbb{Z}$​

• ​​The set ​​$[0, 1)$​ has the same cardinality as the set ​​$[1, 2)$​

​​

​​You can demonstrate that a bijection exists/that ​​$|A| = |B|$​ by 

• ​​finding a function ​​$f : A \to B$​ for which an inverse ​​$f^{-1} : B \to A$​ exists

• ​​showing both ​​$|A| \leq |B|$​ and ​​$|A| \geq |B|$​ (injection and surjection)

​​Countability

​​A set is countable if its cardinality is less than or equal to that of the natural numbers.

• ​​Sets with a finite number of elements are countable

• ​​Sets that are bijective with ​​$\mathbb{N}$​ are countably infinite

​​If the elements of a set can be listed or enumerated such that any element in the set will appear eventually in the list, then the set is countable.

​​Cartesian Product

​​The Cartesian product of two sets ​​$A$​ and ​​$B$​ is the set of tuples containing elements from ​​$A$​ and ​​$B$​, ​​$A \times B = \{ (a, b) | a \in A \land b \in B \}$​.

• ​​If ​​$A$​ and ​​$B$​ are countable, then ​​$A \times B$​ is countable.

• ​​This is why the set of rational numbers is countable

​​Cantor’s Diagonalization

​​The set ​​$[0, 1)$​ is uncountable.

​​Proof

​​Suppose it is countable. Then we can list all the numbers

​​

​​0	​​0.1343592…
​​1	​​0.1872882…
​​2	​​0.4921423…
​​…	​​…

​​With this list, it turns out there are some real numbers missing. We can construct one, digit by digit. To make it different from the first number, ​​ ​​​$0.1343592 ...$​, we pick a different tenths digit, such as ​​$2$​. To make it different from the second number, ​​$0.1872882...$​, we pick a different hundredths digit, such as ​​$9$​. Continuing down, we construct a real number that is not included in the list, which means we’ve reached a contradiction.

​​So the set ​​$[0, 1)$​ is uncountable, and ​​$\mathbb{R}$​ contains ​​$[0, 1)$​ so it is uncountable as well.

​​The Halting Problem

​​No program can determine whether another program will halt or loop forever.

​​The program TestHalt(P, x) = Yes if P halts for input x, No otherwise​ does not exist.

​​Proof

​​Suppose TestHalt(P, x)​ exists. Then we can define the program

​​Turing(P):

​​    if TestHalt(P, P) = Yes

​​        loop forever

​​    else

​​        exit

​​Then the behavior of Turing(P)​ is to loop forever if P​ called on input P​ halts, and to exit if P​ called on input P​ loops.

​​It turns out that calling Turing(Turing)​ leads to a contradiction. It neither halts nor loops forever.

1. ​​Suppose it loops forever. Then that means the first branch must have been taken in the control flow (if TestHalt(P, P) = Yes​). This means TestHalt(Turing, Turing)​ returns Yes​, so Turing​ halts on input Turing​. Contradiction

2. ​​Suppose it halts. Then that means the second branch must have been taken (if TestHalt(P, P) does not equal Yes​). This means TestHalt(Turing, Turing)​ returns No​, meaning Turing​ loops forever on input Turing​. Contradiction

​​Reductions

​​A problem ​​$A$​ reduces to problem ​​$B$​ if a solution to ​​$B$​ could be used to solve ​​$A$​.

​​If ​​$A$​ reduces to ​​$B$​ then ​​$B$​ is at least as hard as ​​$A$​, i.e. ​​$A$​ could not be solved by the solution to an easier problem; otherwise ​​$A$​ would actually be easier to solve. 

​​