Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know that given a sentence or formula of a formal system, this formula is a logical truth if it is true under all interpretations.

Is it possible to define this same concept of logical truth without the reference to models and interpretations?

Thanks!

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

For first-order logic this is essentially the completeness theorem.

The completeness theorem tells us that if $T$ is a first-order theory, then $\varphi$ is provable from $T$ if and only if $\varphi$ is true in every model of $T$.

If a formula is logically true it means that it is true in every interpretation. Every interpretation is a model for the empty theory, and so by the completeness theorem we can say that something is logically true if and only if it is provable from $\varnothing$.

share|improve this answer
    
What does the quantifier "every" run over? –  alancalvitti Feb 15 '13 at 4:28
    
@alancalvitti: Where? –  Asaf Karagila Feb 15 '13 at 4:33
    
"true in every interpretation. Every interpretation is a model..." - is there a set of all interpretations or similar quantifiable object? –  alancalvitti Feb 15 '13 at 15:35
    
@alancalvitti: No. But there is no set of ordinals when I quantify over "Every ordinal is a transitive set". The class is definable and therefore we can quantify over its elements. –  Asaf Karagila Feb 15 '13 at 15:40
    
When I wrote similar, I meant perhaps class or category if not set. Are interpretations well-ordered and can we do induction over them like ordinals? Do they form a category? –  alancalvitti Feb 15 '13 at 15:51
show 16 more comments

The common distinction is between syntactical truth and semantic truth. Given a deduction system (i.e., some rules telling us what which strings are allowed and how to deduce new the syntactical truth of a sentence given the syntactical truth of others) you get a well-defined notion of syntactic truth as those statements that are derivable in the deduction system from a given theory.

In contact, semantic truth relates to a given model and is means those statements that when interpreted in $M$ are true.

Goedel's completeness theorem states that (for first order logic) in a deduction system, a statement is syntactically true given a theory $T$ if, and only if, it is semantically true in all models of $T$. So, this answers your question.

The fact that syntactic truth implies semantic truth is quite easy to prove. The other direction is involved and requires a slightly weaker axiom than the axiom of choice.

share|improve this answer
1  
Six seconds, oh snap. :-) –  Asaf Karagila Feb 15 '13 at 2:57
    
oh my god :D :D –  Ittay Weiss Feb 15 '13 at 2:58
add comment

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.