User:IssaRice/Computability and logic/Semantic completeness

Semantic completeness is sometimes written as: if $\mathrm{\Sigma }\models \varphi$, then $\mathrm{\Sigma }⊢\varphi$.

Semantic completeness is the completeness that is the topic of Godel's completeness theorem.

Semantic completeness differs from negation completeness.

Semantic completeness is about the completeness of a logic (not about the completeness of a theory).

Definition

I want to make sure all these definitions are saying the same thing, so let me list some from several textbooks so I can explicitly compare.

Smith's definition: a logic is semantically complete iff for any set of wffs $\mathrm{\Sigma }$ and any sentence $\varphi$, if $\mathrm{\Sigma }\models \varphi$ then $\mathrm{\Sigma }⊢\varphi$.

Leary/Kristiansen's definition: A deductive system consisting of logical axioms $\mathrm{\Lambda }$ and a collection of rules of inference is said to be complete iff for every set of nonlogical axioms $\mathrm{\Sigma }$ and every $\mathcal{L}$-formula $\varphi$, if $\mathrm{\Sigma }\models \varphi$, then $\mathrm{\Sigma }⊢\varphi$.

Alternative formulation

It is possible to formulate completeness by saying that a consistent set of sentences is satisfiable. In other words, the following are equivalent:

1. Let $\mathrm{\Gamma }$ be a set of sentences, and let $\varphi$ be a sentence. If $\mathrm{\Gamma }\models \varphi$, then $\mathrm{\Gamma }⊢\varphi$.
2. Let $\mathrm{\Gamma }$ be a set of sentences. If $\mathrm{\Gamma }$ is consistent, then $\mathrm{\Gamma }$ is satisfiable (has a model).

Proof idea

The first trick in the proof is to notice that the $\mathrm{\Gamma }$ that appears in (1) is not the same as the $\mathrm{\Gamma }$ that appears in (2). Since $\mathrm{\Gamma }$ is an arbitrary set of sentences in each of (1) and (2) (i.e. each statement is surrounded by "for all $\mathrm{\Gamma }$ …"), we can use a different set of sentences than the arbitrary $\mathrm{\Gamma }$ we are given. If you try to use the same $\mathrm{\Gamma }$ in both places, your proof will go nowhere.

In other words, the statement of the proposition obfuscates the situation a bit by using the same symbol for "different things" in the proof. One might ask why one would obfuscate things this way; one response is that if you're just stating one of the formulations in isolation, you would just use your "default variable" for a set of sentences. For instance, if you tend to use $\mathrm{\Gamma }$ for a set of sentences, then if someone asked you to state (1), you would use $\mathrm{\Gamma }$. Then if someone asked you to state (2) a few weeks later, you wouldn't use $\mathrm{\Delta }$ or $\mathrm{\Sigma }$ unless you had (1) in mind.

The other trick is to figure out just what to use as $\mathrm{\Gamma }$ when going from (2) to (1), and to figure out what to do with $\varphi$ when going from (1) to (2).

The rest of the proof is some routine manipulations.

Proof

Suppose (1) is true. We will prove the contrapositive of (2). Let $\mathrm{\Gamma }$ be a set of sentences, and suppose $\mathrm{\Gamma }$ is unsatisfiable. Let $\mathrm{\perp }$ be a contradictory sentence, such as $\varphi \wedge \mathrm{\neg }\varphi$. Now, since $\mathrm{\Gamma }$ is unsatisfiable, there is no structure $\mathfrak{A}$ such that $\mathfrak{A}\models \mathrm{\Gamma }$. This means that vacuously, for every $\mathfrak{A}$ such that $\mathfrak{A}\models \mathrm{\Gamma }$, we have $\mathfrak{A}\models \mathrm{\perp }$. Thus we have $\mathrm{\Gamma }\models \mathrm{\perp }$. Now by (1) (with $\mathrm{\perp }$ serving the role of "$\varphi$"), this means $\mathrm{\Gamma }⊢\mathrm{\perp }$, which shows that $\mathrm{\Gamma }$ is inconsistent, as desired.

Now suppose (2) is true. Let $\mathrm{\Gamma }$ be a set of sentences, let $\varphi$ be a sentence, and suppose $\mathrm{\Gamma }\models \varphi$. We will first show that $\mathrm{\Gamma }\cup \{\mathrm{\neg }\varphi \}$ is unsatisfiable. Suppose for the sake of contradiction that $\mathrm{\Gamma }\cup \{\mathrm{\neg }\varphi \}$ is satisfiable. Then we would have a structure $\mathfrak{A}$ such that $\mathfrak{A}\models \mathrm{\Gamma }\cup \{\mathrm{\neg }\varphi \}$. This means $\mathfrak{A}\models \mathrm{\Gamma }$ and $\mathfrak{A}\models \mathrm{\neg }\varphi$. Since $\mathrm{\Gamma }\models \varphi$, this means $\mathrm{\Gamma }\models \varphi$. So we have both $\mathfrak{A}\models \varphi$ and $\mathfrak{A}\models \mathrm{\neg }\varphi$, a contradiction. This proves that $\mathrm{\Gamma }\cup \{\mathrm{\neg }\varphi \}$ is unsatisfiable.

Since $\mathrm{\Gamma }\cup \{\mathrm{\neg }\varphi \}$ is unsatisfiable, by (2) we have that $\mathrm{\Gamma }\cup \{\mathrm{\neg }\varphi \}$ is inconsistent. This means $\mathrm{\Gamma }\cup \{\mathrm{\neg }\varphi \}⊢\mathrm{\perp }$, so $\mathrm{\Gamma }⊢\mathrm{\neg }\varphi \to \mathrm{\perp }$, which means $\mathrm{\Gamma }⊢\varphi$, which is what we wanted.

Proof commentary

In proving (1) ⇒ (2), we only needed that "if $\mathrm{\Gamma }$ is unsatisfiable, then $\mathrm{\Gamma }\models \mathrm{\perp }$". However, it is also possible to prove the converse, and show that if $\mathrm{\Gamma }$ is satisfiable, then $\mathrm{\Gamma }\models ̸\mathrm{\perp }$. Some books factor out both sides of this implication as a lemma.