Question

Q3 Let A = {a,b,c} and Aº = {abcw1W2 ---W | W; E A for all i > 1} denote the set of all infinite length strings over A that start with the “abc" substring. That is, each string A™ is an infinite sequence of characters "abcw1W2 ... Wo" where each wie A. Prove that Aº is not countable using a proof by contradiction that includes a diagonalization argument.

Answer 1

A= {a,b,c} & A² = {abcw, wy... waf we c A viss} Suppose A® be countable. Let us enumerate Ao abc wi w sw ... was abc we we? W... was abc ww w... Wao ... distinct : صلحا now construct another abcãū ūg... W. where Wat wh and so on. in the in the nth oth Thus abe, w, wo ... Wat is different from string abc w hwn w... who entry of string (counted from @ thus this string not in the list above abus A cannot countable: is be