TopoLogic

The Continuum Hypothesis trilogy will continue later. Today I’ll recall some discussion I made a year ago or so in the student seminar.

I guess someone would say that it is surprising, how closely related these two branches of mathematics — topology and logic — are.

Applications of logic to topology include non-standard homology theory (compare to non-standard analysis), independence results, for example properties of Cech-Stone compactification of N depend on continuum hypothesis to some extend. Also many set theoretical constructions serve as counter examples in topology. For example [tex]\omega_1[/tex] is sequentially compact, but not compact space.

I am going to give here an example of an application of topology to logic. That probably sounds even more hc, because people tend to think of logic as the foundations of mathematics. But note that logic can also be formalized in ZFC, as any other branch of mathematics.

Applications of topology to logic include Stone spaces (spaces of types — which appear Stone-Cech compactifications of certain spaces), Baire cathegory theorem is equivalent with the axiom of Dependent Choice (a weak version of the Axiom of Choice) and is considered one of the most important mathematical theorems by the leading logician of our department; determinacy of games depends on topological (Borel/Analytic/etc) properties of certain sets…

Tychonoff’s theorem implies the compactness theorem of proposition logic.

Denote P = the set of proposition symbols = [tex]\{p_0, p_1,\dots\}[/tex] a set indexed by natural numbers. The set PL of the propositional sentences is the smallest set of finite strings such that

1. [tex]P \subset PL[/tex]
2. [tex]a \in PL \Rightarrow \lnot a \in PL[/tex]
3. [tex]a,b \in PL \Rightarrow; a\land b \in PL[/tex]

Using these, one can define disjunction, implication etc. Next let us define truth. A valuation function is a function [tex]v:P \to \{0,1\}[/tex]. From now on denote 2 = {0,1}. One for true, zero for false. This defines recursively the truth of all sentences as follows:

1 if [tex]v(a)[/tex] is defined, then [tex]v(\lnot a) = 1-v(a)[/tex]
2 if [tex]v(a)[/tex] and [tex]v(b)[/tex] is defined then [tex]v(a\land b)=v(a)v(b).[/tex]

If T is a collection of proposition sentences (a theory) and v is a valuation function,
we denote v(T) = 1 if the case is that v(a) for every a in T.

Now we can state the compactness theorem:

Let T be a theory. There exists a [tex]v:P \to 2[/tex] such that [tex]v(T)=1[/tex] if and only if for every finite subset T’ of T there exist a v such that [tex]v(T’)=1[/tex].

I will not explain here the standard proof of this given in textbooks. We see that the direction “only if” is trivial in this context. The other direction we obtain as follows. Let [tex]X = 2^P[/tex] = {all valuation functions} with product topology. This is known as the Cantor set. It is compact by Tychonoff’s theorem above. The basis of the topology is

[tex]A_n = \{v\in X | v(p_n)=1\}\text{ and }B_n = \{v\in X | v(p_n)=0\}.[/tex]

It is then clear that in fact [tex]A_n[/tex] is the complement of [tex]B_n[/tex], thus the basic sets are clopen. Closed and open so to say. Let a be a proposition sentence. It is a finite string, so there occures only finitely many proposition symbols [tex]p_0, p_1,\dots[/tex] Thus [tex]C_a = \{v\in X | v(a)=1\}[/tex] is a finite intersection of basic sets, hence closed. Our assumption implies that every finite intersection of sets [tex]C_a, a\in T[/tex] is non-empty. We have to show that the intersection of all [tex]C_a, a\in T[/tex] is non-empty. But if it is empty, then the complements of [tex]C_a[/tex]’s form an open cover of our compact space, which have the finite subcover, whose complements intersection would be empty. A contradiction.

About Vadim Kulikov

For details see this
This entry was posted in Logic, Mathematics, Topology. Bookmark the permalink.

2 Responses to TopoLogic

  1. Thinking. It’s always the same thing. To think is to go crazy.

  2. Pingback: Walks On Math » Map Colouring Problem And Compactness

Leave a Reply

Your email address will not be published.