In my opinion it is uncountable since we can think every natural number as a member of one alphabet like $\quad0\in\sum_0 ,1\in \sum_1, ... \quad$ And there are also other symbols than natural numbers in alphabets. So there is no possible 1:1 and onto mapping from set of all alphabets to natural numbers. Thus they cannot be enumerated which means they are uncountable. Is there anything wrong with my approach?

  • 1
    $\begingroup$ It depends on which symbols you allow to be in your alphabets. What is an alphabet for you? $\endgroup$ – Yuval Filmus Mar 22 '17 at 19:26
  • $\begingroup$ In fact I am stuck with that question. In my textbook it is written that any object can be in an alphabet but I could not find anything about the limits of the objects(symbols) we can use in an alphabet. $\endgroup$ – kntgu Mar 22 '17 at 19:35
  • $\begingroup$ Are $\{0, 1\}$, $\{a, b\}$ and $\{c, d\}$ three different alphabets, or just three ways of writing down the two-symbol alphabet? $\endgroup$ – Pontus Mar 22 '17 at 19:44

Your approach can essentially be summarized as:

  1. I define an injection between $\mathbb{N}$ and my set $S$.
  2. This injection is not a bijection because some elements of the codomain are left unmapped.
  3. Therefore there exists no bijection between $\mathbb{N}$ and $S$.

Stated like this, it is perhaps clear that the last statement does not follow from the others. An example of where this reasoning would fail is if we let $S = \mathbb{Z}$ and let the injection be the identity function (mapping naturals to themselves). This leaves all the negative integers in the codomain unmapped, but we know that $\mathbb{Z}$ is countable.

  • $\begingroup$ Thank you...Now I can understand approach I showed was unfounded. I think there is a mapping $\quad f:\mathbb{N}->\mathbb{Z} \quad$ because set of all integers contains some ordering property. But how can we order the objects that will be used in alphabets? Can we order an infinite set with lexicographical ordering? $\endgroup$ – kntgu Mar 22 '17 at 20:01
  • $\begingroup$ @kntgu There is order in most things that we make up, but one may have to look hard to find it. To make your question answerable, you probably have to make it more well-defined. For instance, how many symbols do you have available to make alphabets of, and do you differentiate alphabets with different symbols, but the same size? $\endgroup$ – Pontus Mar 23 '17 at 7:03

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.