The proof generally begins with an inductive definition of the set. For example, let's say the set of connectives was {$\oplus$}.
Let F be the smallest set such that:
1) Any propositional variable is in F
2) If P and Q are in F then so are (P $\oplus$ Q)
The next step in the proof is to prove by structural induction that no formula in F is equivalent to, let's say (P + Q). There are 4 possible truth assignments to consider:
$\tau_0: \tau_0$ falsifies P and falsifies Q;
$\tau_1: \tau_1$ falsifies P and satisfies Q;
$\tau_2: \tau_2$ satisfies P and falsifies Q;
$\tau_3: \tau_3$ satisfies P and satisfies Q;
Of the four, only 2 of the assignments can satisfy $(P \oplus Q)$ while 3 of them can satisfy $(P+Q)$.
So let S(R): Let R $\varepsilon$ F. Then only 2 of $\tau_0, \tau_1, \tau_2, \tau_3$ can satisfy R
Now, suppose we try to prove this by structural induction:
Basis:
R is of the form $P\oplus Q$ where P and Q are proposiitonal variables. It is clear that S(R) holds.
Inductive Step:
R is of the form $P\oplus Q$ where P and Q are formulas constructed only from $\oplus$
Again we have the same possible truth assignments as the basis. So again, only 2 of $\tau_0, \tau_1, \tau_2, \tau_3$ can satisfy R. Hence S(R) holds.
We then conclude that since 3 assignments satisfy $P+Q$ while only 2 satisfy $P\oplus Q$, that no formula in F is logically equivalent to $P+Q$ and hence that {$\oplus$} is incomplete.
My question(s) are:
1) The inductive step seems to holds by itself without following from or using the inductive hypothesis. Is this still a valid induction proof?
2) The proof does not include formulas that consist only of a single propositional variable (PV). While, it is clear that no single PV can be equivalent to $(P+Q)$ is it still valid to leave it out of the proof?
Hope someone can clarify the concepts of the proof for me.
Best Answer
I'm confused about what exactly you are trying to prove by induction. In particular, are you trying to prove:
Moreover, I don't think you've really used structural induction at all. Structural induction proves statements of the form "for all $x \in F$, $x$ has property $T$", by proving that variables have property $T$ and if $x$ and $y$ are formulae with property $T$ then $x \oplus y$ has property $T$. I'm not clear on what $x$ or $T$ are in your argument.
I'm also confused by your assertion that there are 4 possible truth assignments. Certainly there are 4 cases that you've identified, but surely each may correspond to no or many assignments of the variables, at least in principle?
How about this instead: prove by structural induction that all formulae in $F$ are falsifiable: you can choose some assignment of the variables to make them false. Then any tautology (e.g. $x \to x$) clearly can't be represented.
Here's some remarks on structural induction that I'm not sure are useful but I've written them now and don't want to throw them away:
Why does structural induction work? Well, there are a couple of ways of understanding it. One formal way is to say that if we call $S$ the set of things with property $T$, then the bas case and inductive hypothesis show that $S$ satisfies the conditions 1. and 2. in your definition of $F$; since $F$ was the minimal set satisfying those conditions, $F$ is a subset of $S$, i.e. all elements of $F$ satisfy the property $T$.
The more intuitive way is to grab an arbitrary element of $F$ and see how the inductive tools can be used to build a proof for that element. Let's say we look at $a \oplus ((b \oplus c) \oplus d)$. Well, our base case says the theorem holds for $b$ and $c$, so the inductive step says it holds for $b \oplus c$. But then it holds for $b \oplus c$ and $d$, so it holds for $(b \oplus c) \oplus d$. But then it holds for $a$ and $(b \oplus c) \oplus d$, so it holds for $a \oplus ((b \oplus c) \oplus d)$. What we're doing here is saying, this set is the set of all things that can be made from these starting points taking these steps, so anything that is true at all the starting point and stays true when you take each step is going to be true everywhere in the set.