Is there a contradiction that only contains the logical symbol implication?

Question

I have shown by tedious case analysis that any formula in the first order logic that does not contain the negation or implication symbol cannot be a contradiction (false under every interpretation). I am wondering if a there is a formula without the not symbol that is a contradiction, and if there is a formula with only the logical symbol of implication that is a contraction.

Answer 1

There is no such sentence, and this remains true if we allow $\wedge,\vee,\leftrightarrow$ as well (thus subsuming the previous result you mention).

In fact, fixing a first-order language $\Sigma$, the unique (up to isomorphism) one-element $\Sigma$-structure $\mathcal{A}_\Sigma$ where every $n$-ary relation holds on the unique $n$-tuple satisfies every negation-free $\Sigma$-sentence.

This is a straightforward induction on complexity (and also a neat example of a situation where strengthening the induction hypothesis simplifies the argument):

• For the base case, note that every atomic $\Sigma$-formula is true in this structure under every (i.e., the unique) variable assignment.

• For the inductive case, quantifiers are essentially trivial, and all connectives except $\neg$ are "truth preserving" in the sense that whenever all inputs are true the result is true.

Note that the nature of the structure $\mathcal{A}_\Sigma$ is used in two places: the analysis of atomic formulas, and the triviality of the quantifiers.

Incidentally, the point about propositional connectives above is also the standard way to prove that $\{\wedge,\vee,\rightarrow,\leftrightarrow\}$ is not functionally complete. Meanwhile, note that the notion of "truth preserving" used here is incredibly weak; in particular, since "False implies False" is true but "True implies False" is false we see that it doesn't imply truth monotonicity (= "making the inputs more true makes the output more true"). As such I don't think it actually has an accepted name, it's too weak a condition in almost every context.

Answer 2

If such a formula existed, one with a minimal number of implications would contain at least one $\to$ (because you've already checked the case with none), and we could write some such contradiction as $a\to b$. (If $(a\to b)\lor c$ is a contradiction, so is $a\to b$; if $(a\to b)\land c$ is a contradiction, so is $(c\land a)\to b$.) We then need $a$ to be true and $b$ false in all interpretations. But then $b$ is an option with one fewer $\to$, a contradiction.