Recently I'm learning logic. Here is the definition from the book "Logic For Computer Science":
A countable set $PS$ of proposition symbols: $p_0,p_1,\dots$
The set $\text{Prop}$. propositions is the smallest that satisfies:
-
Every proposition symbol $p_i$ is in
$\text{Prop}$. -
Whenever $\varphi$ is in $\text{Prop}$, $\neg \varphi$ is also in
$\text{Prop}$. -
Whenever $\varphi, \psi$ are in $\text{Prop}$, $(\varphi \vee \psi), (\varphi\wedge \psi)$ and $(\varphi\rightarrow\psi)$ are also in $\text{Prop}$.
-
A string is in $\text{Prop}$ only if it is
formed by applying the rules $1, 2$ and $3$.
Now I want to know whether $\text{Prop}$ is countably infinite, and if so how to prove that.
Best Answer
Yes, PROP is countably infinite. It’s clearly infinite, because each of the strings $P_i$ for $i\in\Bbb N$ belongs to PROP. To show that it’s only countably infinite, it suffices to find an injection from PROP to a set that is already known to be countably infinite. One way to do this is to find a countably infinite set that contains PROP as a subset.
Let $S$ be the set whose elements are the proposition symbols $P_i$ for $i\in\Bbb N$ and the symbols $\lnot$ (or ~), $\lor$, $\land$, and the left and right parenthesis symbols. $S$ is a countably infinite set.
Every string in PROP has a length, and that length is a positive integer. If $\sigma\in\text{PROP}$ has length $n$, then $\sigma\in S^n=\underbrace{S\times S\times\ldots\times S}_{n\text{ times}}$. Thus, every string in PROP belongs to the set
$$T=\bigcup_{n\in\Bbb Z^+}S^n=S\cup S^2\cup S^3\cup S^4\cup\ldots\;\;.$$
Since $\text{PROP}\subseteq T$, all that’s necessary in order to show that PROP is countably infinite is to show that $T$ is countably infinite. To do this in detail requires several steps.
Prove that $S^2$ is countably infinite; this can be done with the Cantor pairing function.
Prove by induction on $n$ that $S^n$ is countably infinite for each $n\in\Bbb Z^+$.
Prove that the union of countably many countably infinite sets is countably infinite. This can be done by a slightly more sophisticated use of the pairing function. Once you know that each $S^n$ is countably infinite, you know that each can be listed as $S^n=\{\sigma_n(k):k\in\Bbb N\}$. You then use the pairing function $\pi$ to assign each $\sigma_n(k)\in T$ the natural number $\pi(n,k)$; this gives a bijection from $T$ to $\Bbb N$.