# Are there any nontrivial examples of contradictions arising in non-foundational or applied math due to naive set theory?

I understand that naive set theory, whose axioms are extensionality and unrestricted comprehension, is inconsistent, due to paradoxes like Russell, Curry, Cantor, and Burali-Forti.

But these all seem to me like pathological, esoteric, ad-hoc examples, that really only matter in foundations, and most non-foundational and applied mathematics wouldn't go anywhere near touching them.

Am I wrong here? If we were to do non-foundational math over naive set theory and just ignore the paradoxes, what problems might we face? Yes, I know that we can technically prove $$0=1$$ because logic, but I'm looking for more interesting examples, particularly ones that could arise without having to specifically look for them.

Question: Notwithstanding technicalities like explosion, are there any "natural" examples of contradictions arising in non-foundational or applied math due to the paradoxes of naive set theory?

Has anyone ever arrived at a false statement in, say, algebra or number theory, using naive sets?

edit: I'd like to be clear that I'm playing devil's advocate. I'm of course aware that relying on an inconsistent theory is in general a bad idea, but of course not all flawed structures collapse immediately. How far could we go in practice before we ran into problems?

edit: By "non-foundational" I basically mean anything outside of set theory or mathematical logic. If the question of a theory's consistency comes up at all (this thought experiment notwithstanding), then it's probably "foundational". But it's of course fuzzy.

• I don't get what you are after. Russel's set $\{x\mid x\notin x\,\}$ is about the simplest "set" that can be built using the naive methods, so using naive set theory as a tool for sets defined by properties involving more than three symbols cannot be trusted at all. - And all of todays non-foundatioanal or applied math is not based on naive set theory (or can be translated to set theories that are not obviously inconsistent) – Hagen von Eitzen May 10 '15 at 19:35
• @HagenvonEitzen I'm aware that "technically" naive set theory "can't be trusted". I'm asking a hypothetical question: Suppose history had gone a bit differently, and we were still basing all math on unrestricted comprehension. What would be the first signs of trouble outside of set theory? – BenW May 10 '15 at 19:42
• I think this is a good question. I was just wondering a similar thing yesterday. A less controversial version of the question might ask "has naive set theory ever actually led anyone doing non-foundational mathematics into a contradiction?" rather than "is it okay to use naive set theory to do non-foundational mathematics" (to which most people would shout "no!") – Trevor Wilson May 10 '15 at 20:03
• On Trevor's advice, I've edited the title of the question to hopefully be less controversial and more reflective of what I'm really asking. – BenW May 10 '15 at 20:18
• Really, a set that contains itself or any construction that remains on self-containment is not natural at all! All those paradoxes come up if you let your intuition go und suddenly realize that the result is counter-intuitive. I call that a paradox of the human mind ... – image May 11 '15 at 10:20

With a strict enough definition of "non-foundational mathematics" I think the answer is probably "no" (although I would be very interested in seeing potential examples.) However, this shouldn't make mathematicians working on such mathematics feel safe about using unrestricted comprehension. The reason is that it's not always clear a priori what mathematics will turn out to be "foundational".

Indeed, people may start working on some mathematics that seems non-foundational but then turns in a foundational direction. For example, Cantor's development of set theory was a natural consequence of his study of sets of uniqueness in harmonic analysis.

If someone working in a supposedly non-foundational branch of mathematics ended up with a contradiction by using unrestricted comprehension, then with the benefit of hindsight we could say that he or she must have been working in an area related to foundations after all.

It might seem like cheating to make such a declaration after the fact, but perhaps it is not: It seems likely that, from a novel use of unrestricted comprehension to obtain a contradiction, one could obtain a novel use of replacement to obtain a theorem that could not have been obtained without replacement (i.e. using only restricted comprehension). I say this because replacement is a natural intermediate step between restricted and unrestricted comprehension.

Mathematics that uses replacement in an essential way is often considered ipso facto to be foundational. So I think it is likely that mathematics that uses unrestricted comprehension an an essential way (to the extent that it can be salvaged) would be considered foundational as well.

