A Example Uncountable Set Proof o suppose R is countable o list r according to the bijection f: n f(n 13.14159 25.55555. 30.12345 40.50000
Example Uncountable Set ◼ Proof: suppose R is countable list R according to the bijection f: n f(n) _ 1 3.14159… 2 5.55555… 3 0.12345… 4 0.50000… …
A Example Uncountable Set Proof o suppose R is countable o list r according to the bijection f: set X=0. a1a2a3a4 13.14159 where digit a; t ith digit after decimal 25.55555 point of f((not 0, 9) eg.x=02312. 30.12345 x cannot be in the list 40.50000
Example Uncountable Set ◼ Proof: suppose R is countable list R according to the bijection f: n f(n) _ 1 3.14159… 2 5.55555… 3 0.12345… 4 0.50000… … set x = 0.a1a2a3a4… where digit ai ≠ i th digit after decimal point of f(i) (not 0, 9) e.g. x = 0.2312… x cannot be in the list!
Non-RE Languages Theorem: there exist languages that are not Recursively enumerable Proof outline o the set of all tms is countable o the set of all languages is uncountable o the function L: TMS)languages cannot be onto
Non-RE Languages Theorem: there exist languages that are not Recursively Enumerable. Proof outline: the set of all TMs is countable the set of all languages is uncountable the function L: {TMs} →{languages} cannot be onto
Non-RE Languages Lemma the set of all tms is countable Proof o the set of all strings 2* is countable for a finite alphabet 2. With only finitely many strings of each length, we may form a list of 2* by writing down all strings of length 0, all strings of length 1, all strings of length 2, etc o each tM M can be described by a finite-length string s <M> o Generate a list of strings and remove any strings that do not represent a TM to get a list of TMs
Non-RE Languages ◼ Lemma: the set of all TMs is countable. ◼ Proof: the set of all strings * is countable, for a finite alphabet . With only finitely many strings of each length, we may form a list of * by writing down all strings of length 0, all strings of length 1, all strings of length 2, etc. each TM M can be described by a finite-length string s <M> Generate a list of strings and remove any strings that do not represent a TM to get a list of TMs
Non-RE Languages Lemma: the set of all languages is uncountable Proof o fix an enumeration of all strings S,, S2, S3 (for example, lexicographic order) o a language L is described by its characteristic vector xu whose ith element is0 if s: is not in l and 1 if s; is in l
Non-RE Languages ◼ Lemma: the set of all languages is uncountable ◼ Proof: fix an enumeration of all strings s1 , s2 , s3 , … (for example, lexicographic order) a language L is described by its characteristic vector L whose ith element is 0 if si is not in L and 1 if si is in L