Sets of problems in different models of computation and cardinality

Question

In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg

Essentially, Pushdown Automata (PDA) can solve more problems (i.e. recognize more languages) than Finite State Machines (FSM), Turing machines (TM) can solve more problems than PDA etc. To continue, suppose $s(FSM), s(PDA), s(TM)$ denotes the set of problems solved by FSMs, PDAs and TMs, respectively. Then, the figure states that: $s(FSM) \subset s(PDA) \subset s(TM)$

However, I have a confusing argument regarding the cardinality of the above sets.

1. All sets of computational models (e,g, FSMs, PDAs and TMs) are countably infinite. Because all can be represented as computer programs in binary string form, which are also countably infinite.
2. If FSMs are countably infinite, then the problems that can be solved with FSMs, $s(FSM)$, cannot be more than countably infinite. The same is true for $s(PDA)$ and $s(TM)$.
3. Countably infinite sets have cardinal number $\aleph_0$ (aleph zero). Thus if $C(.)$ denotes cardinality, $C(s(FSM)) = C(s(PDA)) = C(s(TM)) = \aleph_0$.

Is the above argument correct? If it is true and the above sets have the same cardinality, in what sense is the figure (which states that $s(FSM) \subset s(PDA) \subset s(TM)$ true?

The only hypothesis I can think of is an argument of "redundancy". That is that while there is an equal number of TMs and FSMs, the same is not true for the problems that can be solved with these. That would mean that that many FSMs solving the exact same problem is common, while many TMs solving the same problem is less frequent. Thus, more problems can be solved with TMs than can be with FSMs. Stated differently, the set of problems solved by TMs is greater than the problem set solved by FSMs. However, both problem sets are infinite and there is no infinity smaller than $\aleph_0$, so the two problems sets should have the same cardinality $\aleph_0$

Answer 1

Cardinality is a Weak Property

As described in the question, cardinality is a very weak property. It is not strong enough to distinguish $s(FSM)$, $s(PDA)$, $s(TM)$. It cannot differentiate any two different sets that are both countably infinite.

That is not surprising at all.

For example, we know that $$\mathbb N\subsetneq(\mathbb N\cup\{-1\})\subsetneq\mathbb Z\subsetneq\mathbb Q\subsetneq\mathbb Q(\sqrt2).$$ However, $$C(\mathbb N)= C(\mathbb N\cup\{-1\}) = C(\mathbb Z) = C(\mathbb Q)=C(\mathbb Q(\sqrt2))=\aleph_0.$$

the Meaning of $s(FSM) \subsetneq s(PDA) \subsetneq s(TM)$

Fix any alphabet $\Sigma$ such as $\{0,1\}$ or $\{a,b,c\}$. Let $s(FSM)=s_\Sigma(FSM)$ be the set of regular languages over $\Sigma$. Similarly, $s(PDA)$ be the set of context-free languages over $\Sigma$ and $s(TM)$ be the set of computably-enumerable languages over $\Sigma$. Then $s(FSM) \subsetneq s(PDA) \subsetneq s(TM)$.

In case you are not satisfied with a fixed alphabet, we can switch to different definitions. Let $\Sigma_1\subset\Sigma_2\subset\cdots$ be a sequence of alphabets. (Each alphabet is still finite.) Let $s(FSM)=s_{\Sigma_1}(FSM)\cup s_{\Sigma_2}(FSM)\cup s_{\Sigma_1}(FSM)\cup\cdots$. Define $s(PDA)$ and $s(TM)$ similarly. Then we still have $s(FSM) \subsetneq s(PDA) \subsetneq s(TM)$.

"That would mean that that many FSMs solving the exact same problem is common, while many TMs solving the same problem is less frequent..." It might be better not to consider that kind of logic, which is basically trying to compare $\infty/\infty$ with another $\infty/\infty$, where we have four different infinities. (In fact, my intuition indicates the other way. For example, it is decidable whether two FSMs solve the same problem while it is undecidable whether two TMs solve the same problem.)