
## 4 Proofs 4.1 Proofs Of Propositions 3 And 4

Lemma 2. *For any formulas* F1, . . . , Fn (n ≥ 0), any set X *of atoms, and any* connective ⊗ ∈ {∨,∧}, (F1 **⊗ · · · ⊗** Fn)
X *is classically equivalent to* F
X
1 **⊗ · · · ⊗**
F
X
n
.

Proof. Case 1: X |= F1 **∧ · · · ∧** Fn. Then, by the definition of reduct, (F1 **∧ · · · ∧**
Fn)
X = F
X
1 **∧· · ·∧**F
X
2
. Case 2: X 6|= F1**∧· · ·∧**Fn. Then (F1**⊗· · ·⊗**Fn)
X = ⊥;
moreover, one of F1, . . . , Fn is not satisfied by X, so that one of F
X
1
, . . . , F X
nis
⊥. The case of disjunction is similar.

Proposition 3. For any formula F *and any HT-interpretation* (X, Y ), (X, Y ) |= F
iff X |= F
Y.

Proof. It is sufficient to consider the case when Γ is a singleton {F}, where F contains only connectives ∧, ∨, → and ⊥. The proof is by structural induction on F.

- F is ⊥. X 6|= ⊥ and (X, Y ) 6|= ⊥.

- F is an atom a. X |= a Yiff Y |= a and X |= a. Since X ⊆ Y , this means iff X |= a, which is the condition for which (X, Y ) |= a.

- F has the form G∧H. X |= (G∧H)
Yiff X |= GY ∧HY by Lemma 2, and then iff X |= GYand X |= HY. This is equivalent, by induction hypothesis, to say that (X, Y ) |= G and (X, Y ) |= H, and then that (X, Y ) |= G ∧ H.

- The proof for disjunction is similar to the proof for conjunction.

- F has the form G → H. X |= (G → H)
Yiff X |= GY → HYand Y |= G → H, and then iff
X |= G
Yimplies X |= H
Y, and Y |= G → H.

This is equivalent, by the induction hypothesis, to
(X, Y ) |= G implies (X, Y ) |= H, and Y |= G → H,
which is the definition of (X, Y ) |= G → H.