1
$\begingroup$

I was following these notes and I tried doing exercise (5) on page 42:

If $\varphi$ is an L-tautology, then $\vdash \varphi$ (without thm 2.7.4, completeness of predicate logic)

intuitively it makes sense (or it should be true) but I don't know how to even start a proof. Usually I would look at the list of axioms (propositional axioms, equality axioms, quantifier axioms) and try some of them. However, the equality axiom and quantifier axioms seem pretty useless because it feels really strange to introduce equality signs or quantifiers to a "virgin" L-tautology (which just is a formula of the form $p(\varphi_1, \dots, \varphi_n)$ for some tautology $p(\alpha_1, \dots, \alpha_n) \in Prop\{\alpha_1,\dots,\alpha_n \})$ i.e. introduce symbols to something that doesn't have them or doesn't need them.

Then I proceeded to check the propositional axioms since those seemed more plausible to be useful. The ones my notes provide as axioms are:

  1. T
  2. $\varphi \to (\varphi \lor \psi); \varphi \to (\psi \lor \varphi)$
  3. $\neg \varphi \to (\neg \psi \to \neg (\varphi \lor \psi) $
  4. $(\varphi \land \psi) \to \varphi; (\psi \land \varphi) \to \psi$
  5. $\varphi \to (\psi \to (\varphi \land \psi))$
  6. $(\varphi \to (\psi \to \theta)) \to ((\varphi \to \psi)\to (\varphi \to \theta))$
  7. $\varphi \to (\neg \varphi \to \bot)$
  8. $(\neg \varphi \to \bot) \to \varphi$

however, these propositional axioms already have formulas $\varphi,\psi,\theta$ and thus, it didn't seem sensible if I wanted to prove $p$ was a tautology, to introduce even more formulas...

Am I missing something really obvious? Or is this suppose to be hard?


-- For context, definition of Tautology

In propositional logic tautologies are those propositions $p$ that no matter the truth assignment to the atoms $t:A^n \to A$, $p$ is always true denoted $ \models p$. I assume that for predicate logic this definition is the same but with L-structures $\mathcal A = (A;(R^{\mathcal A})_{R \in L^r},(F^{\mathcal A})_{F \in L^f} )$ i.e. a L-formula $p(\varphi_1, \dots, \varphi_n)$ is a tautology if

$$\mathcal A \models p(\varphi_1, \dots, \varphi_n)$$

for all L-structures $\mathcal A$. I assume its denoted the same way $\models p(\varphi_1, \dots, \varphi_n)$ or $\models p$.


To give even more context I realized that I had a tautology and wanted to prove it from the axioms. Is:

$$ \varphi \to \exists x \varphi $$

which looks obviously true no matter what. Thus, I wanted to show that was true by using exercise (5) but (5) didn't depend on any specific tautology so that seemed odd to me.

Once I knew (5) I'd show that it is a tautology plugging in any L-structure and showing it always evaluates to True. Then invoke exercise (5).

$\endgroup$
2
  • $\begingroup$ I'm not familiar with those notes, but perhaps all the author wants you to do is to apply completeness of propositional logic and the quantifier axioms $\forall \varphi \rightarrow \varphi(t/y)$. First you claim that the propositional tautology from which $\varphi$ was obtained has a proof. Then you apply the quantification axioms to extend that proof and get $\varphi$ from the propositional tautology. $\endgroup$ Oct 1, 2018 at 3:30
  • $\begingroup$ @FabioSomenzi we are definitively not allowed to use completeness of predicate logic...I guess completeness of propositional might be legal, I'd have to think about it...didn't realize that was allowed. $\endgroup$ Oct 1, 2018 at 3:39

1 Answer 1

1
$\begingroup$

A tautology is true in every structure, so $\models \varphi$. By the Completeness Theorem, $\vdash \varphi$.

(Here $\models \varphi$ and $\vdash \varphi$ are shorthand for $\emptyset\models \varphi$ and $\emptyset \vdash \varphi$, respectively.)

Edit (in response to a comment): The proof above uses Completeness for first-order logic. With just a little more care, you can prove this using only Completeness for propositional logic.

According to the definition in your notes, a tautology is a formula of the form $p(\varphi_1,\dots,\varphi_n)$, where $p(\alpha_1,\dots,\alpha_n)$ is a propositional tautology, and $\varphi_1,\dots,\varphi_n$ are first-order formulas. So $p(\varphi_1,\dots,\varphi_n)$ means that you substitute $\varphi_i$ for $\alpha_i$ in $p$, turning the propositional formula into a first-order formula.

Since $p(\alpha_1,\dots,\alpha_n)$ is a propositional tautology, there is a propoisitional proof of $p(\alpha_1,\dots,\alpha_n)$ (by Completeness for propositional logic). Now you can check that if you substitute the $\varphi_i$ for the $\alpha_i$ everywhere in the proof, you get a first-order proof of $p(\varphi_1,\dots,\varphi_n)$. This amounts to checking that every axiom and every application of a logical rule used in the propositional proof remains an axiom or a valid application of a logical rule in the first-order proof after substituting the $\varphi_i$ for the $\alpha_i$.

$\endgroup$
2
  • $\begingroup$ I should have mentioned they didn't want us to use completeness of predicate logic (theorem 2.7.4 of the notes). My apologies! Unless your using completeness of propositional logic which I assume is legal? $\endgroup$ Oct 1, 2018 at 3:36
  • $\begingroup$ @Pinocchio Ah, I see. Edited. $\endgroup$ Oct 1, 2018 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.