Let’s look again at the notion of definability, rewritten slightly: for any set A, x⊆A is definable over A if there is a first-order formula φ(y,ū) and elements ā∈A such that
x={z∈A:φA(z,ā)}
where φA is φ relativized to A, i.e., all quantifiers in φ range only over A.
Very clearly the right-hand side depends on A. In some cases, we can write a formula for x that is independent of A. For example:
x={y} ↔ y∈x ∧ ∀z(z∈x→z=y)
Absoluteness is at the heart of Gödel’s proof that V=L holds in L. Failures of absoluteness present the main technical obstacles to showing that L satisfies ZF.
Three Non-absolute Notions
Let’s look at three non-absolute notions:
| x=𝒫(y) | |
| z is uncountable | |
| x=𝒫un(y)={z⊆y:z is uncountable} |
Now think about relativizing these three notions to L and to the Lα’s. Suppose x and y are both present in some Lα, and Lα⊧ x=𝒫(y). As we ascend to higher Lβ’s, the assertion “x=𝒫(y)’’ can become false1, because new subsets of y can appear in Lβ. The reverse switch from false to true can’t happen: once we have a “witness” z to x≠𝒫(y) (i.e., z⊆y but z∉x, or z⊈y but z∈x), it won’t go away. (Note that the meaning of x and y can’t change, because the Lα’s are all transitive: by the time x shows up, all its elements have shown up. Ditto for y.)
Here’s a slightly different way to look at it. Consider the sequence xα=𝒫Lα(y). The sequence xα is monotonically increasing (indeed, 𝒫Lα(y)=𝒫(y)∩Lα). So the assertion x=xα can flip from true to false as α increases2. It can’t flip from false to true, because that would mean that x had some elements (subsets of y) that xα was missing—but in that case x wouldn’t have been an element of Lα in the first place.
It’s a similar story for uncountability. We have:
Lα⊧ z is uncountable ↔ Lα⊧¬∃f(f:z↣ω)
where f:z↣ω is shorthand for saying that f is a injection from z into ω. If a witness f to the countability of z appears in some higher Lβ, then z “becomes countable”, and remains countable after that.
Next we look at x=𝒫un(y). Let xα=𝒫unLα(y). New uncountable subsets of y can appear at any time. But also, a subset of y that is uncountable in Lα can become countable later on. The upshot: 𝒫unLα(y) can both gain and lose elements as α increases, and the truth-value of “x=𝒫un(y)’’ can switch back and forth over and over again.
We will look at the limiting behavior (i.e., 𝒫L(y) and 𝒫unL(y)) later on.
Absolute Formulas
How about absolute formulas? We say that a formula φ(ū) is absolute if for all ā in K
| K⊧φ(ā) ↔ V⊧φ(ā) | |
| (K a transitive class, ā∈K) |
in other words, the truth-value of K⊧φ(ā) doesn’t depend on K, provided only that K is a transitive class. (To be precise, when we say K⊧φ(ā), we mean (K,∈)⊧φ(ā). Also, ā∈K means that all the ai belong to K. Note that without ā∈K, K⊧φ(ā) makes no sense.)
Δ0 formulas
A Δ0 formula is one where all quantifiers are bounded, i.e., of the form (∀x∈y) or (∃x∈y).
Here’s the intuition behind Δ0 formulas. In post 14, we defined the transitive closure of x to the elements of x, plus the elements of the elements of x, etc. Here we want the augmented transitive closure, where we add x as an element. Any transitive class containing x as an element contains its augmented transitive closure. In fact, it’s easy to see that the augmented transitive closure of x is the smallest transitive class containing x as an element, and that the augmented transitive closure is a set. OK: if φ(ā) is Δ0, then to find out if K satisfies φ(ā), we only need to root around in the augmented transitive closure of the ai’s. We never need to search through all of K. It looks like Δ0 formulas should always be absolute.
One proves this by a routine induction on complexity. If φ(x̄) and ψ(x̄) are absolute, it’s immediate that ¬φ(x̄), φ(x̄)∧ψ(x̄), and φ(x̄)∨ψ(x̄) are absolute. As for (∃ū∈v)φ(ū,x̄), one direction is easy. Suppose for ā,b∈K we have K⊧(∃ū∈b)φ(ū,ā). Then
| K⊧(∃ū∈b)φ(ū,ā) | |
| ⇒(∃c̄∈K) K⊧c̄∈b∧φ(c̄,ā) | |
| ⇒(∃c̄∈V) V⊧c̄∈b∧φ(c̄,ā) | |
| ⇒V⊧(∃ū∈b)φ(ū,ā) |
In the other direction, again with ā,b∈K (as demanded by the definition of absoluteness)
| V⊧(∃ū∈b)φ(ū,ā) | |
| ⇒(∃c̄∈V) V⊧c̄∈b∧φ(c̄,ā) | |
| ⇒(∃c̄∈K) K⊧c̄∈b∧φ(c̄,ā) | |
| ⇒K⊧(∃ū∈b)φ(ū,ā) |
We know that c̄∈K in the third line because c̄∈b∈K and K is transitive. The inductive assumption takes us from V⊧φ(c̄,ā) to K⊧φ(c̄,ā).
Some examples of Δ0 formulas:
Example 1: “x⊆y’’ is Δ0, since it can be written (∀z∈x)z∈y.
Example 2: “x is an ordinal” is Δ0. In post 17 we wrote out the clauses for this; for example, one was “(∀u,v∈x)(u<v∨v<u∨u=v)’’. (Recall that < is the same as ∈ for ordinals.) This is obviously Δ0. The transitivity of x was “(∀u,v)(u∈v∈x→u∈x)’’, which we can rewrite as “(∀v∈x)(∀u∈v)u∈x’’. Only the last clause isn’t Δ0, even rewritten this way:
(∀y⊆x)(y≠∅ → (∃u∈y) u∩y=∅)
The issue is “∀y⊆x’’. This does not count as a bounded quantifier. But Foundation makes this clause unnecessary.
Example 3: “f:x↣ y’’ is Δ0, i.e., f is an injection of x into y. Intuition: We just need to dig inside the guts of f and its domain and range to show that f is a function and is 1–1.
(∀〈u,z〉∈f) (∀〈v,z〉∈f) u=v
says that f is injective. The vernacular “∀〈u,z〉∈f’’ expands to “(∀p∈f)p=〈u,z〉’’, and this presents no snags.
Example 4: “w=ω’’ is Δ0, i.e., w is the first infinite ordinal. Here’s the formula for this:
w is an ordinal ∧ (∀y∈w)(y=∅ ∨ (∃x∈w)y=x+)
where x+=x∪{x}, the successor of x.
Example 5: f:y↣ω, i.e., f establishes that y is countable. This follows immediately from the last two examples.
In none of these examples do we ever need to climb outside the transitive closure of a given set and wander around the entire class K.
In contrast, we cannot check that K⊧x=𝒫(y) or that x is countable in K without surveying all of K, looking for (respectively) subsets of y and injections f.
Syntactic Analysis
With this in mind, we turn to a syntactic analysis of our non-absolute examples.
As noted, z⊆y and f:z↣ω are Δ0. So x=𝒫(y) is of the form
∀z δ1(x,y,z)
and “x is uncountable” is of the form
∀z δ2(x,z)
where δ1 and δ2 are Δ0.
Finally, x=𝒫un(y) is of the form ∀z∀f∃g δ3(x,y,z,f,g), where δ3 is Δ0. Showing this takes a bit of work. First we break down x=𝒫un(y) into three parts:
| ∀z(z∈x → z⊆y) | |
| ∧ ∀z(z∈x → ∀f ¬(f:z↣ω)) | |
| ∧ ∀z((z⊆y ∧ ∀g ¬(g:z↣ω)) → z∈x) |
We ask, how could this conjunction fail to be true? This way:
| ∃z(z∈x ∧ z⊈y) | |
| ∨ ∃z(z∈x ∧ ∃f f:z↣ω) | |
| ∨ ∃z(z⊆y ∧ ∀g ¬(g:z↣ω) ∧ z∉x) |
Now we use basic logical equivalences to move the quantifiers outwards. Say we have formulas φ, ψ(u), and ξ(u), where u does not appear in φ. Then
| φ∧∃uψ(u) | ↔∃u(φ∧ψ(u)) |
| φ∨∃uψ(u) | ↔∃u(φ∨ψ(u)) |
| φ∧∀uψ(u) | ↔∀u(φ∧ψ(u)) |
| φ∨∀uψ(u) | ↔∀u(φ∨ψ(u)) |
| ∃uψ(u) ∨ ∃uξ(u) | ↔∃u(ψ(u)∨ξ(u)) |
So we can rewrite the failure of x=𝒫un(y) as:
| ∃z ∃f ∀g [ | |
| (z∈x ∧ z⊈y) | |
| ∨ (z∈x ∧ f:z↣ω) | |
| ∨ (z⊆y ∧ ¬(g:z↣ω) ∧z∉x) ] |
The stuff inside the brackets is Δ0, so negating this gives us the form we claimed.
Thinking in terms of witnesses makes this more picturesque. Suppose x≠𝒫un(y). In other words, x is accused of the crime of not being 𝒫un(y). The prosecution and defence must provide witness lists before the trial starts. The prosecution lists z and f; the defence, all the g’s. Any one of the three disjuncts is sufficient to convict; let’s imagine a trial lasting three days. The witness z is called each day. On the first day, if z testifies to being an element of x but not a subset of y, game over. But suppose z surprises Jack McCoy (the prosecutor) by being a subset of y. On the second day, f is also called, to testify to the countability of z; McCoy hopes to show that z∈x. Too bad for McCoy, f’s testimony falls apart. On the third day, z is recalled and is shown to be both a subset of y, and not an element of x after all! The defence tries to argue that’s ok, because z is countable. He calls up every single g to testify to being the required injection, but each g fails. The jury convicts and McCoy repairs to the bar to have a drink with his ADA.
The Lévy Hierarchy
Summarizing the previous section:
| x=𝒫(y) | is of the form | ∀uδ1(x,y,u) | |
| x is uncountable | is of the form | ∀uδ2(x,u) | |
| x=𝒫un(y) | is of the form | ∀u∀v∃wδ3(x,y,u,v,w) |
where δ1, δ2, and δ3 are all Δ0 formulas. This syntactic analysis fits into a scheme known as the Lévy Hierarchy.
Formulas of the form ∀uδ(x̄,u) are called Π1 formulas; replace the ∀ with an ∃, and you’ve got a Σ1 formula. (Of course, δ here stands for a Δ0 formula.) More generally, any string of ∀’s is allowed at the front of a Π1 formula, likewise any string of ∃’s at the front of a Σ1 formula.
The negation of a Π1 formula is Σ1, and vice versa. Truth “propagates upwards” for Σ1 formulas and “propagates downwards” for Π1 formulas. The intuition is clear: if K⊧∃ūδ(ā,ū) for some ā⊆K with K a transitive class, then we have witnesses—elements c̄∈K such that K⊧δ(ā,c̄). The witnesses cannot be impeached by enlarging K, because δ is Δ0. So ∃ūδ(ā,ū) holds also in any transitive class containing K. Likewise for the downward propagation with Π1 formulas.
∀ū∃v̄δ(x̄,ū,v̄) is a Π2 formula; its negation is a Σ2 formula. A formula that looks like ∀ū∃v̄∀w̄…δ, where there are n alternating quantifier blocks, is a Πn formula; starting off with an existential block gives a Σn formula.
A formula equivalent to both a Σ1 and a Π1 formula will thus be absolute—but that word “equivalent” is the kicker. Equivalent in what sense? One answer: φ(x̄) is ΣnZF if there is a Σn formula ψ(x̄) such that ZF⊢∀x̄(φ(x̄)↔ψ(x̄)); likewise for ΠnZF. If a formula is both ΣnZF and ΠnZF, we say it’s ΔnZF. So Δ1ZF formulas are absolute between models of ZF. (And of course, Σ1ZF formulas are absolute upwards, Π1ZF absolute downwards, but only between models of ZF.)
This tradeoff between admitting more formulas or more classes can take a variety of forms. I won’t explore the full landscape, but a few aspects should be highlighted.
First let’s look at the role of bounded quantifiers. In Σ1 formulas they must appear on the inside the scope of the unbounded ∃x̄. (∀x∈y)∃z(z∈x) is not Σ1, for example.
If we restrict attention to ZF-models, then we can allow bounded quantifiers anywhere, and still get something equivalent to Σ1. Example: the formula (∀x∈y)∃zφ(x,y,z) is ZF-equivalent to ∃u(∀x∈y)(∃z∈u)φ(x,y,z), by an argument involving ranks3. So we can migrate all bounded quantifiers to the inside.
Formulas like (∀x∈y)∃zφ(x,y,z) are absolute upwards for all transitive classes, not just models of ZF. The idea is simple: in quantifying (∀z∈y)… with y∈K, the bounded quantifier never asks us to go outside K, for a transitive K. So if the assertion holds for K, it will hold for any transitive M⊇K.
For “function-like” formulas, we have another trick. We encountered this notion in posts 13 and 17: φ(x̄,y) is function-like if for any x̄ there is a unique y making φ(x̄,y) true. That is, ∀x̄∃y∀z(φ(x̄,z)↔z=y).
Any formula that is absolute upwards between transitive classes K⊆M, and is function-like over both K and M, is in fact absolute between K and M. Proof: Suppose ā∈K, and we have both K⊧φ(ā,b) and M⊧φ(ā,c), with b∈K and c∈M. Because φ(x̄,y) is absolute upwards from K to M, we also have M⊧φ(ā,b). But since φ(x̄,y) is function-like over M, that means b=c. So K⊧φ(ā,c).
This result has a counterpart in the Lévy hierarchy. Suppose we have a Σ1 formula
∃ūφ(x̄,y,ū)
where φ(x̄,y,ū) is Δ0. Suppose also that K is a transitive class, and ∃ūφ(x̄,y,ū) is function-like for K. That is, for any c̄∈K, there is a unique d such that K⊧(∃ū)φ(c̄,d,ū). Then our formula is equivalent to this Π1 formula over K:
∀ū∀z(φ(x̄,z,ū)→y=z)
I relegate the proof to the end of this post.
Now suppose that (∃ū)φ(x̄,y,ū) is function-like for both K and M with K⊆M. Then it is equivalent in both classes to a Π1 formula; we might say it is Δ1 for K and M, and hence absolute between them.
The Πn/Σn classification is not confined to set theory; in a more general context, quantifier-free formulas play the role of Δ0 formulas. Historically, proofs in logic often began by reducing formulas to prenex normal form (i.e., all quantifiers in front). This isn’t so widespread anymore. But induction on the “complexity” of formulas still pervades logic, and the Πn/Σn classification is our deepest analysis of this complexity.
Here is the argument about function-like Σ1 formulas. Suppose one of these formulas holds for (c̄,d). If the antecedent holds in the Π1 formula for some ū with x̄=c̄ and z=d′, then the Σ1 formula also holds for (c̄,d′). By the uniqueness hypothesis, d=d′ and the consequent holds for (c̄,d) in Π1 formula. That shows that the Σ1 formula implies the Π1 formula. For the other direction, suppose the Π1 formula holds for (c̄,d). By the existence part of function-likeness, there must be a ū and a d′ making the Σ1 formula true for (c̄,d′). The Π1 formula tells us that d=d′, so the Σ1 formula holds for (c̄,d). This argument can be extended by induction to show that function-like Σn formulas are Πn.}
[1] Just to be clear: by saying “x=𝒫(y) becomes false”, I mean that although Lα⊧x=𝒫(y), Lβ⊧x≠𝒫(y). Here x and y are fixed elements of L, which both belong to Lα (and thus also to Lβ).
[2] Again, to be clear, by “flip” I mean that x=xα but x≠xβ for two ordinals α<β.
[3] For each x in y, let αx be least ordinal such that there is a z of rank αx making φ(x,y,z) true. Let ξ=supx∈yαx, and set u=Vξ. Later on I will call this sort of reasoning a waiting argument.
Diagonal Argument 