0

This question takes inspiration from this question.

A tautology is organic if none of it's proper sub-formulas are tautologies. In other words, if all of the sub-formulas excluding the formula itself are not tautologies.

For example, C C p q C C q r C p r is organic, but C p C q C r q is not, since C q C r q is a tautology.

I suspect that there exist infinitely many organic tautologies which are not substitution instances of other tautologies. How might that get proved?

Community
  • 1
Doug Spoonwood
  • 11,211

1 Answers1

2

Can't you just expand your first formula by adding more variables? For instance

$$ (a\to(b\to c))\to((a\to d)\to((b\to d)\to(c\to d)) $$

or CCaCbcCCadCCbdCcd in Polish notation, should be an organic tautology if I'm not wrong.

Jack D'Aurizio
  • 353,855
  • You're right that this would work for what I asked. I've edited the question to preclude using such substitution instances. – Doug Spoonwood Jun 27 '15 at 22:09
  • 1
    @DougSpoonwood: I'm not sure I really know what a "substitution instance" is, but is $$ (a\to(b\to c))\to((a\wedge b)\to c)$$ allowed? – Jack D'Aurizio Jun 27 '15 at 22:19
  • CCaCbcCCadCCbdCcd is not a tautology. Let a = 0, b = 0, c = 1, and d= 0. Then CaCbc = 1. But, CCadCCbdCcd = CC00CC00C10 = CC00CC000 = CC00C10= CC000= C10 = 0. A substitution instance I of a tautology T is simply a wff that we can obtain from T by substitution alone (uniform replacement of variables by formulas throughout the formula). Your example is incorrect, but your idea works! You just prefix the conditionals instead of what you did. More like C CaCpq C CaCqr CaCpr, C CbCaCpq C CbCaCqr CbCaCpr, C CcCbCaCpq C CcCbCaCqr CcCbCaCpr... – Doug Spoonwood Jun 27 '15 at 23:25
  • The pattern there goes that you have Ca...CoCpq as the antecedent, Ca...CoCqr as the antecedent of the consequent, and Ca...CoCpr as the consequent of the consequent. Since the consequent of the consequent has form Ca...CoCpr, we could assume Ca...CoCpq and Ca...CoCqr, and all variables in a ... p. Then we have q, and finally r following. Discharging all assumptions yields the formula as a tautology. It's not organic, since the antecedent is not a tautology (nor does it contain any) and neither is the consequent of the consequent, nor the antecedent of the consequent. – Doug Spoonwood Jun 27 '15 at 23:32
  • And the consequent itself is not a tautology either, so none of the sub-formulas are tautologies, rendering all tautologies of this form organic. – Doug Spoonwood Jun 27 '15 at 23:32
  • Oh and extended forms of importation and exportation like you've suggested with your last comment should work also. – Doug Spoonwood Jun 27 '15 at 23:39