Take the 2-minute tour ×
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.

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.

share|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
add comment

5 Answers

up vote 3 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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.