PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 82(96) (2007), 107–110 DOI 102298/PIM0796107P

FORCING WITH PROPOSITIONAL LINDENBAUM ALGEBRAS

Aleksandar Perović

Abstract. We prove equivalence between the forcing with propositional Lindenbaum algebras and the Cohen forcing with finite partial functions.

1. Introduction

Let ℙ be an infinite set of propositional letters and let For ℙ be the corresponding set of propositional formulas. It is easy to see that the relation ∼ on For ℙ, defined by

A ∼ B iff A ⇔ B is tautology,

is a Boolean congruence. The Lindenbaum algebra of ℙ, denoted by B(ℙ), is defined as follows:

• The universe of B(ℙ) is the set For ℙ/∼;

• [A] ⩽ [B] iff A ⇒ B is tautology. As it is usual in mathematics, we will slightly abuse notation and identify B(ℙ) with its universe. One can easily show that B(ℙ) ∖ {[A ∧ ¬A]} is a nonatomic separative ordering, hence forcing with B(ℙ) adds new sets in generic extensions. In fact, we will show that forcing with propositional Lindenbaum algebras is exactly the Cohen forcing with finite partial functions.

The rest of the paper is organized as follows: in Section 2 we list the facts needed for the main result; in Section 3 we prove the main theorem; we conclude in Section 4.

2. Dense embeddings

Our notation is standard and closely follows [4]. For the definition and basic properties of forcing we refer the reader to [1, 2, 4]. Here we will state some facts about dense embeddings, which are the main tool for the unification of different notions of forcing. As before, we will slightly abuse notation and identify posets with their universes.

2000 Mathematics Subject Classification: 03E35.

Definition 2.1. Suppose that P and Q are arbitrary posets and i : P → Q. We say that i is a dense embedding if:

(1) for all p, p′ ∈ P, p ⩽ p′ implies i(p) ⩽ i(p′);

(2) for all p, p′ ∈ P, p and p′ are incompatible in P iff i(p) and i(p′) are incompatible in Q;

(3) i[P] is dense in Q, i.e., if for each q ∈ Q there exists p ∈ P such that i(p) ⩽ q.

If i : P → Q is a dense embedding, then we define i_{∗} : V^{P} → V^{Q} as follows:

i_{∗}(σ) = {⟨i_{∗}(τ, i(p))⟩ | ⟨τ, p⟩ ∈ σ}.

The next fact gives us a connection between the complete embeddings and forcing. For the proof we refer the reader to [4].

Fact 2.1. Suppose that M be a countable transitive model of ZFC, i, P, Q ∈ M, and

M ⊧ “i : P → Q is a dense embedding”.

If G ⊆ P, let

ĩ(G) = {q ∈ Q | (∃p ∈ G)(i(p) ⩽ q)}.

Then:

(1) If H ⊆ Q is Q-generic over M, then i^{−1}(H) is P-generic over M and H = ĩ(i^{−1}(H)).

(2) If G ⊆ P is P-generic over M, then ĩ(G) is Q-generic over M and G = i^{−1}(ĩ(G)).

(3) If G = i^{−1}(H) (or, equivalently, if H = ĩ(G)), then M[G] = M[H].

Note that the notions of complete and dense embeddings are absolute for tranzitive models of ZFC.

For the main result we will also need the Cohen notion of forcing. Let κ be an infinite cardinal. The Cohen forcing, Fn(κ, 2), is the set of finite partial functions from κ to 2, ordered by the reversed inclusion.

3. The main theorem

As we suggested earlier, we want to prove the equivalence between the Cohen forcing with finite functions and the forcing with propositional Lindenbaum algebras.

Theorem 3.1. Let ℙ be an infinite set of propositional letters. Then, the forcing with B(ℙ) is equivalent with the Cohen forcing with Fn(κ, 2), where κ = |ℙ|.

Proof. According to (3) of 2.1, it is sufficient to prove that Fn(κ, 2) densely embeds into B(ℙ). Here by B(ℙ) we actually mean B(ℙ) ∖ {[A ∧ ¬A]}. Let

ℙ = {p_{ξ} | ξ < κ}.

