3
$\begingroup$

It is claimed in some logic books that the compactness theorem of first-order logic can be proven using Tychnoff's theorem from topology.

Now, to me this feels very strange because I consider logic as something "lower" in the sense that the theorems of topology follow from the axioms and theorems in logic. How can we avoid circularities then?

Another small question I have is that if we have $A \iff B$ and we prove both directions with contraposition, does there exist a direct proof? You could say we could just follow the steps backwards, but is this always possible?

  • 0
    Jonas: You do not need compactness or completeness to prove Tychonoff's theorem, so there is no circularity. The use of topological arguments in logic is actually very fruitful.2010-11-10
  • 0
    You could define a topology on the sentences and have the theory as a product of compact spaces.2010-11-10

2 Answers 2

3

When we study mathematical logic, we use the same mathematical methods that would be used to study any other area (algebra, analysis, topology, etc.). This includes the use of set-theoretical techniques. Otherwise, we would be needlessly hamstringing ourselves. In principle, the results that we obtain could be built up entirely from primitive axioms, just like the rest of mathematics; but just like the rest of mathematics complete formalization is not usually the goal.

However, even ignoring those practical considerations, it's not hard to see that none of the axioms of point set topology or set theory used in topology presuppose that the compactness theorem of logic holds. So there is no circularity if we use topological methods to prove the compactness theorem.

1

For the second question, suppose that in some proof system you can prove $p(x) \Leftrightarrow q(x)$ for some expressions $p,q$, and only $p(x)\Rightarrow q(x)$ requires proof by contradiction. Then to prove $p(x) \land q(y) \Leftrightarrow q(x) \land p(y)$ you probably need proof by contradiction on both sides.

If you only know that $p(x) \Rightarrow q(x)$ requires proof by contradiction ($p(x) \Leftarrow q(x)$ not necessarily being true), then $p(x) \Rightarrow p(x) \land q(x)$ also probably requires proof by contradiction, and this time both sides are equivalent.

  • 0
    Is there any difference if the proof is by _contraposition_ instead of contradiction? By the way, to summarize what you said, the answer to my question is: Not always?2010-11-10
  • 0
    If you want a real answer, you need to decide what a proof by contraposition/contradiction is. For example, you could side a statement uses these principles if it isn't true (can't be proven) in intuitionistic logic. For example, $\lnot \lnot A \Rightarrow A$ isn't true intuitionisticly. The rest probably works with this definition of "requires proof by contradiction/contrapositive".2010-11-11