We start by giving a rough idea of Cohen’s notion of a generic set (in the PA setting); Feferman’s and Addison’s sets are generic. A generic set is patternless or random1; it has no special properties. For example, the set of primes is not generic, nor is any set containing the set of primes—that’s a discernable pattern, even though it doesn’t determine the whole set. Likewise, if a set contains no primes then it’s not generic. The “least specific” thing we can say about G⊆ℕ, vis-a-vis primes, is that it contains an infinite number and omits an infinite number. So this should be true for any “generic” set. Perhaps you can already see how a generic set will be “slippery”, eluding various kinds of definability.
A generic G⊆ℕ can’t literally have no properties. For example, either 0∈G or 0∉G, and likewise for any other number n. A condition is a consistent conjunction of a finite number of statements, each either n∈G or n∉G for some n∈ℕ. (For example, 0∈G ∧ 17∈G ∧ 221∉G. This is the “formula” definition of condition. “Consistent” just means we don’t have both n∈G and n∉G in the same condition.) Suppose G satisfies a condition p. Cohen’s methods enable us to say exactly which statements about G should hold, given that G is “generic” and satisfies p. Cohen used the (initially vague) notion of “generic” to inspire the notion of “forcing”: if p forces φ, then φ holds for all generic G satisfying p.
The motivation runs from genericity to forcing, but the formal treatment takes the reverse route: first an inductive definition of forcing, then a definition of generic set in terms of forcing, and finally some lemmas justifying the initial intuition.
Now let’s nail down a few details. First, a matter of terminology. Shortly after Cohen’s forcing appeared, Feferman introduced a variation he called weak forcing. The one-way implication mentioned above becomes an equivalence for weak forcing: p weakly forces φ if and only if φ holds for all generic G satisfying p. For this reason, most authors nowadays just say “forcing” for “weak forcing”. Cohen’s version is, naturally, called “strong forcing”. The notation ⊩* is used for strong forcing, ⊩ for weak forcing. I will follow this convention. We’ll define (weak) forcing in a later post. (The strong/weak distinction is independent of the ZF/PA difference.) As it happens, the most natural treatment first defines strong forcing, proves theorems about it, and then defines weak forcing as a derived concept.
We let ℒ(PA+G) be the language of PA augmented with one new unary predicate G. We write (ℕ,A) for the structure consisting of the standard model (ℕ,0,1,+,·,<) of PA, plus A⊆ℕ interpreting G. We let p,q,r stand for conditions. For our present purposes, conditions as finite bitstrings works better than the “formula” notion. Some notations: p≤q and q≥p mean that q extends (or equals) p. A⊧p means that p is an initial segment of A (regarding A as an infinite bitstring). We let ∅ stand for the empty condition (i.e., the null string).
One difference between the bitstring and formula notions: if A⊧p1,p2, then with the bitstring notion, either p1≤p2 or p2≤p1. With the formula notion, we are assured only that p1 and p2 have a common extension q satisfied by A. We will avoid using this special fact about the bitstring notion, to keep certain arguments more general.
We’ll write p⊩*φ to mean that p strongly forces φ; here φ is a closed formula in ℒ(PA+G). The definition of p⊩*φ is inductive, as I mentioned. A key aspect of the definition: ∃ is regarded as basic, with ∀ just an abbreviation. Likewise, ∨ is basic with ∧ an abbreviation.
- p⊩* s=t ↔ ℕ⊧s=t, where s and t are closed terms in ℒ(PA).
- p⊩* G(n) ↔ p(n)=1.
- p⊩* α∨β ↔ p⊩*α or p⊩*β.
- p⊩* ¬φ ↔ there is no q≥p with q⊩*φ.
- p⊩* ∃xφ(x) ↔ for some n∈ℕ, p⊩*φ(n).
In (2) and (5), we are being a bit sloppy about the distinction between n∈ℕ and the numeral representing it in ℒ(PA).
Let’s talk about clause (4), the definition of p⊩*¬φ. Cohen originally put everything into prenex normal form. Dana Scott later suggested clause (4), simplifying the development. What is the intuitive justification for (4)? We want to have p⊩*φ precisely when (ℕ,A)⊧φ for all “generic” A⊧p. Obviously we don’t want to have p⊩*¬φ and q⊩*φ for some q≥p. On the other hand, if no extension q≥p strongly forces φ, this indicates we will always find generic sets satisfying an extension q and also satisfying ¬φ, no matter how q extends p.
Imagine going through the elements of ℕ in increasing order, choosing which to put into A. Suppose at some point that A⊧p. After that, we will never be able to assure the truth of φ; only when we’ve gone through “all of ℕ’’ will we find out if φ is true. That suggests that φ is somehow “specific”, that we have to choose “carefully” infinitely often if we want φ to end up true. For example, suppose φ says “G contains only finitely many primes”. This is more specific than its negation, since if n0 is the largest prime in A, then we have to vigilantly exclude every single prime greater than n0. So all generic A’s will contain infinitely many primes (and likewise omit infinitely many).
To put it another way: if A⊧p and p extends as far as the last prime in A, then this fact about p tells us an infinite number of facts about A. Namely, exactly which primes belong to it. But if A contains an infinite number of primes, then for any finite initial segment of A, we can say nothing about the primes past it. That seems more “generic” than the alternative.
Clause (4) captures this intuition. Suppose A contains infinitely many primes. If we claim of a condition that “It’s got all the primes of A!”, then our claim will be falsified by some extension. ∅⊩*¬φ says that there is no condition q with q⊩*φ. Because of clause (5), it’s a short step from q⊩* “A has only finitely many primes” to q⊩* “I’ve got all the primes of A!”. But we’ve just seen that that can’t happen.
The last few paragraphs make the heuristic case for clause (4). Ultimately these clauses justify themselves by the formal development based on them.
The following trivial consequence of clause (4) is important: we cannot have both p⊩*φ and p⊩*¬φ.
Now we are ready to define “generic” formally.
A⊆ℕ is generic iff for every closed formula φ in ℒ(PA+G), there is a condition p with A⊧p and either p⊩*φ or p⊩*¬φ.
Intuitive justification: either (ℕ,A)⊧φ or (ℕ,A)⊧¬φ. Either way, the truth of φ or its negation should depend on only a finite amount of information about A, namely a condition p (plus the fact that A is “generic”). So we should have either p⊩*φ or p⊩*¬φ.
This suggests a slight extension of the ⊩* notation. Write A⊩*φ to mean that there exists a p with A⊧p and p⊩*φ. With this notation, we have
A⊆ℕ is generic iff for every closed formula φ in ℒ(PA+G), either A⊩*φ or A⊩*¬φ.
[1] But we will avoid the word “random” from now on, since there is a different notion of algorithmically random.
Diagonal Argument 