Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

  1. Every proposition symbol $p_i$ is in $\text{Prop}$.

  2. Whenever $\varphi$ is in $\text{Prop}$, $\neg \varphi$ is also in $\text{Prop}$.

  3. Whenever $\varphi, \psi$ are in $\text{Prop}$, $(\varphi \vee \psi), (\varphi\wedge \psi)$ and $(\varphi\rightarrow\psi)$ are also in $\text{Prop}$.

  4. 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.

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
I wouldn't say that $\sigma\in S^n$, but that we can associate the string $\sigma$ to a tuple $\sigma'\in S^n$ by the obvious mapping $\sigma=s_1s_2\cdots s_n\mapsto (s_1,s_2,\cdots,s_n)$. – YoTengoUnLCD Feb 5 at 4:03
@YoTengoUnLCD: $\sigma$ is in $S^n$; what do you think a string is? – Brian M. Scott Feb 5 at 22:42

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.