For example, the statement S = “There exists an a with a*a = 2″ is true in R, but false in Q since the square root of 2 is irrational. Similarly, the statement T = “There exists an a with a*a = -1″ is true in C, but false in R (the imaginary unit i satisfies the statement in C).

[]

Hence, if you believe the Soundness Theorem, we should not expect to be able to prove either S or (not S) from F because there is one model of F in which S is true, and one where S is false. Similarly, we should not expect to be able to prove either T or (not T). Thus, our system F is incomplete, i.e. there are statements X such that we can neither prove X nor (not X).

[]

However, there are [] good reasons why it is incomplete [;] there are statements which can be either true or false depending on which model of F you are currently working.

The Completeness Theorem basically says that this is the only way a system can be incomplete. In other words, the above converse question is true, which implies that we can prove absolutely everything that is not ruled out for the above basic reason.

— Godel’s Completeness Theorem

— Joe Mileti

2013.07.17 Wednesday ACHK