Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Is it possible to give a formal proof for the above?

share|cite|improve this question
    
Yes it is indeed possible to give a formal proof. And it is proved in many textbooks. Which have you looked at? – Peter Smith Nov 6 '12 at 17:42
    
i hav not looked at any textbooks as yet.can you please give any reference.so far i have been sticking to my notes only. – heboy Nov 6 '12 at 17:47
    
I know not the tastes of others, but I learned my set theory from Bourbaki.Hope you like it. – awllower Nov 6 '12 at 17:56
3  
You might want to take a look at Enderton, H. B. (2002) A Mathematical Introduction to Logic, Harcourt/Academic Press, ISBN 0-12-238452-0. Note that in first order logic, such tautologies (or formulas which have "tautological shape in propositional logic) are a proper subset of logically valid formulas, which I presume you know. – amWhy Nov 6 '12 at 18:05

The only way I can make sense of "tautological shape" is to suppose a formula $\psi$ is of the form: $$\psi = \alpha[\phi_1 / p_1, \dots,\phi_n/p_n]$$ where $/$ denotes substitution (adequately defined), for some first-order formulas $\phi_i$ and a propositional tautology $\alpha$ in the variables $p_i$.

Now let $\mathcal M$ be a structure for $\psi$ and let $v: {\sf Var} \to \mathcal M$ be an assignment of variables, both arbitrary.

The crux is to define the boolean interpretation $v': \{p_1,\dots,p_n\} \to \{T,F\}$ by: $$v'(p_i) = \begin{cases}T&\text{ if $\mathcal M,v \models \phi_i$}\\F&\text{ if $\mathcal M, v \not\models \phi_i$}\end{cases}$$ and subsequently demonstrate by induction on the complexity of propositional formulas $\beta$ in the symbols $p_i$ that: $$v'(\beta) = T \iff \mathcal M,v\models \beta[\phi_i/p_i]$$ Having established this equivalence, since $\alpha$ is a tautology, we conclude that $\mathcal M,v \models \psi$ for all structures $\mathcal M$ and assignments $v$; that is, $\psi$ is valid.

share|cite|improve this answer

You might want to have a look at any proper proof of Herbrand's Theorem. There, $\forall \vec{y}\exists \vec{x}\phi_{qf}(\vec{x},\vec{y})$ sentences are transformed into a finite quantifier-free disjunction $\phi_{qf}(\vec{c_x},\vec{t_{1}})\vee\dots\vee\phi_{qf}(\vec{c_x},\vec{t_{n}})$; this disjunction, interpreted as a formula in propositional logic (!), is a tautology if and only if the original sentence was already valid.

The proof of this will contain some justification about the part where the quantifier-free disjunction is interpreted as a propositional formula. Basically, this should be straightforward. You define an injective mapping which assigns propositional variables to atoms such that exactly thos atoms which are syntactically equivalent are assigned the same variables. Then you do some argumentation based on the semantics of first-order and propositional logic; basically, these semantics should coincide for the "propositional" part of first-order logic.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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