Boolean valued second order logic
Daisuke Ikegami
Tokyo Denki University
Joint work with Jouko Väänänen

1st of December, 2016

In this talk...

We will work on 2nd-order logic.

Review; 1st-order logic
1st-order logic enjoys several nice properties:• Completeness Theorem• The set of (Gödel numbers of) valid sentences is Σ01 .
• Compactness Theorem• Löwenheim-Skolem-Tarski Theorem

Review; 1st-order logic
1st-order logic enjoys several nice properties:• Completeness Theorem• The set of (Gödel numbers of) valid sentences is Σ01 .
• Compactness Theorem• Löwenheim-Skolem-Tarski Theorem

How about 2nd-order logic?

2nd-order logic; Two semantics

1. Henkin semantics: Very simple (very week), essentiallythe same as 1st-order logic
2. Full semantics: Highly complex (very powerful), does
NOT enjoy completeness, compactness.

Full semantics
Full semantics = semantics with full 2nd-order structures

Definition
Full 2nd-order structures are those of the form
M = (A, P(A), . . .).

Full semantics
Full semantics = semantics with full 2nd-order structures

Definition
Full 2nd-order structures are those of the form
M = (A, P(A), . . .).

Theorem (Väänänen?)
The set of valid 2nd-order sentences with full semantics isΠ2 -complete in the language of set theory.

Full semantics
Full semantics = semantics with full 2nd-order structures

Definition
Full 2nd-order structures are those of the form
M = (A, P(A), . . .).

Theorem (Väänänen?)
The set of valid 2nd-order sentences with full semantics isΠ2 -complete in the language of set theory.
Point: There is a 2nd-order sentence ϕ0 in the languageL = {R} such that for any 2nd-order full L-structure
M = (A, P(A), R M ),M ⊨ ϕ0 ⇐⇒ for some λ with λ = |Vλ |, (A, R M ) ≃ (Vλ , ∈).Full semantics ctd.

Theorem (Folklore?)
There is a 2nd-order sentence ϕ1 in the language L of Peano
Arithmetic (PA) such that for any 2nd-order full L-structure
M = (A, P(A), . . .),M ⊨ ϕ1 ⇐⇒ (A, . . .) ≃ (N, +, ×, 1).
In particular, Compactness Theorem fails for 2nd-order logic
with full semantics.

In this talk...

We introduce Boolean valued semantics for 2nd-order logic andcompare it with full semantics w.r.t. the following 3 points:
1. Complexity of the validity
2. How much Compactness Theorem holds (or fails)
3. The construction of Gödel’s L w.r.t. the corresponding
definability

Boolean valued semantics; Introduction

Idea: Consider all the Boolean-valued subsets of the formf : A → B,
where A: the 1st-order universe, B: a complete Booleanalgebra

Boolean valued semantics; Introduction

Idea: Consider all the Boolean-valued subsets of the formf : A → B,
where A: the 1st-order universe, B: a complete Booleanalgebra
Note: When B = {0, 1}, it is the same as considering all thesubsets P(A), i.e., full semantics.

Boolean-valued semantics; Boolean-valuedstructures
From now on, L will be a relational language {R1 , . . . , Rm }.

Boolean-valued semantics; Boolean-valuedstructures
From now on, L will be a relational language {R1 , . . . , Rm }.

Definition

A Boolean-valued L-structure is a tuple M = (A, B, {RiM })where
1. A is a nonempty set,
2. B is a complete Boolean algebra, and3. for each n-ary relational symbol Ri in L, RiM : An → B.

Boolean-valued semantics; Boolean-valuedstructures
From now on, L will be a relational language {R1 , . . . , Rm }.

Definition

A Boolean-valued L-structure is a tuple M = (A, B, {RiM })where
1. A is a nonempty set,
2. B is a complete Boolean algebra, and3. for each n-ary relational symbol Ri in L, RiM : An → B.

ExampleIf B = {0, 1}, RiM is a relation in 1st-order logic and M is thesame as a 1st-order L-structure.

Boolean valued semantics; the interpretation
From now on,y or ⃗y : 1st-order variables, X : 2nd-order variables.

Boolean valued semantics; the interpretation
From now on,y or ⃗y : 1st-order variables, X : 2nd-order variables.

Definition

Let M = (A, B, {RiM }) be a Boolean-valued L-structure. Then
we assign ∥ϕ[⃗a, ⃗f ]∥M to each 2nd-order formula ϕ, ⃗a ∈ A<ω ,and ⃗f ∈ (BA )<ω as follows:Boolean valued semantics; the interpretation
From now on,y or ⃗y : 1st-order variables, X : 2nd-order variables.

