Logic; prove set of connectives incomplete

[honestrosewater]

Let p and q be distinct prime formulas (a.k.a. atomic propositions) and P be a set constructed as follows:

1) p and q are in P;
2) if r and s are in P, then (r -> s) is in P.

Prove that no formula in P is tautologically equivalent to (p & q). In other words, there exists no t in P such that t^v

= T when p^v = T and q^v = T;
= F otherwise.

I can't get anywhere. I'll be going through the possibilities until I notice something.

Oh, nevermind, I got it by contradiction and going backwards; every possibility dead ends. Maybe there's a better (more useful) way though.

 

[AKG]

I'm guessing you did it like this:

Assume there were such a sentence. Clearly, neither of the prime formulas are equivalen to (p & q). Assume that no formulas of length less than or equal to k are equivalent to (p & q). Consider a sentence (r -> s) of some length such that the length of s is less than or equal to k. If (r-> s) were equivalent to (p & q), then it must be false when at least one of p and q are false, and true when both are true. However, every sentence is clearly true when both p and q are true. Now for (r -> s) to be false, r must be true and s must be false. So we get that s must be false when at least one of p and q are false, and true when both are true. That is, s must be equivalen to (p & q), but it is not by inductive hypothesis, so we're done.

Of course, the above is a bit sketchy, and I never clearly explained what I meant by length, but it gives the idea of the proof.

What did you mean by a "better" or "more useful" way?

 

[Hurkyl]

My first thought is via truth tables. There are only 16 different boolean functions of two variables, and you can manually write down which ones correspond to elements of P.

More rigorously...

Elements of P can be construed as boolean functions of two variables. Two elements of P are tautologically equivalent if and only if their corresponding boolean functions are equal. There are only 16 such boolean functions.

So, you can simply compute which boolean functions can correspond to elements of P. In other words, you simply start with the two functions p'(x,y) := x and q'(x,y) := y, and compute its closure under the binary operation of implication.



You could do the same, but without invoking boolean functions. Just find a subset S of P containing p and q with the property that if x and y are elements of S, then x -> y is logically equivalent to an element of S. Then, by induction, everything in P is logically equivalent to something in S.



Back to boolean functions, I think you can inductively prove everything in P has a truth table with at least two T's in it. This seems by far the shortest path to a proof.

 

[honestrosewater]

My first one: all I'm interested in are truth-values, and we just finished proving everything about truth tables, so I was already thinking of them. There are 4 valuations (rows) and, as Hurkyl said, 16 columns. I just followed the possible derivations backwards. They all start with p and q, which I assigned (T, T, F, F) and (T, F, T, F), respectively. Assume there is such a t. It's of the form (r -> s) and its column = (T, F, F, F). This gives me all the possible combinations of columns for r and s, which are themselves either atomic (in which case they must be (T, T, F, F) or (T, F, T, F)) or of the form (u -> v), in which case I find all the possible combinations of columns for u and v, etc. There are only 16 columns, so they have to start repeating eventually, and if I can't get back to some combination of (T, T, F, F) or (T, F, T, F), t is not in P. It looks something like this.

(r -> s) = TFFF so
1) r = TTTT and s = TFFF -- s <=> t, so end this branch.
2) r = FTTT and s = TFFF -- s <=> t, end branch.
3) r = FTTT and s = FFFF.

s = (u -> v) = FFFF so
1) u = TTTT and v = FFFF -- u <=> s, end branch.

r = (w -> x) = FTTT so
... they all end without passing what could be a combo of p or q.

By more useful, I mean faster, easier, or more general. I don't mind the longer, more specific ones -- I do want to get to know the language and how it works (and they tend to reveal useful patterns, e.g., here, the many general rules regarding the number and placement of Ts and Fs in a formula and its subformulas). I just want some of both. Thanks for the ideas.

 

[Hurkyl]

Hrm. If you look in the forward direction, the only distinct possibilities are:

TTFF p
TFTF q
TFTT p->q
TTFT q->p
TTTF (p->q)->q
TTTT 1

I believe this set is closed under implication. It's neat to see the or operation in there as pVq = (p->q)->q.

I thought this suggested a nice pattern, but a quick look at the 3 atomic formula case suggests that might not be true.

 

[honestrosewater]

Yeah, I meant to work on this today but didn't get time. I happen to be interested in complete sets of connectives, so I'm going to play with them; I'll post anything interesting I find.

I think this was the most useful thing yet (I imagine there are similar ones for other connectives):

1) If I is an implication formula, IA is its antecedent, and IC its consequent, then if row n of column I = F, then row n of column IC = F.

So no formula in P can have more than 2 Fs in its column, since if I has 4 Fs, IC has 4 Fs (IC = I), so its branch closes immediately, and if I has 3 Fs, IC has either exactly 4 Fs (so closes) or exactly 3 Fs in the same rows (IC = I), so it closes immediately. If I has 2 Fs, IC has exactly 4, 3, or 2 Fs in the same rows, so it either closes immediately or equals p or q. And by (1)'s contrapositive, if row n of column IC ≠ F, then row n of I ≠ F, so for all f in P, row 1 of column f ≠ F. I think that covers everything not in your list.

(Woops, a few times I said f when I meant column f. It should be clear though.)