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.

First order logic: "consistency," "compactness"?

Consistency: A set sigma ⊆ WFF is consistent iff there is no ϕ ∈ WFF such that sigma ⊢ ϕ and sigma ⊢ (¬ϕ)

Compactness: A set sigma is consistent iff every finite sigma_0 ⊆ sigma is consistent

I have read through these definitions, however I still feel like I do not understand them. Can someone respond and break them down for me in simpler terms? I feel more confident in my abilities if I understand them to the fullest and their application.

Thank you

share|improve this question
    
What definitions? They are missing. –  Guy Coder Dec 10 '12 at 1:31
    
I don't think that a general explanation of consistency and compactness is the sort of question that the FAQ for the site asks for. In particular, it is hard to see that there is a correct answer to the question, such as it is. The FAQ says, " If you can imagine an entire book that answers your question, you’re asking too much." For that reason, I voted to close. However, the question could be improved by asking about the specific thing that you would like to know about. –  Carl Mummert Dec 10 '12 at 1:33
    
could you explain them further then the definitions? –  Masterminder Dec 10 '12 at 1:35
add comment

1 Answer

The definition of a theory being consistent is that it can not prove both $\varphi$ and $\neg\varphi$. However an alternative way of think about a theory $T$ in the language $\mathcal{L}$ being consistent is that $T$ can not prove all $\mathcal{L}$ sentences. In this way an inconsistent theory is not very intersesting since $T$ can prove every sentence. Moreover, a theory being consistent also means that it has a model, i.e. a $\mathcal{L}$-structure $\mathcal{M}$ such that $\mathcal{M} \models \varphi$ for all $\varphi \in T$.

The compactness theorem of logic states that a theory $T$ is consistent if and only if every finite $\Lambda \subset T$ is consistent. Model theoretically, $T$ has a model if and only every finite set of sentences of $T$ has a model. In practice, it often fairly easy for certain theories to construct models for any finite collection of sentences. Then using the compactness theorem, you can conclude the whole (possible infinite theory $T$) has a model (i.e. is consistent) without explicitly producing a model for $T$.

share|improve this answer
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.