Definition

Let M = (A, B, {RiM }) be a Boolean-valued L-structure. Then
we assign ∥ϕ[⃗a, ⃗f ]∥M to each 2nd-order formula ϕ, ⃗a ∈ A<ω ,and ⃗f ∈ (BA )<ω as follows:
1. ϕ is Ri (⃗y ). Then ∥Ri (⃗y )[⃗a]∥M = RiM (⃗a).
2. ϕ is X (y ). Then ∥X (y )[a, f ]∥M = f (a).
3. Boolean combinations are as usual.
∨4. ϕ is ∃y ψ. Then ∥∃y ψ[⃗a, ⃗f ]∥M = b∈A ∥ψ[b,⃗a, ⃗f ]∥M .
∨5. ϕ is ∃X ψ. Then ∥∃X ψ[⃗a, ⃗f ]∥M =∥ψ[⃗a, g , ⃗f ]∥M .
g : A→B

Boolean-valued semantics; the interpretation ctd.
Let B be a complete Boolean algebra. Then
(B-valued semantics) = (Full semantics in V B )Boolean-valued semantics; the interpretation ctd.
Let B be a complete Boolean algebra. Then
(B-valued semantics) = (Full semantics in V B )Definition

Let M = (A, B, {RiM }) be a Boolean valued L-structure andG be a B-generic filter over V . Then for each n-ary predicate
M/GRi , set Ri
as follows:
M/GRi= {⃗x ∈ An | RiM (⃗x ) ∈ G }.

Then let M/G be the full 2nd-order L-structure
M/G(A, P V [G ] (A), {Ri}) in V [G ].

Boolean-valued semantics; the interpretation ctd..

(B-valued semantics) = (Full semantics in V B )Key Lemma (Forcing Theorem)
If ϕ is a 2nd-order L-sentence and b ∈ B, then the following
are equivalent:
1. ∥ϕ∥M = b, and2. for any B-generic filter G over V with b ∈ G , M/G ⊨ ϕ.

Boolean-valued semantics; Validity
Definition

A 2nd-order L-sentence ϕ is Boolean-valid if ∥ϕ∥M = 1 for
any Boolean-valued L-structure M.

Boolean-valued semantics; Validity
Definition

A 2nd-order L-sentence ϕ is Boolean-valid if ∥ϕ∥M = 1 for
any Boolean-valued L-structure M.

Remarkϕ is Boolean-valid if and only if ϕ is valid w.r.t. full semantics
in any set generic extension.

Boolean-valued semantics; Validity
Definition

A 2nd-order L-sentence ϕ is Boolean-valid if ∥ϕ∥M = 1 for
any Boolean-valued L-structure M.

Remarkϕ is Boolean-valid if and only if ϕ is valid w.r.t. full semantics
in any set generic extension.

Definition
02f = {ϕ | ϕ is valid w.r.t. full semantics}
02b = {ϕ | ϕ is Boolean valid}.

Boolean-valued semantics; Validity
Definition

A 2nd-order L-sentence ϕ is Boolean-valid if ∥ϕ∥M = 1 for
any Boolean-valued L-structure M.

Remarkϕ is Boolean-valid if and only if ϕ is valid w.r.t. full semantics
in any set generic extension.

Definition
02f = {ϕ | ϕ is valid w.r.t. full semantics}
02b = {ϕ | ϕ is Boolean valid}.

Question
02f or 02b , which is more complicated?

BV semantics vs full semantics; Validity
Theorem (Väänänen, I.)
If V = L, then 02b ≡T 02f .
Point: Gödel’s L is absolute in any set generic extension of L.

BV semantics vs full semantics; Validity
Theorem (Väänänen, I.)
If V = L, then 02b ≡T 02f .
Point: Gödel’s L is absolute in any set generic extension of L.

Theorem (Väänänen, I.)
If you assume the existence of proper class many Woodin
cardinals and the Ω-Conjecture, then 02b is strictly simpler
than 02f .
Point: 02b ≡T 0Ω = {ψ | ψ is Ω-valid}.

Compactness numbers
Definition

Let L be a logic. Then the Compactness number κL of L isdefined as follows:κL = min{κ | for any set T of sentences in L, if every subset
of T of size less than κ has a model, then T has a model}

Compactness numbers
Definition

