sniffnoy | "Get a logician! Quick!"

...OK, so nobody actually said that. "I think we broke math" may have been a better title, as IIRC Nic did actually say that. But anyway - so today Nic said that he and a second-year named ~~Cory~~ Korei had come up with something that appeared to demonstrate that ZFC was inconsistent. He presented this at mathclub social hour and no-one could find where the argument went wrong. And so the call went out... "I think we should find a logician."

And so various people were sent one at a time to find one, though none returned, and I suggested that a monster in the basement had eaten them. Finally they returned - they had found some logic grad students and had been working it out in the tea room; it had taken them quite a while, though! But the flaw was exposed and mathematics was not, in fact, broken.

OK. Here's the apparent paradox: Assume ZFC is consistent. We'll construct another theory B as follows: Take ZFC, and add in a new unary function symbol, L. Now ∀n∈ω, add in the axiom φ_n which states "L(n+1)∈L(n)" where here n,n+1 stand for the set-theoretic representations of such. Also, for good measure, let's expand the axiom schemas of separation and replacement by adding in versions for those predicates containing L.

So consider any finite subset of B; this contains only finitely many of the φ_i, let φ_n be the maximum one. Then we construct a model for it as follows: Take a model of ZFC and use that same notion of ∈, so we just need to define L. Well, for S∉{0,1,...,n,n+1}, define L(S)=∅, as they don't appear in any of the axioms involving L, so this is fine. Then we define L(n+1)=∅, L(n)={∅}, L(n-1)={{∅}}, etc, down to L(0). So this is a model for this finite subset of B. (Note that yes, this models the expanded separation/replacement schemas, because in this case L isn't doing anything ZFC can't do.)

But then by the compactness theorem, B is consistent, i.e. it is consistent with ZFC to have a function f:ω→Sets such that f(n+1)∈f(n) (which we can certainly construct using our expanded replacement axiom schema). Except it isn't, because this violates the axiom of foundation.

Now there's clearly something fishy here. For sone thing, that the contradiction comes from the axiom of foundation, which is, after all, totally irrelevant. But it is equiconsistent with the other axioms, so (if this were right) we couldn't just say "Well, I guess the axiom of foundation is problematic" and throw it out.

So, where's the flaw in the proof?

The problem is at the very end. Sure, you can construct such an f; but to get a violation of foundation, you need to prove that ∀n∈ω f(n+1)∈f(n). But we don't have that statement - rather, for each n, we have the separate statement f(n+1)∈f(n). How are you going to get from the latter to the former? You can't check infinitely many cases. Why don't the latter suffice in the first place? Well because you try to get a contradiction by taking S={f(n):n∈ω}, S≠∅ let T∈S be disjoint from S, saying ∃k∈ω st T=f(k), and then what? What you want is to say therefore f(k+1)∈T, contradiction, but you can't, because what you have is ∃k∈ω st T=f(k); you just know there's some such k, you can't go out of the system and say "Well, *one* of the φ_i proves it..." - which one? Again, you can't check infinitely many cases. You need one statement here to cover all cases to proceed logically, and you don't have that. Similarly you can't prove ∀n∈ω f(n+1)∈f(n) by induction, as you might think, because what's your inductive step? You don't have a single statement to cover it. To identify φ_n from n goes outside the system and isn't allowed. So it doesn't work. You have a collection of individual statements, not the global statement you need.

So, yay, math isn't broken.

-Harry