Show that a set $ F $ is uncountable Let $$ \{a,b,c\}^n = \big\{(x_1,x_2,\dots,x_n): x_j \in \{a,b,c\} \big\}$$ and
$$ \{a,b,c\}^{*} = \bigcup_{n=1}^{\infty} \{a,b,c\}^n.$$
Consider the set $ F = \big\{ f: \{a,b,c\}^{*} \to \{a,b,c\} \big\}$ and show that $ F $ is not countable.
I've tried a couple of solutions:
i) No bijection between $ F \to \mathbb{N} $. Although I've tried to use Cantors diagonalizing argument I'm getting nowhere, since the arguments of $ f$ is such a mess.
ii) $ F $ is clearly an infinite set. Then it's sufficient to show that $ \mid F \mid \neq \mathbb{N}^0$ (aleph-null) or $ \mid F \mid > \mathbb{N}^0 $.
How do I solve this?
 A: The set $A=\{a,b,c\}^{*}$ is countable. Thus $P(A)$, the power set of $A$, is uncountable. Now we see $P(A)\cong\big\lbrace f:A\to \lbrace 0,1\rbrace\big\rbrace\subset F$, so $F$, too, is uncountable.
A: This proof is basically the hint that @Hanul_Jeon gave in the comments as well as a follow on to your attempt number $1$. First, note that the set $\{a,b,c\}^{*}$ is countable. This is because there exists an injective function between this set and a subset of the rational numbers. One such function can be formally written as
$$g(\{x_1,x_2,...,x_n\})=\sum_{i=1}^n \frac{h(x_i)}{4^i}$$
where
$$h(x_i)=\begin{cases} 
      1 & x_i=a\\
      2 & x_i=b \\
      3 & x_i=c
   \end{cases}$$
Now that we have shown that $\{a,b,c\}^{*}$ is countable, we can show that $F$ is uncountable. Let $r:\{a,b,c\}^{*}\to\mathbb{N}$ be a bijection between $\{a,b,c\}^{*}$ and the natural numbers and suppose by way of contradiction that $F$ is countable. Then we can list the elements of $F$ in a bijection with $\mathbb{N}$:
$$f_1:\{a,b,c\}^{*}\to\{a,b,c\}$$
$$f_2:\{a,b,c\}^{*}\to\{a,b,c\}$$
$$f_3:\{a,b,c\}^{*}\to\{a,b,c\}$$
$$\vdots$$
We will now construct a new function $f^{*}$ that is not on this list (Technically, the diagonal arguement is a constructive arguement, not contradiction. But its easier to understand as a proof by contradiction so I'll leave that terminology from above). For each element in $\{a,b,c\}^{*}$, define
$$f^{*}(\{x_1,x_2,...,x_n\})=K[f_{r(\{x_1,x_2,...,x_n\})}(\{x_1,x_2,...,x_n\})]$$
where
$$K(x)=\begin{cases} 
      a & x=b\\
      b & x=c \\
      c & x=a
   \end{cases}$$
There is a lot to unpack in that function, but the basic idea is this: To find what $f^{*}$ does to an arbitrary element $s\in\{a,b,c\}^{*}$ do the following

*

*Use the bijection $r$ to get the natural number corresponding to the $s$


*Go to the function $f_{r(s)}$ in the list (the one we assumed to exist)


*Change the output of $f^{*}$ to be different from $f_{r(s)}$
In this way, we are assured that $f^{*}$ is different from all functions on the list. As this is a contradiction, we conclude that $F$ is not countable.