Let L be a logic. Then the Compactness number κL of L isdefined as follows:κL = min{κ | for any set T of sentences in L, if every subset
of T of size less than κ has a model, then T has a model}

ExampleIf L is 1st-order logic with the standard semantics, then
κL = ω.

BV semantics vs full semantics; Compactness
κ2f = κL for L = SOL w.r.t. full semantics
κ2b = κL for L = SOL w.r.t. Boolean-valued semantics

BV semantics vs full semantics; Compactness
κ2f = κL for L = SOL w.r.t. full semantics
κ2b = κL for L = SOL w.r.t. Boolean-valued semantics

Theorem (Magidor)
1. κ2f exists if and only if there is an extendible cardinal.
2. If κ2f exists, then κ2f is the least extendible cardinal.

Definition
A cardinal κ is extendible if for any α with κ < α, there are aβ and an elementary embedding j : (Vα , ∈) → (Vβ , ∈) withcritical point κ such that j(κ) > α.

BV semantics vs full semantics; Compactness ctd.
Theorem (Väänänen, I.)
1. κ2b exists if and only if there is a generically extendible
cardinal.
2. If κ2b exists, then κ2b is the least generically extendiblecardinal.

Definition
A cardinal κ is generically extendible if for any α with κ < α,there is a set generic extension V [G ] of V such that in V [G ],there are a β and an elementary embeddingj : (Vα , ∈)V → (Vβ , ∈)V [G ] with critical point κ such thatj(κ) > α.

BV semantics vs full semantics; Compactness ctd..
Question
How small could generically extendible cardinals be?

BV semantics vs full semantics; Compactness ctd..
Question
How small could generically extendible cardinals be?

Theorem (Väänänen, I.)
Suppose there are proper class many Woodin cardinals. Thenevery successor cardinal is generically extendible. In particular,
κ2b = ω1 .
Point: Use Stationary Tower Forcing P<δ .

BV semantics vs full semantics; Compactness ctd..
Question
How small could generically extendible cardinals be?

Theorem (Väänänen, I.)
Suppose there are proper class many Woodin cardinals. Thenevery successor cardinal is generically extendible. In particular,
κ2b = ω1 .
Point: Use Stationary Tower Forcing P<δ .

Open problem
What is the consistency strength of a generically extendible
cardinal?

Gödel’s Constructible Hierarchy
Definition
L0 = ∅,()
Lα+1 = DefFOL (Lα , ∈) ,∪Lγ =Lα (γ is limit),
α<γL=∪α∈OnLα .

Inner models from logics
Definition

Given a logic L extending FOL,
LL0 = ∅,()
LLα+1 = DefL (LLα , ∈) ,∪LLγ =LLα (γ is limit),
α<γL(L) =

∪α∈On

LLα .

BV semantics vs full semantics; Gödel’s L

Theorem (Myhill, Scott)
If L is SOL with full semantics, then L(L) = HOD.

BV semantics vs full semantics; Gödel’s L ctd.
Let L2b be L(L) for L = SOL with Boolean-valued semantics.

Theorem (I.)
Suppose there are proper class many Woodin cardinals. ThenL2b is the least inner model M of ZFC such that for any poset
P in M and any P-generic filter G over V ,(Hω1 , ∈)M[G ] ≺ (Hω1 , ∈)V [G ] .
In particular, Projective Determinacy (PD) holds in L2b .

BV semantics vs full semantics; Gödel’s L ctd.
Let L2b be L(L) for L = SOL with Boolean-valued semantics.

Theorem (I.)
Suppose there are proper class many Woodin cardinals. ThenL2b is the least inner model M of ZFC such that for any poset
P in M and any P-generic filter G over V ,(Hω1 , ∈)M[G ] ≺ (Hω1 , ∈)V [G ] .
In particular, Projective Determinacy (PD) holds in L2b .
Also, L2b is the least inner model of ZFC closed under theoperator (n, x) 7→ Mn# (x). Furthermore,
1. L2b is invariant under set forcings, and2. L2b is a premouse, hence is a model of GCH, ♢κ , and □κ
for all uncountable regular cardinals κ.

Conclusion• Henkin semantics and full semantics are the major

semantics for 2nd-order logic.
• Henkin semantics is essentially the same as 1st-orderlogic.
• Full semantics is much more powerful than 1st-order logic
and highly complicated.
• Boolean-valued semantics is a powerful semantics for
2nd-order logic while it could be simpler than fullsemantics under the existence of large cardinals.

The End.