List of Statements Independent of ZFC
en.wikipedia.org
en.wikipedia.org
What are some reasonable-sounding statements that are independent of ZFC?
https://mathoverflow.net/questions/1924/what-are-some-reason...
With the top voted result currently being:
"If a set X is smaller in cardinality than another set Y, then X has fewer subsets than Y."
As is also mentioned in the linked entry, this statement is independent of ZFC.
This is the only sensible way to interpret claims of independency, since if ZFC is inconsistent it just proves every statement so there's no independent ones
For this particular list, the statements have been proven to both be consistent with ZFC and for their negations to be consistent with ZFC.
Therefore, |P(R)| > |R| = |P(N)| > |N|, so the power set of the reals has more elements than the power set of integers.
The continuous hypothesis is the belief that no cardinal exists between |N| and |P(N)|. My previous argument fails if we pick two sets A and B, such that |A| < |B| < |P(A)|.
If you answered "the integers" to the first question, you aren't thinking about this right, as the integers and the positive integers have the same number of elements to start with. source: https://en.wikipedia.org/wiki/Aleph_number
See e.g. https://en.wikipedia.org/wiki/Finitism
Doron Zeilberger would like to pat you on the back.
Infinities have the opposite effect then you might think, they make things simpler. It's much easier to reason about an infinite list of numbers then to reason about 64 bit numbers.
In analysis, it's much easier to reason about infinitely differentiable, or smooth, surfaces then very rigid and complicated services.
The fact that infinities cause some complications in the foundations itself is a drop in the bucket to the practical application and simplifications of day to day mathematics.
I would argue that a few extra lines in a proof is a small price to pay to avoid the Godelian catastrophe.
A realist might say that mathematics exists within this universe, therefore it is equally subject to its constraints just like anything else. Problems arise via misapplication or misinterpretation of the math.
A model theorist might point out that even in models of math with only a countable collection of objects, it's still true that the reals are uncountable. The problem isn't with infinitie, it's that the finitary objects have subtle interactions.
A logician might object that ZFC already does start of with an intuitive notion of infinity, i.e. the counting numbers is a natural collection. The problem is that this inevitably has unintended consequences.
A historian might gently point out that this debate already occurred vigorously about 150 years ago, and the verdict was that we just gotta live with the weirdness of infinities. The problem is that we lose too much useful math by trying to throw them out.
Etc.
Note that I don't mean to imply that this is the entirety of my philosophy. Just that one should distinguish between what is practically relevant and what is not and I think the current state of mathematics and CS does a poor job of making this distinction.
He's very nearly a minority of one, mind you.
And you can't easily only partially include infinity.
> And you can't easily only partially include infinity.
Sure you can. You just need to use a dx that's small enough for the particular functions you're working with and the degree of precision you need.
One argument in favor of this belief is that neither practical computations nor analytic intuition require actual infinitesimals.
The later, at least, has been my experience. I think I have a fairly decent practical intuition for calculus based on imagining dx becoming smaller and smaller until it's small enough, but I don't think my brain has any actual representation of "true infinitesimals" and my intuition breaks down completely if I try to imagine things like the relationship between the rational and irrational numbers. Maybe that's due to my intellectual limitations, but I wonder if it isn't because these concepts might be over-elaborate abstractions that don't really exist in our world.
Don't derivatives count? That's a pretty important and trivial calculation. Sure, you can approximate it when it's nicely behaved, but they aren't always. There's also lots of verrrrrrry slowly converging series that can't be easily computed numerically.
And, again, coming up with derived theorems that are useful.
This is like Stacey King saying "I'll always remember this as the night that Michael Jordan and I combined for 70 points."
Pretty much the entire field of Analysis (of which calculus is a part) relies on 'infinities' of some kind. Even if you try to restrict to the rationals, you're still typically working with infinite series of them.
You can do some analysis over the rationals, but often this takes the form of Cauchy sequences of rationals which might be cheating.
[0] https://math.stackexchange.com/questions/387234/how-far-can-...
For infinite sets of arbitrarily large cardinality?
But then we have this (from [3]):
> For each of the following statements, there is some model of ZF¬C where it is true:
> - In some model, there is a set that can be partitioned into strictly more equivalence classes than the original set has elements, and a function whose domain is strictly smaller than its range. In fact, this is the case in all known models.
So it's really, pick your own poison - either one of these:
- you can take apart a ball and put the pieces back together into two balls
- there exists a function whose range is larger than its domain
Math is weird.
[1] https://en.wikipedia.org/wiki/Axiom_of_determinacy
[2] https://en.wikipedia.org/wiki/Solovay_model
[3] https://en.wikipedia.org/wiki/Axiom_of_choice#Statements_con...
> In 1973, Saharon Shelah showed that the Whitehead problem ("is every abelian group A with Ext^1(A, Z) = 0 a free abelian group?") is independent of ZFC.
(This is the same Shelah who proved what is usually called "Sauer's Lemma" on set separability, upon which the "VC dimension" and the resulting VC learning theory are based.)
Anyway, this was surprising because I didn't know there were any theorems outside of set theory that had been known and studied, and then later turned out to be independent of ZFC.
Apparently, the surprise I felt is just because I wasn't paying attention -- there are a couple of other problems in the page that seem to have a similar flavor. I'm not enough of a mathematician to appreciate to what extent they are interesting problems that arise independently of counterexamples.
[edited to add: the comment of @triska nearby addresses exactly this point!]
Topology and set theoretic topology is full of those statements, are there Suslin lines? Are there S-spaces? Is the product of two ccc spaces also ccc? The list goes on
Another one from analysis is a very strong form of Fubini's theorem that was shown independent by Friedman.
There's surely more but those are the ones I could remember right now!
Proofs and formal systems, and why we're kinda screwed
Mathematicians like to prove things. What we would really like would be to be able to find, for every mathematical statement, either a proof that it's true or a proof that it's false.
It wasn't until the early 20th century that mathematicians got a clear enough idea of what proof is to figure out whether that could be done. And it turns out it can't! That was proved in 1931 by Kurt Goedel, who did something that these days is very familiar to anyone in computing but was novel then: he found a way to encode mathematical statements, and sequences of mathematical statements, as numbers, in such a way that properties of those statements turn into properties of the numbers, so that you can use ordinary mathematics to reason about them.
This enabled him to show that if you have any system for doing mathematics that (1) is powerful enough to describe ordinary arithmetical statements and (2) is simple enough that you can check mechanically what is and isn't a proof, then there are statements that that system can neither prove nor disprove. (With a proviso I'll come to in a couple of paragraphs.)
So much for the hopes of mathematicians.
Anyway, despite that setback, mathematicians didn't abandon the idea of building up all of mathematics in some nice simple formalized system in which we can prove and disprove things. We still like to do that, and have come to terms with the fact that there will be things we can neither prove nor disprove.
... Unless the system we're working in happens to be inconsistent, meaning that there's some proposition that it can both prove and disprove. In that case, what actually happens is that it can prove everything, which is of course completely useless. So far as we know, the systems we like to use aren't inconsistent. It would be nice to prove they aren't -- but there's a nice variant of Goedel's theorem that says not just "for any system that isn't inconsistent, there are propositions it can't decide" but "for any system that isn't inconsistent, a formalized statement of its own consistency is a proposition it can't decide".
Once, again, so much for the hopes of mathematicians.
The particular formal system called ZFC
One particular nice simple formalized system is called ZFC, which is short for "Zermelo-Fraenkel set theory with the Axiom of Choice". That's a bit of a mouthful. So, "set theory" means that the basic idea we're starting with is that of a set of things. (In order to do mathematics, we certainly need some idea like that. It turns out that taking it as the foundational idea works fairly well.) Zermelo was a mathematician who came up with one fairly good way to do that. Fraenkel was another mathematician who improved Zermelo's system.
The "Axiom of Choice" -- the C in ZFC -- is a rather technical statement in set theory that turns out to be (1) "obviously true" according to some mathematicians' intuition, (2) useful for proving things we care about, and (3) something that plain old ZF, without the C, can neither prove nor disprove. (Unless, as usual, ZF is actually inconsistent.) In particular, this means that if ZF is a consistent system -- if it isn't able to prove 1+1=3 -- then ZFC is as well. (Because if you could get a contradiction out of ZFC, you could use it to prove not-C within ZF.) So adding the Axiom of Choice to ZF is "safe"; it can't create contradictions that weren't already there. And, since it's useful, we tend to keep it around.
[You can skip the next two paragraphs if you like. They describe the sort of thing you do if you want to build up all of mathematics on top of set theory.]
So, how do you build mathematics out of set theory? The usual sort of game you play is this. We want to be able to talk about numbers. So first of all we find an implementation of numbers in terms of sets. (If you were doing mathematics in a computer you'd want to do roughly the reverse, and build your sets out of numbers.) So we might, e.g., say that 0 "is" the empty set, and then 1 "is" the set containing just 0, and then 2 "is" the set containing just 0 and 1, and so forth. That gets you a load of sets that can (as well as being sets) do double duty as the non-negative integers. Then you construct the integers (negative as well as positive) out of those, and then the rational numbers (ratios of integers) out of those, and then you need some fancier footwork to get the "real numbers" (including things like pi and the square root of 2).
And then you're off to the races, because once you have the real numbers you can do geometry: e.g., three-dimensional space "is" the set of triples (x,y,z) of real numbers, and things like spheres and dodecahedra are just sets of points in space. And now you have numbers and geometrical things, and you can build all the other weirder more abstract things mathematicians like to study in a similar way.
OK, so if we have sets then we have everything, so a formalized set theory is a reasonable thing to try to use as a basis for mathematics. But, ever since Goedel, we know that any formalized system will be unable to decide (i.e., either prove or disprove) some statements we might be interested in.
What that page is about
The Wikipedia page linked here is a list of statements we might be interested in that ZFC is, as it turns out, unable to decide. "Independent of" means "neither provable nor disprovable from".
(There are other systems you can use instead of ZFC. Some of them are other varieties of set theory; some work entirely differently. It usually turns out that you can translate most statements of ordinary mathematics to and fro between them, and that what's provable and what isn't doesn't depend on "implementation details" (e.g., I described one particular way to build non-negative integers out of sets; what if we do it a different way? The answer is usually that it doesn't matter). But some systems are "stronger" than others and can prove or refute more statements. To be usable for mathematics, a system can't be "too much" weaker than ZFC. And since in some sense ZFC encodes most of the things that mathematicians are pretty sure "ought" to be true, most systems people want to use aren't "too much" stronger than ZFC either. A lot of the statements on that page would also be on similar pages about systems other than ZFC.)
A lot of those statements are weird technical things that only a mathematician could care about, and indeed that only a mathematician specifically interested in what's provable from ZFC and what isn't could care about. Some of them are at least potentially interesting to some mathematicians for their own sake, but understanding them generally requires a pile of background that (1) I don't really have myself in most cases and (2) you really don't want me to make this long enough to deal with.
But here's one of them, one of the oldest of them all. Some sets are bigger than others. For instance, {1,2,3} is bigger than {1,2}. What about infinite sets? It's not obvious a priori what "bigger" should even mean for infinite sets, but Georg Cantor (a pioneer of this stuff) found a good answer, whose details we don't need right now. It turns out that the integers are "the same size" as the rational numbers, even though the integers seem like a tiny subset of the rational numbers, but that the real numbers are "bigger". So here's the question: are there any sets bigger than the rational numbers but smaller than the real numbers? This is called the "continuum hypothesis", which is a bit of a stupid name but never mind, and it is neither provable nor disprovable in ZFC.
Has anyone named a set in between the rationals and the reals?
You can kinda think of it as "the set of real numbers MOD the set of rationals". Kinda. And they're dorked up because the length is infinitesimal, but a countably infinite number of them add up to length 1.
For a more precise explanation see here: https://math.stackexchange.com/a/137959/287133
https://en.m.wikipedia.org/wiki/Continuum_hypothesis
There are many sets which are strict supersets of the rationals and strictly sheets of the reals, of course.
For example, if ℚ is the rationals and ℝ is the reals then ℚ∪{√2} is a strict superset of the rationals but a strict subset of the reals. However, it still has the same cardinality as the rationals (cf. https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Gra...)
Assume that CH fails and well order the reals. An initial segment of length omega_1 is an example of such a set.
The book suggests there was a lot of displeasure and argumentation within the philosophy and math communities because it was felt that there was no real basis for infinitesimals. Some mathematicians (I believe Hilbert and Frege among them?) became determined to shut-up the pesky philosophers by proving the soundness of math based on some logical axiomatic fundamentals. Of course, this was later proven to be impossible by Gödel but at the time they considered it a win that philosophers and mathematicians could at least agree on logic (and more broadly "logical empiricism" which is a basis of "analytical philosophy").
I recall being completely dissatisfied at the arguments presented in favour of ZFC (not mathematically, but philosophically). I remember there was a single paragraph somewhere in the final third of the book that I head to re-read several times before I finally gave up in frustration. My impression of this history is that the mathematicians "won" in some sense by railroading their ideas. Calculus works, right? It is extremely effective and leads to correct results ... so ignore the seeming paradox of summing an infinite quantity of infinitesimally small values and move on already! Further, ignore the actual paradoxes inherent in infinite sets. And this was all done not because there was some problem to be solved but rather to shut-down debate that seemed to undermine the philosophical position of logical empiricism.
Another interesting (if historically questionable) exploration of this topic is the graphic novel Logicomix [2]. This work follows Bertrand Russel and Wittgenstein through this period in our history.
1. https://www.amazon.com/Philosophy-Set-Theory-Introduction-Ma...
Nowadays, the idea that math has a role to play in pretty much every science isn't really questioned at all. I mean, imagine I suggested that something other than math should be brought to bear on physics. I doubt a single person in here would support such an approach on any level. I think that represents a clear win. Answering objections about the fundamentals of math using formalisms like ZFC was a component of that.
ZFC wasn’t even the end of the debate on mathematical foundations even in math. There are a lot of people trying to redo everything with types and category theory today.
Almost no scientists cared about formalizing or proving the soundness of the mathematical tools they used. In the same way the majority of programmers do not care about proving the soundness of their programming languages. In general, people seem to be interested in the practical aspects of their work.
But the general idea that symbolic logic is the primary basis for understanding the world is something a bit different and something we rarely question now. I think people assume that this is some obvious thing but it is actually an idea that was coordinated and forwarded. It appears to me that the debate at the beginning of the 20th century around using set theory to establish the foundations of math by way of logic is when the scale seems to have heavily tipped towards that particular idea.
I think hacker news can be a bubble since these deeper issues can sometimes appear here. I recall a recent post about a soundness bug found in Rust and it generated quite a lot of discussion. However, I see that as analogous to the intense scrutiny of a small cabal of scientists/philosophers, the Vienna Circle for example, who did take these fundamentals seriously in math/sciences. I just do not believe and have not experienced that sentiment to be prevalent outside of this bubble.
For example, I highly recommend the paper Rethinking set theory by Tom Leinster:
https://arxiv.org/abs/1212.6543
It highlights Lawvere set theory. The paper won this year's Chauvenet Prize:
https://www.maa.org/programs-and-communities/member-communit...
ZFC, its subtheories, and its extensions, serve as a universal yardstick for consistency results. It's not really clear why that is the case, but it has so far proven to be so.
So you were to specify such a thing and the thing was small enough it's value could be determined by a command line program and you found integers m1.... m9 such that when you typed them at the command line, the value returned was 0, would "reality" have determined a "truth" that was not deducible?
Still, I can't see each of the steps wouldn't be easily determined by existing axioms.
Anyway, my head hurts.
But this seems to go against the idea that for any proposition independent from an axiom system, there is a model of the axiom system where that proposition is true and another where it is false.
Someone enlighten me (not sarcastic).
If this were formalizable it would be a proof.
I encourage you to read through the excellent piece on the busy beaver function and computability. It's not entirely related, but it's fun! And it touches on the same theme as your question here, that human intuition about mathematics is weak. The writeup describes and proves the non-computability of a particular function of positive integers with definite (but non-computable!) value.
A proof, but not a proof that can be expressed inside ZFC.
However, it seems intuitively you construct the notion of finite, could engage in the ordinary computation and have a way of distinguishing these "weird roots" from regular roots.
I suppose if you make the position of (something like) "every polynomial whose root cannot be found by finite calculation does not, in fact, have one" an axiom but then you would have discarded the notion of finite axioms (you'd have a second order system).
Still, might actually have a way to specify "truth", something I'd thought was a bit beyond logic at this point.
Assuming is ZFC is consistent, the theory says there are polynomials whose zeros we could forever fruitless search for but which couldn't be proved to have no zeros in ZFC. We could forever fruitlessly search for a proof of the polynomail having no zero, in fact (putting it this way, returns the situation to something marginally understandable, in fact makes something that would follow from the halting problem).
If ZFC is inconsistent, we actually could prove that this polynomial had a zero and we could prove it didn't have a zero, since we could prove anything, at least anything in the vocabulary of ZFC.
I think it must use some tools I'm unfamiliar with.
The two main techniques to produce new models of ZFC are inner models, that is submodels of a model, for example studying the inner model L (Gödel's constructible universe) is how the consistency of the continuum hypothesis, the generalized continuum hypothesis, the existence of Suslin trees etc. was shown. Looking at L also allows one to conclude that the axiom of choice is consistent with ZF. Another commonly study inner model is the so called HOD, and there's a whole area, "inner model theory" that essentially tries to construct canonical inner models for some statements.
The second big way to produce a model of ZFC is by forcing. This is a very versatile tool that allows to extend a given model of ZFC by adding a new set to it (for example by adding a lot of new reals numbers to a model of CH you can make CH false). Forcing is how the consistency of the negation of CH and GCH was proved.
An interisting example is the negation of AC and its consistency with ZF. If you happen to live in a model of AC every forcing extension will still be a model of AC so it seems that our previous techniques are powerless. But actually what can be done is to look at a carefully chosen submodel of a forcing extension that still models ZF but in which AC fails.
1.Set-theoretic technique : forcing, e.g. Cohen forcing which was used in the proof of the independence of the continuum hypothesis.A good reference is Shelah's book on forcing.
2. Model-theoretic: construct a model for ZFC in which the negation of the statement is true and another model for which the statement is true.
There may be proof-theoretic techniques based on the non-existence of proofs involving finitely many steps, but I am not aware of these.
- TFA
And, besides, from any (consistent) axiom system for which a given statement is undecidable, there is another axiom system which is the same except it adds that statement as an additional axiom, and the statement is therefore (trivially) provable in that system.
And, it doesn’t seem like physics is constrained to use only some specific axiom system.
It seems to me that the relevant thing to physics would be, rather than an axiom system, instead, a model (in the math sense, not the physics sense).
But doesn't that lead to systems with infinite numbers of axioms?
but any statement we could make about stuff in physics, if it could be expressed in the language of the formal system, would, as a single statement, be something that could be added as a single axiom.