3
$\begingroup$

Is the set of all strings of finite length $\Sigma^*$ from a infinite alphabet $\Sigma$ uncountable?

The usual procedure in these types of proof is that you

list strings of length 1 list strings of length 2 list strings of length 3 .......  .......  ....... and so on 

But now even the first line has infinite length so the construction can never stop. What is wrong?

  • 4
    Assuming the Axiom of Choice, the set of finite strings from an infinite alphabet has the same cardinality as the alphabet. But your method does not work, because the first "list" never ends, so you never get to the the list of strings of length 2. To show countability in the countable sense, well-order the alphabet, list words of the same length lexicographically, and then imitate the proof that the positive rationals are countable.2012-02-09
  • 0
    @Arturo Magidin if the alphabet was finite then my method would work right?2012-02-09
  • 1
    Yes, it would: in that case each line of your table would be finite.2012-02-09
  • 0
    hi could someone please help me out with this proof. Iam stuck ? :(. Help is greatly appreciated.2012-02-09
  • 2
    @Arturo: You actually don't need the axiom of choice at all here. If the alphabet is countable then without the axiom of choice you can show that the finite strings form a countable set; if the set was not countable to begin with... well, the result will not be countable.2012-02-10
  • 0
    @Asaf: Right; my caveat came from thinking about the assertion that "the set of finite strings has the same cardinality as the alphabet" in the infinite case. I agree on the countable case. But the proof I know for the general case uses a lot of cardinal arithmetic, and you've taught me to be careful in asserting it holds without AC. Does the general case of *equal cardinality* hold regardless of AC?2012-02-10
  • 0
    @Arturo: Indeed to show that the cardinality is *the same* requires and even implies the axiom of choice; however in here we are merely arguing countability vs. uncountability. In this aspect there is a very obvious map from the alphabet into the finite strings which ensures us that if the alphabet was uncountable then the finite strings are uncountable.2012-02-10
  • 0
    @Asaf: Okay, so my statement is correct, since the clause "Assuming the Axiom of Choice" is modifying "the set of finite strings form an infinite alphabet has the same cardinality as the alphabet." (-:2012-02-10
  • 0
    @Arturo: Of course, my remark was merely to suggest that the axiom of choice is not required to show countability or uncountability of this set, since deciding whether or not this set is countable can be deduced directly from the cardinality of the alphabet. If you want to calculate the cardinality the axiom of choice will indeed be useful. :-)2012-02-10

4 Answers 4