(This answer doesn't address the question of how long, on average, it would take people using unrestricted comprehension in non-foundational-seeming areas of mathematics to run into problems. I think that question is very interesting but probably also very hard to answer.)

• Good point - the term "foundational" is not very precise. I guess here I basically mean anything outside set theory and mathematical logic. – BenW May 11 '15 at 19:38
• @BenW Sure, but the terms "set theory" and "mathematical logic" are not entirely precise either. I think any definition of these fields as they are today should at least partly characterize them as the areas of mathematics arising from Russell's paradox and the closely related diagonal argument of Cantor, which would at least partly explain why they are the only areas (or at least the main areas) where "paradoxes" related to these ones seem to arise. – Trevor Wilson May 11 '15 at 20:14

The whole idea of using set theory as a foundational theory is that you want a theory that if you believe is consistent, the rest of mathematics is consistent.

Naive set theory is inconsistent. So you can't really continue, you cannot trust it to give you the rest of mathematics. And it is not important that you "don't seem to appeal to the paradoxes".

Axiomatic set theories, like $\sf ZFC$, come to make an effort to at least fight the problems that come up with naive set theory.

Why should you really care about the axioms of $\sf ZFC$? You shouldn't. You should care about the fact that $\sf ZFC$ is sufficient to develop basic model theory, and create the rest of mathematics inside its universe. And this makes set theory like the back-end architecture of your CPU. Do you really care that your computer is using an Alpha back-end or a SPARC back-end? No. You care that it is able to run Chicken Invaders, or YouTube, or $\LaTeX$.

Of course, if you are interested in mathematics, then you should learn at least a little bit how this processor works. Much like learning programming involves understanding the operating system, or the hardware design. So you should care because you want to know how your mathematics is being modeled, but in general you should care because naive set theory is provably bad for you.

• But is it really "provably bad for you" if you are doing, say, algebra? Can you point to an example of an algebraist who was unaware of Russell's paradox and accidentally "proved" an incorrect "theorem" in algebra as a result of this naivete? – Trevor Wilson May 10 '15 at 20:07
• Well, I can prove in naive set theory that $\Bbb Q$ has characteristics $2$. Is this bad enough for you? And once you start saying things like "Oh, but you can't use this and you can only use that" you essentially start to dole out axioms and get into axiomatic set theory. – Asaf Karagila May 10 '15 at 20:11
• @user2520938: It's just an application of the principle of explosion. Contradiction proves everything. :-) I know it's somewhat "cheating" but axiomatic set theory is exactly how we gave a list of rules which forbade that sort of cheating. – Asaf Karagila May 10 '15 at 20:13
• No, I don't think that's bad enough -- you were only able to do it because you knew about Russell's paradox and were using it on purpose. The OP was asking about what happens if we ignore the paradox. My point is that the claim "naive set theory is bad for you" (unlike the claim "naive set theory is inconsistent") is a statement about human mathematical practice, so it should be supported with evidence about human mathematical practice. – Trevor Wilson May 10 '15 at 20:15
• @Asaf I'm not sure that we actually disagree, but we can agree to disagree about whether or not we disagree, instead of (or in addition to) our original (dis)agreement. In any case, a mathematically natural example would be interesting. (I'm not sure it would have much to do with what rank of sets are "natural" to consider, though; I think it would have more to do with finding a more "natural" formula to apply unrestricted comprehension to.) – Trevor Wilson May 10 '15 at 20:27

I think:

The theorem is in algebra, and is about whether the $\lim^1$ functor vanishes on Mittag-Leffler sequences in abelian categories satisfying certain axioms. In order to correct the mistake, the author had to add a smallness condition.

I also think that the non-existence of a free complete Boolean algebra on a countably infinite set of generators could be considered, though perhaps complete Boolean algebras are more explicitly "foundational".

• Unfortunately I don't currently have access to those papers. – BenW May 11 '15 at 4:48

Well, I wouldn't trust a building whose structure was shown to be flawed. Note that it isn't a suspicion, it is a certainty.

But I know what you mean by your question... consider the following "proof" (taken from another question at MSE):

Theorem: Let $K$ be a field, then $K$ has an algebraic closure $\bar{K}$ (i.e an algebraic extension that is algebraically closed).

"Proof": Define $A=\{ F \supset K | F \text{ is an algebraic extension of } K\}$ and inherit this with the usual partial order of inclusion. One can check that Zorn's lemma applies (union of a nested chain of algebraic extensions is itself algebraic). Thus take $\overline{K}$ to be a maximal element. It must be algebraically closed for otherwise there is an irreducible polynomial with root in some strictly bigger field. $\blacksquare$

Do you trust this, as it is?

• I "trust" it in the sense that it is a true statement, and the proof does not immediately pop out as being flawed. Of course I'm playing devil's advocate here, but this does show that not all flawed structures collapse immediately. – BenW May 10 '15 at 19:53
• Do you have an example of how an algebraist using this type of flawed argument to prove algebraic results might accidentally fall into contradiction? – Trevor Wilson May 10 '15 at 19:56
• Hey the same "proof" shows that there exists a maximal ordinal! – Hagen von Eitzen May 10 '15 at 19:58
• @HagenvonEitzen I'm not saying that naive set theory is "valid", or "justified". Philosophically and mathematically, it's not. But even so, one might ask: what happens if we use it to do, say, algebra? Has anyone ever accidentally obtained an incorrect result in this way? – Trevor Wilson May 10 '15 at 20:18
• @A.P.: Zorn's lemma doesn't apply for proper classes. Essentially it works here since the "height" of this partial order is bounded, so we can extract a set which suffice for representing all the possible algebraic extensions up to isomorphism, and then apply Zorn's llama. – Asaf Karagila May 10 '15 at 22:11

There is a counterintuitive counterexample from the theory of inverse problems of a non-measurable conductivity on a disc that is not distinguishable from a homogeneous one w/boundary circle electrical measurements. It involves a function $f(r):[0,1]\rightarrow R^+$, such that $f(r^n)=f(r)$ for all natural numbers $n$. The construction of such a function involes a non-measurable set and the Axiom of choice. The inverse problems are relatively applied mathematics w/apllications e.g. to medical imaging.

• How easy would it be to run into a contradiction if one were to base this theory on naive sets? Presumably this would be possible if you played with it long enough. (Again, invoking the famous paradoxes directly doesn't count, i.e. you can't just say "Consider inverse problems of a non-measurable conductivity... Let $R = \{x | x \notin x\}$..." While that is a "valid" proof, it's rather trivial. I'm looking for more interesting examples.) – BenW May 19 '15 at 0:44
• Well, there is a principle of no loss of information in physics, e.g. information is not lost inside a black hole, it is spread on its horizon. But my counterexample w/non-measurable medium/function contradicts the principle. – DVD May 19 '15 at 1:31
• But does that prove that naive set theory is inconsistent? – Asaf Karagila May 19 '15 at 4:21
• Well, it may imply that the set theory w/Axiom of choice is inconsistent w/the laws of physics. – DVD May 19 '15 at 6:23
• But who cares about that? – Asaf Karagila May 19 '15 at 10:11