2

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.

Arjun Dhiman
  • 422

3 Answers3

5

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.

Rory Daulton
  • 32,288
  • what does wff stand for? – Arjun Dhiman Jun 27 '15 at 17:29
  • @Zero: Well-formed formula. A correctly formatted logical statement. – Rory Daulton Jun 27 '15 at 17:31
  • Would this be an accurate proof?
    • Pf(By Contradiction)

    Claim: There are a finite amount of tautologies.

    A $\implies$ A ....

    Therefore, by contradiction there are infinitely many tautologies.

     – Arjun Dhiman Jun 27 '15 at 17:37
  • 4
    There's no reason to make it a proof by contradiction! Just write down a list of infinitely many tautologies, as suggested. Ok, maybe you can't quite write down the whole list... – David C. Ullrich Jun 27 '15 at 17:54
  • This proof doesn't show that there exist infinitely many most general tautologies. – Doug Spoonwood Jun 27 '15 at 20:46
  • @DougSpoonwood What do you mean by "most general"? – Wojowu Jun 27 '15 at 20:52
  • @Wojowu Assume that the variables in tautologies always appear in a fixed order. Tautology A is more general than tautology B if we can obtain B from A by substitution alone. Given a bracket type for formulas... that is the positions where the connective symbols go (e. g. C p C p p and C p C q p have the same bracket type and C p C q p is more general than C p C p p), a formula F is a "most general" formula for that bracket type if there do not exist any more general formulas {G} of that bracket type which can get used to obtain F from a member of {G} by substitution alone... – Doug Spoonwood Jun 27 '15 at 21:05
  • A tautology is a most general tautology T if no other tautologies can get used to obtain T by substitution alone. For instance, "C C p q C r C p q" is a most general tautology for it's bracket type. But, it is not a most general tautology, since it can get obtained by substitution alone from C p C q p. C p C q p is a most general tautology, since there do not exist any other tautologies from which we can obtain C p C q p by substitution alone. – Doug Spoonwood Jun 27 '15 at 21:11
2

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!

Peter Smith
  • 54,743
-3

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.

Doug Spoonwood
  • 11,211