"Get a logician! Quick!"
Jan. 23rd, 2009 06:31 pm...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?
( Solution cut )
So, yay, math isn't broken.
-Harry
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?
( Solution cut )
So, yay, math isn't broken.
-Harry
