Not logged in. · Lost password · Register

SLWINF
Member since Oct 2014
54 posts
Subject: completeness
I thought completeness is this H |= A then H  |- A
In exercise 9.3 it is : H |= A IFF H  |- A
Are we actually supposed to show both directions ? Do I miss something ? Or is this an error?
Jazzpirate
Member since Oct 2016
803 posts
Good question!

Technically, the direction "If H |= A then H  |- A" is what's called completeness. The other direction is called soundness.

However, any calculus which is *unsound* is basically useless and inadequate for any purposes (recall what it would mean if a calculus is unsound: Then I can prove things that aren't true!), so we only ever consider calculi that are sound. Hence, *given* that a calculus is (supposed to be) sound anyway, the two statements "If H |= A then H  |- A" and "H |= A IFF H  |- A" are equivalent.
Jazzpirate
Member since Oct 2016
803 posts
In reply to post #1
Possibly relevant: You may accordingly *without loss of generality* assume the calculus in your proof to be sound ;)
rappatoni
Member since Nov 2018
26 posts
Subject: Completeness and Model Existence
A little aside: one direction of the Model Existence Theorem (If you cannot derive a contradiction from H then H has a model) is equivalent to the strict definition of completeness (H |= A then H  |- A). This is a very useful equivalence which is often used to prove completeness of a logic: the proof then boils down to picking an arbitrary consistent set of formulae and constructing a model for it (the "canonical" model).
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen