Prove that there are infinity many tautologies. For this question I think I am suppose to use proof by contradiction, but I need some hints on how to proceed with the proof. Always if someone can give me a brief explanation on how proof by contradiction was that would be really helpful.
 A: Just show a pattern of tautologies that clearly has infinitely many wff's. For example,
$$A\implies A,\ B\implies B,\ C\implies C,\ldots$$
or
$$A\implies A,\ (A\land A)\implies (A\land A),\ (A\land A\land A)\implies (A\land A\land A),\ldots$$
or many other patterns. Make one that you like.
A: If you must use a proof by contradiction, then you could use something along these lines. Suppose there were only a finite number of tautologies, let them be $A_i$ for $1 \leq i \leq n$. Since the $A_i$ are finite in number we can form their conjunction, another wff, $A_1 \land A_2 \land A_3 \land ... \land A_n$ (suitably bracketed!). But then if each conjunct is a tautology (true on all valuations) so obviously is the whole conjunction. So we have found a tautology distinct from all the $A_i$. Contradiction!
A: If there exist only finitely many tautologies, then the system {CpCqp} under the rule of substitution and detachment has a shortest member (the length of a wff consists of the number of symbols it has excluding parentheses).  But, we can always substitute any already proved theorem for 'p' in that formula, and substitute any variable for 'q' which does not belong to the already proved theorem.  Thus, we obtain C$\alpha$$\beta$ from $\beta$, where $\beta$ consists of a theorem.  Since $\beta$ represents an arbitrary axiom or theorem (thesis), we can always obtain a longer theorem than $\beta$.  Thus, there is no shortest member of the set of all tautologies, which means we have a contradiction.  So, there exist infinitely many tautologies.
