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 lNon-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