Define the characteristic sequence of a set A C Z+ to be the following infinite binary sequence, XA-bib2bz... . whose nth bit is 1 if n E A Write XA for the first n bits of xA Prove: For every decidable set A C z+ there is a constant c E N such that, for all nEz, CaAn) logn+c A,T Define the characteristic sequence of a set A C Z+ to be the following infinite binary sequence, XA-bib2bz... . whose nth bit is 1 if n E A Write XA for the first n bits of xA Prove: For every decidable set A C z+ there is a constant c E N such that, for all nEz, CaAn) logn+c A,T