Question: Prove that a set of connectives is incomplete using structural induction

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.

• @amwhy I'm trying to prove that the XOR operator is incomplete. The XOR operator is a binary operator: P XOR Q – EggHead Oct 26 '13 at 1:12
• Since we know that 3 of the 4 cases will satisfy P OR Q, we can conclude that no formula consisting of just the XOR operator can be made logically equivalent to OR. Hence, the set of connectives consisting only of XOR is incomplete. – EggHead Oct 26 '13 at 1:20
• What I'm having a problem with is that the property T can be proved in the inductive step without using the inductive assumption. This is because XOR is a binary boolean operator so there will always only be the four cases and only 2 of them will satisfy the formula. – EggHead Oct 26 '13 at 1:23
• The structural induction is on the definition of F. I'm not sure whether the proof of the property T is structural. – EggHead Oct 26 '13 at 1:26
• Thus, if P is falsified by a given truth assignment, any complex formula that uses XOR and only P as an argument is falsified by the same assignment. But negation of P should be satisfied when P is satisfied. So, none of these formulas using only XOR, however complex they are, can play the role of negation. – J Marcos Oct 26 '13 at 1:41

I'm confused about what exactly you are trying to prove by induction. In particular, are you trying to prove:

• There exist formulae $P$ and $Q$ such that $P + Q$ is not equivalent to any formula in $F$, or
• For all formulae $P$ and $Q$, $P + Q$ is not equivalent to any formula in $F$?

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.

• I can only guess @EggHead might be trying to prove that every formula with only two arguments (for which there are only four distinct classes of truth assignments) and having XOR as its sole connective is either falsified by two truth assignments or by all four truth assigments. He can indeed check that by structural induction. So, if one needs to find a formula, say, that plays the role of OR or of AND using only XOR, it will turn out to be impossible, as these connectives are falsified in an even number of the four mentioned truth assignments. – J Marcos Oct 26 '13 at 2:14
• @JMarcos: I think if you are having to guess then there's something amiss that should be worked out :) – Ben Millwood Oct 26 '13 at 12:08
• @JMarcos Your guess about what I was trying to prove is correct. My problem was with stating that "only 2 out of 4 possible truth assignnments will satisfy P XOR Q while 3 of those will satisfy P OR Q". It would be more precise as you mentioned to say "Only truth assignments from 2 of the classes of truth assignment..." – EggHead Oct 26 '13 at 13:48
• @JMarcos I was also trying to include formulas consisting only of single propositional variables in the base case but that seems impossible since the four classes of truth assignments reuqire 2 variables... – EggHead Oct 26 '13 at 13:52