Let $A$ and $B$ be two sequences of positive integers. We say $A$ and $B$ are inequivalent if whenever a finite initial sequence is removed from $A$ and whenever a finite initial sequence is removed from $B$, the resulting two sequences $A'$ and $B'$ are not identical. I want to show that the set consisting of all sequences which are pairwise inequivalent is uncountable. I thought the Cantor approach of assuming we have a sequence of such sequences and changing the diagonal would work, but adding the condition of pairwise inequivalence seems to throw that off. I'm sure this is pretty obvious but I'm just not seeing it right now. Can anyone offer a hint?

  • $\begingroup$ What is the base case for "inequivalent"? I'm sure it's the obvious "this set does not equal that set", but it should be explicit in a definition. $\endgroup$ – abiessu May 22 at 1:39
  • $\begingroup$ For example, {1, 1, 1, ...} and {2, 2, 2, ...} are inequivalent, while {1, 2, 3, 4, 5, 6, 7, 8, 9, ...,} and {1, 2, 4, 5, 6, 7, 8, 9, ...} are not. $\endgroup$ – gorzardfu May 22 at 1:48

Given an integer sequence $A$, the number of integer sequences equivalent to $A$ is countable (I'll leave this to you as an exercise). So if the number of equivalence classes were countable, then the total number or integer sequences would be a countable union of countable sets. Try to use this to get a contradiction (you can use Cantor's diagonal argument to show that the total number of integer sequences is uncountable).

  • $\begingroup$ Thanks! I had the same thought earlier about thinking about an equivalence class containing a given sequence, but I didn't follow it deeply enough. Knew it wasn't hard, thanks! $\endgroup$ – gorzardfu May 22 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.