Q:

Inequivalent Sequences of Positive Integers

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?

A:

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).