We define the function i : Fn(κ, 2) → B(ℙ) by i(p) = [ ⋀_{ξ∈dom(p)} p_{ξ}^{p(ξ)}], where p^{0} = ¬p and p^{1} = p. To conclude the proof, we need to verify that i satisfies (1),

(2) and (3) of Definition 2.1.

(1): Let p, q ∈ Fn(κ, 2) and let p ⊇ q. Then, dom(q) = {ξ_{1}, …, ξ_{m}}, dom(p) = {ξ_{1}, …, ξ_{m}, η_{1}, …, η_{n}}, ξ_{k} ≠ η_{j}, and p(ξ_{k}) = q(ξ_{k}). By the definition of i,

i(p) = [ ⋀_{j=1}^{m} p_{ξ_{j}}^{q(ξ_{j})} ∧ ⋀_{k=1}^{n} p_{η_{k}}^{p(η_{k})}], i(q) = [ ⋀_{j=1}^{m} p_{ξ_{j}}^{q(ξ_{j})}],

and since the formula

⋀_{j=1}^{m} p_{ξ_{j}}^{q(ξ_{j})} ∧ ⋀_{k=1}^{n} p_{η_{k}}^{p(η_{k})} ⇒ ⋀_{j=1}^{m} p_{ξ_{j}}^{q(ξ_{j})}

is clearly a tautology, we have that i(p) ⩽ i(q). Hence, (1) holds.

(2): Suppose that p, q ∈ Fn(κ, 2) are incompatible. Then, there is ξ ∈ dom(p)∩ dom(q) such that p(ξ) = 1−q(ξ). In particular, i(p) ⩽_{B(ℙ)} [p_{ξ}^{p(ξ)}], i(q) ⩽_{B(ℙ)} [p_{ξ}^{q(ξ)}],

and [p_{ξ}^{p(ξ)}] and [p_{ξ}^{q(ξ)}] are incompatible in B(ℙ), since the formula ¬(p_{ξ}^{p(ξ)}∧ p_{ξ}^{q(ξ)}) is a tautology. Thus, i(p) and i(q) are incompatible as well. The converse implication of (2) can be proved similarly.

(3): Pick an arbitrary [A] ∈ B(ℙ). By the DNF theorem,

[A] = [ ⋁_{j=1}^{m} ⋀_{k=1}^{n} p_{ξ_{jk}}^{a_{jk}}],

where a_{jk} ∈ 2. If we define condition p ∈ Fn(κ, 2) by dom(p) = {ξ_{11}, …, ξ_{1n}} and p(ξ_{1k}) = a_{1k}, then it is easy to see that i(p) ⩽ [A], which proves (3). □

4. Conclusion

First, we notice that the embedding i defined in the proof of Theorem 3.1 is quite natural: p_{ξ} stands for “ξ maps to 1”, while ¬p_{ξ} stands for “ξ maps to 0”. In this way, finite conjunctions of literals nicely represent finite partial functions.

Second, it is well known that, up to isomorphism, every Boolean algebra is a Lindenbaum–Tarski propositional algebra B(T) (see [3]). Recall that B(T) is defined by

A ∼ B iff T ⊢ A ⇔ B,

where T is certain propositional theory. In this way, every notion of forcing may be seen as a B(T) forcing. Still, it would be interesting to see what kind of propositional theory T naturally corresponds to particular notion of forcing P. Here “natural” should be understood as a kind of correspondence that exists between Fn(κ, 2) and B(ℙ). We notice that such correspondence is not given by the proof of the characterization of Boolean algebras via Lindenbaum–Tarski propositional algebras.

References

[1] T. Jech, Multiple Forcing, Cambridge University Press, 1986.

[2] T. Jech, Set Theory, The Third Millennium Edition, revised and expanded Series, Springer Monographs in Mathematics, 3rd rev. ed., 2003.

[3] S. Koppelberg, General theory of Boolean algebras, in: D. Monk, R. Bonnet (editors), Handbook of Boolean Algebras, Volume 1, Elsevier, 1989.

[4] K. Kunen Set Theory. An Introduction to Independence Proofs, Studies in Logic and the Foundations of Mathematics, 102. North-Holland, Amsterdam–New York, 1980.

Saobraćajni fakultet Vojvode Stepe 305 11000 Beograd Serbia

pera@sf.bg.ac.yu