效绵 Example Uncountable Set ■Proof: suppose R is countable 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… …
效绵 Example Uncountable Set ■Proof: suppose R is countable list R according to the bijection f: f(n) set x 0.a azaga4... 13.14159. where digit a#ith digit after decimal 25.55555.. point of f(i)(not 0,9) e.g.×=0.2312. 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: the set of all TMs is countable the set of all languages is uncountable the function L:{TMslanguages} 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: 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 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: fix an enumeration of all strings s,s2,S3,... (for example,lexicographic order) 0 a language L is described by its characteristic vector XL whose ith element is 0 ifs;is not in L and 1 ifs: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