size of infinite strings and infinite alphabets

Question

Please forgive the lack of formal vocabulary.

Which set has a larger cardinality?

A) a set of all possible countably infinite strings with a finite alphabet of symbols.

B) a set of all possible finite strings with a countably infinite alphabet of symbols.

(And in case this is needed, the order of symbols matters, and repetition is allowed (otherwise A will have problems) )

*And another question in reply to a comment by Element118. Is B the same size as the the set of positive integers? I would guess that B is larger than the set of integers because the subset of B containing all strings with only one symbol would completely match-up with the integers, leaving all the other subsets of finite strings free from a one-to-one correspondence.

Answer 1

I like the question.

But the answer is simple and well known.

A) has cardinality $n^{\aleph_0} = 2^{\aleph_0}$ which is uncountable

B) has isomporphic to $Z\times....Z$ which has a 1-1 corespondence to Z which is countable.

A) has examples in infinite decimal expansions (which describe the reals) and formalized by $X_{i\in \mathbb N}[0,1]$ infinite length 2-ples which can be shown by Cantor's diagonal to be uncountable.

Meanwhile B) is the cross product of countable sets which, like the diagonal ordering of the rationals, can be shown to be countable.

Answer 2

You've found an injection from $\mathbb{N}$ to $B$ which misses "most" of $B$; however, this sort of intuition can be very misleading. For example, the map $x\mapsto x^2$ is a map from $\mathbb{N}$ to $\mathbb{N}$ which misses "most" of $\mathbb{N}$, but clearly $\mathbb{N}$ is not smaller than itself!

Indeed, $B$ is countable - consider the map $F$ from $\{$finite sequences of naturals$\}$ to $\mathbb{N}$ given by $$F(\langle a_1, . . . , a_n\rangle)=2^{a_1}3^{a_2}...p_n^{a_n}$$ (where $p_n$ denotes the $n$th prime).

$A$, by contrast, has the same cardinality as $\mathbb{R}$ (as long as you have at least $2$ symbols - with only $1$ symbol, $A$ is of course countable). This is a good exercise (hint: base-$n$ expansions . . .).