I got stuck trying to prove that statement. I am sorry if I got some terms wrong. I did my best to look for the equivalent terms in English, but I study in different language. So just to be on the same page, $Ded(\emptyset)$ is an inductive set such that its base is $B=A_1 \cup A_2 \cup A_3$ and
$$
A_1 = \{\alpha \rightarrow(\beta\rightarrow\alpha) \space\space | \space\space\alpha,\beta\in WFF_{\{\neg, \rightarrow\}}\}\\
A_2 = \{(\alpha \rightarrow(\beta\rightarrow\gamma))\rightarrow((\alpha\rightarrow\beta)\rightarrow(\alpha\rightarrow\gamma))\space\space | \space\space\alpha,\beta,\gamma\in WFF_{\{\neg, \rightarrow\}}\}\\
A_3=\{((\neg\beta)\rightarrow(\neg\alpha))\rightarrow(\alpha\rightarrow\beta) \space\space | \space\space\alpha,\beta\in WFF_{\{\neg, \rightarrow\}}\}
$$
And the inference rule is modus ponens and denoted by $MP(\alpha,\alpha\rightarrow\beta)=\beta$
This is how I started my proof:
Let $T$ be defined as follows
$$
T=\{\alpha \in WFF_{\{\neg, \rightarrow\}} \space\space| \space \text{there is a main connective in}\space\alpha\}
$$
We can now show with structural induction that $Ded(\emptyset)\subseteq T$.
Base:
Let there be $\alpha \in B =A_1 \cup A_2 \cup A_3$. Since all axioms have a main connective, indeed $\alpha\in T$. Therefore, $B\subseteq T$.
Inductive step:
Assume that $\alpha,\phi \in T$. Denote $\epsilon = MP(\alpha,\phi)$.
Let us look into separate cases:
• If there is no such $\beta\in WFF_{\{\neg, \rightarrow\}}$ such that $\phi = \alpha\rightarrow\beta$, then $\epsilon = MP(\alpha,\phi)=\alpha$. Therefore $\epsilon\in T$.
• If there is $\beta\in WFF_{\{\neg, \rightarrow\}}$ such that $\phi = \alpha\rightarrow\beta$, then $\epsilon =MP(\alpha,\phi)= \beta$.
This is where I got stuck. I couldn't prove that $\beta\in T$, and the assumption didn't help me in this case. I would appreciate if someone could help me complete my proof.
Best Answer
I don't know why induction would get used to prove this.
Note that there exist two types of formulas. Propositional variables (assuming no truth value constants in the language) and formulas with a main connective. Now can we show that no formula in Ded(∅) is a propositional variable?
Well, suppose that some variable were in Ded(∅). But, then we have a consequence which is possibly false, and the distinction between truth and falsity would collapse in logic also, since we could deduce both a true proposition a false proposition. Can any formula in Ded(∅) possibly be false?
Well, if so, then this system would not be sound. So, I would prove it by first proving the soundness meta-theorem for this system, and then using the argument that every formula in Ded(∅) is thus a tautology. No variable is a tautology (otherwise we would have a contradiction with the definition of a tautology). And then it follows that every deducible formula has at least one connective.
It also holds that every formula in Ded(∅) with a ¬ symbol will also have a $\rightarrow$ symbol in it.
Edit: I'm also assuming that something like α→(β→α) is an abbreviation for (α→(β→α)), but this seems rather minor here.