Exercise verification: No topology over a finite set generates as a set of theorems precisely the intuitionistic tautologies.

Question

This answer to this question I asked yesterday contains the following exercise (emphasis mine):

Let $Σ$ denote the underlying set of the Sierpiński space. Are the propositional formulae $φ$ for which $τ⊨φ$ for every topology $τ$ on the set $Σ$ precisely the intuitionistic tautologies?

The answer to this question is negative. Up to isomorphism, there are three different topologies on the two-element set. One of them is the Sierpiński topology itself, and you already know that one doesn't work by itself. The others two topologies are (in)discrete, so satisfy all Boolean identities. In fact, it follows from previously mentioned results (exercise!) that no other finite set $Σ$ is going to work either.

Here is my attempt to prove this result. The basic idea of my proof is that if $|\tau| = n$, then there exists a partition of $n+1$ distinct variables $x_i$ through $x_{n+1}$ into two parts $(a_1, a_2, \cdots)$ and $(b_1, b_2, \cdots)$ such that $(a_1 \land a_2 \land \cdots) \to (b_1 \lor b_2 \lor \cdots)$ is a tautology in the $\tau$-semantics but is not an intuitionistic tautology.

Suppose I have a topology $\tau$ over a finite set $\Sigma$. Since $\Sigma$ is finite, $\tau$ is also finite, with cardinality at most $2^{|\Sigma|}$. Let $n$ be the cardinality of $\tau$.

For ease of writing, let me define the following connective $\Delta((\cdots), \cdots)$.

$\Delta((x_1, x_2, \cdots), y_1, y_2, \cdots)$ is defined as $(x_1 \land x_2 \cdots) \to (y_1 \lor y_2 \lor \cdots)$.

Let $v$ be a sequence of $n+1$ distinct variables. Since $n+1$ > $n$, there is at least one pair of distinct variables that have the same value, for any fixed valuation.

Fix a valuation $x$ and suppose the value of $x_1$ is equal to the value of $x_2$.

I claim that the following is true for the valuation $x$.

$$ \Delta((x_1), x_2, x_3, \cdots) \;\; \text{is true for the topology $\tau$ and valuation $x$} $$

To prove this, let's examine what $\Delta$ looks like in the topological semantics, let $^o$ be the interior operator.

$$ (x_1^c \cup x_2 \cup x_3 \cup \cdots)^o $$

Since $x_1 = x_2$, this is equivalent to the following.

$$ ((\cup \tau) \cup x_3 \cup \cdots) ^ o $$

This is just equal to the entire space $\cup \tau$.

However, when we fixed $x$ we made an assumption that $x_1$ = $x_2$. For an arbitrarily chosen valuation, though, we don't know which variables will have the same values. We can hedge our bets, though, and consider them all in the sentence $\varphi(\tau)$, defined below. Let $e$ be a sequence of variable symbols.

$$ \varphi(\tau) = \Delta((e_1), e_2, \cdots, e_{n+1}) \lor \Delta((e_2), e_1, e_3, \cdots, e_{n+1}) \lor \cdots \lor \Delta((e_{n+1}), e_1, \cdots, e_n) $$

This sentence is intuitionistically false, because for the complete semantics $\tau^R$ (the standard topology on the real line), we can pick $n+1$ non-overlapping open intervals .

Answer 1

Let $e_i$ denote distinct propositional variable symbols. You consider the following formula: $$\varphi_n \equiv \bigvee_{i\leq n} \left( e_i\rightarrow\bigvee_{j\neq i,j \leq n}e_j\right).$$

You choose $n$ big enough that every topology on the finite set $\Sigma$ has less than $n$ opens. Then any topology $\tau$ on $\Sigma$ satisfies $\tau \models \varphi_n$, since no matter which open sets $[e_i]$ we use to interpret $e_i$, by a pigeonhole argument we can find two indices $a,b$ such that $[e_a] = [e_b]$. This means that we have $[e_a \rightarrow e_b] = \Sigma$, and therefore $[e_a\rightarrow\bigvee_{j\neq a,j \leq n}e_j] = \Sigma$, and consequently $[\varphi_n] = \Sigma$ as well. Your reasoning is correct.

You also note that each $\varphi_n$ has an interpretation in $\tau^R$ which does not coincide with all of $\mathbb{R}$, which is true, and enough if it convinces you. If I was presenting this proof in a classroom setting, I'd write down at least some of the required calculations/observations.

Let me just note that one can easily prove that $\varphi_n$ is not an intuitionistic tautology using proof-theoretic methods, without invoking completeness of $\tau^R$. For if $\vdash \varphi_n$ had a proof in the sequent calculus LJ, then by the existence property, we would be able to prove one of the disjuncts of $\varphi_n$. By using the disjunction property yet again, we'd get that we can prove $e_i \vdash e_j$ for some $i \neq j$. However, it's clear that $e_i \vdash e_j$ has no cut-free proof (and therefore no proof) in the sequent calculus LJ.