# Is the propositional set infinitely countable

Recently I'm learning logic. Here is the definition from the book "Logic For Computer Science":
A countable set PS of proposition symbols: P0,P1,P2...

The set PROP of propositions is the smallest set satisfy:

1. Every proposition symbol Pi is in PROP.

2. Whenever A is in PROP, ~A is also in PROP.

3. Whenever A, B are in PROP, (A v B), (A ^ B) and (A->B) are also in PROP.

4. A string is in PROP only if it is formed by applying the rules 1. 2. 3. Now I want to know whether PROP is infinitely countable and how to prove that.

-
It all depends on how many "proposition symbols" there are. If you begin with an uncountable set of proposition symbols, of course the set of propositions will also be uncountable. – Carl Mummert Sep 7 '12 at 21:00

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.

This is pretty obvious, but in any case we can easily write down an explicit bijection $\varphi$ between $S$ and $\Bbb N$; one is given by $\varphi(0)=\lnot$, $\varphi(1)=\lor$, $\varphi(2)=\land$, $\varphi(3)=($, $\varphi(4)=)$, and $\varphi(n)=P_{n-5}$ for $n\ge 5$.

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.

1. Prove that $S^2$ is countably infinite; this can be done with the Cantor pairing function.

2. Prove by induction on $n$ that $S^n$ is countably infinite for each $n\in\Bbb Z^+$.

3. 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$.

-

Assuming that there are a countable number of propositional symbols, then yes there are countable number of sentences.

Let $X_0$ be the set of propositional symbols.

By recursion define $X_{n + 1}$ to be the set consisting of $\neg A$ such that $A \in X_{n}$ and $A \wedge B$ such that $A, B \in X_{n}$, ... so forth.

Then $X = \bigcup_{n \in \omega} X_n$ is the set of all propositional sentence.

First the claim is that $X_n$ is countable for all $n$. Prove this by induction. By assumption $X_0$ is countable. If $X_n$ is countable, then $X_{n + 1}$ is countable. This is because

$X_{n + 1} = \bigcup_{A \in X_n} \{\neg A\} \cup \bigcup_{A \in X_n} \bigcup_{B \in X_n} A \wedge B \cup ...$

where $...$ means do the same thing for $\vee$ and $\Rightarrow$. Countable union of countable sets are countable.

Then $X = \bigcup_{n \in \omega} X_n$ is a countable union of countable sets and hence is countable.

-

Each strng in PROP is a finite sequence of symbols from a countable alphabet (consisting of $P_0, P_1, \ldots$ and the logical symbols). For each $n$, the set of such sequences of length $n$ can be viewd as subset of $\mathbb N^n$. Since the diagonal argument shows that $|\mathbb N\times \mathbb N|=|\mathbb N|$, ist follows by induction that $|\mathbb N^n|=|\mathbb N|$. By the same diagonal argument we see that PROP as the (here: disjoint) union of countably many countable sets is countable.

-

You can just simply order terms by the "level" in which they appear. Each level has countably many terms, and the set of all levels are countable.

-
But the first level, the propositional variables, is described as having infinitely many members $P_0$, $P_1$, $P_2$, ... – Peter Smith Sep 7 '12 at 6:53
Thank you for pointing out my mistake. I've fixed that. – Tunococ Sep 7 '12 at 20:39

Just how quick and dirty a proof is acceptable? Take your favourite Gödel-numbering style coding system for strings of symbols, and take the function that takes $n$ to the wff with code $n$ (if there is one) and to $P_0$ otherwise. And voilà, a surjective function from $\mathbb{N}$ to the set of wffs, which makes the latter countable by definition.

-