Cardinality of tautologies for propositional logic I'm wondering how many tautologies there are in propositional logic. I'm thinking that it must be at least countable, since ($P_{1} \wedge P_{2} \wedge \cdots P_{n}) \models P_{i}$ should be a tautology for any natural number $n$ and any $i \in \{1,2,\cdots,n\}$, where each $P_{k}$ is a sentence symbol for $k \in \mathbb{N}$. 
But there aren't uncountably any, are there? How would one explain/show that? I'm sure this has been asked before somewhere - any references would be appreciated. Thanks!
Sincerely,
Vien
 A: I am assuming that your language only has a countable number of propositional variables. In this case, you can easily show that the number of propositions to begin with is countable (hint: the set of finite strings over a countable language is countable).
Therefore there cannot be more than a countable set of tautologies. In the other direction, it's simpler to note that if $p_i$ is a propositional variable then $p_i\to p_i$ is a tautology. Therefore there are exactly $\aleph_0$ of them.
A: Suppose your language has only one propositional variable and your only connective consists of the material conditional C.  The cardinality of the set of all finite strings for that language comes as at most countable.  Since all tautologies come as finite strings, it follows that the set of all tautologies comes as at most countable also.
Now, Cpp comes as a tautology in this language.  Consequently, it holds that for all truth values in the truth set that Cpp evaluates to true.  All formulas qualify as truth-functional.  Consequently, if a formula $\alpha$ evaluates to true or false, then C$\alpha$$\alpha$ will evaluate to true.  It follows that the rule of uniform substitution can get applied to tautologies.  Consequently, if we uniformly substitute p with Cpp, denoted p/Cpp hereafter, in any formula $\beta$, then the result of such substitution gives us a formula $\beta$' such that $\beta$' qualifies as a tautology.
Now, let's form a sequence which starts with Cpp as its first formula.  Define the (n+1) formula of the sequence as the result of p/Cpp in formula n.  For instance, since the first formula of our sequence is Cpp, CCppCpp is the second formula of our sequence.  Since CCppCpp is the second formula, CCCppCppCCppCpp is the third.  Since p always appears in the (n+1) formula no matter what formula n is, formula (n+1) can always get formed.  Thus, we have an unending sequence of tautologies in this language.  Consequently, this language has countably many tautologies.
