$\color{red}{\text{Detailed Video Solution, with Proof:}}$ https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=2913s
S1: For EVERY alphabet, Set of all recursively enumerable languages is countable.
To show that a set $S$ is countable, we can show that there exists a surjective function from some countable set to set $S.$
Set of all Turing machines is countable, & we can create a Surjective function $f$ from set of all Turing machines to set of all RE languages by mapping any Turing machine $T$ to $L(T)$ i.e. $f(T) = L(T).$ This mapping is surjective. So, set of all recursively enumerable languages is countable.
Detailed Video Explanation of this proof is HERE.
S2: Set of all syntactically valid C programs is countable.
In fact, Set of all programs is countable because every program is a finite sequence of statements. Inside a computer, every program is stored as some binary string of finite length. So, set of all programs is the same as the set of some finite length binary strings which is a countable set.
Detailed Video Explanation of this proof, with more variations is HERE.
S3: For EVERY $\Sigma,$ the set of all languages is uncountable.
The set of all languages over $\Sigma$ is the powerset of $\Sigma^*$ i.e. $P(\Sigma^*).$
Proof:
By Cantor’s theorem, we know: If $S$ is ANY infinite set, then $P(S)$ is always uncountable. (Or we can say, NO infinite powerset is countable.)
Since, for every $\Sigma$, $\Sigma^*$ is infinite, hence, $P(\Sigma^*)$ is uncountable.
Learn Cantor’s Theorem & its Consequences HERE.
S4: For EVERY alphabet, Set of all non-regular languages is uncountable.
We know the set of all regular languages is countable, But the set of ALL languages is uncountable, So, set of all non-regular languages is uncountable.
Detailed Video Explanation of this proof is HERE.
Countability Complete Course, with Proofs, Variations & All type of questions covered: https://youtube.com/playlist?list=PLIPZ2_p3RNHgXosiQv-gL1PvJkcHokW1p&feature=shared