How to prove equivalence of different definitions for compactness?

347 Views Asked by At

My workbook considers three different definitions for compactness in logic. It says that it can be shown that these are equivalent, but what would be a strategy to show this? I'm familiar with showing equivalence of formulas by showing that they have the same truth-table, but what would be the strategy for definitions?

The definitions are the following:

(1) A logic can be considered as compact if and only if for every set of sentences Γ and sentence ϕ, if Γ |= ϕ, then, for some finite ∆ ⊆ Γ, ∆ |= ϕ.

(2) A logic can be considered as compact if and only if for every set of sentences Γ, if every finite ∆ ⊆ Γ is satisfiable, then Γ is satisfiable.

(3) A logic can be considered as compact if and only if for every set of sentences Γ, if Γ is unsatisfiable, then there is some finite ∆ ⊆ Γ which is unsatisfiable.

1

There are 1 best solutions below

0
On BEST ANSWER

HINT:

For $(3)$ implies $(1)$: Suppose $(3)$ holds, and suppose $\Gamma\models\varphi$. Then consider the set $\Gamma\cup\{\neg\varphi\}$. This is unsatisfiable (why?) so some finite subset $\Delta\cup\{\neg\varphi\}$ is unsatisfiable by (3); but then $\Delta\models\varphi$ (why?).

For $(1)$ implies $(2)$: Suppose $(1)$ holds, and suppose $\Gamma$ is unsatisfiable. Then (fix some arbitrary $\varphi$) $\Gamma\models \varphi\wedge\neg\varphi$ (why?). By $(1)$, for some finite $\Delta\subset \Gamma$ we have $\Delta\models \varphi\wedge\neg\varphi$, so this $\Delta$ is unsatisfiable (why?).

For $(2)$ implies $(3)$: think about contrapositives . . .


Note that there's an assumption in the arguments above that the logic includes negation, $\neg$. This is in fact necessary: there are logics without negation which are compact in the sense of (2) and (3), but not (1). Coming up with such an example is a good exercise . . .