Live data from Hacker News

List of Statements Independent of ZFC

en.wikipedia.org

41–50 of 108 posts

Re: List of Statements Independent of ZFC

#41
post #33

Earlier quoted context omitted.

Another example of why mathematics are a wrong abstraction to be optimally useful. Mathematics should have bounds in the same way as our universe has bounds. Any theorem that has a different behavior if something is infinite doesn't matter at all and is a waste of time for real engineers who solve things in the real world. The niche of mathematics that describe things beyond what our universe has to offer should be a…

Tell all of the engineers using calculus that they don't need infinity. And you can't easily only partially include infinity.

Computers handle calculus quite nicely using numerical algorithms, which don't involve any infinite sets.

> 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.

Re: List of Statements Independent of ZFC

#42
post #41
post #33

Earlier quoted context omitted.

Tell all of the engineers using calculus that they don't need infinity. And you can't easily only partially include infinity.

Computers handle calculus quite nicely using numerical algorithms, which don't involve any infinite sets. > 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.

Except for all that numerical analysis around floating point arithmetic...

Re: List of Statements Independent of ZFC

#43
post #30

Earlier quoted context omitted.

Another example of why mathematics are a wrong abstraction to be optimally useful. Mathematics should have bounds in the same way as our universe has bounds. Any theorem that has a different behavior if something is infinite doesn't matter at all and is a waste of time for real engineers who solve things in the real world. The niche of mathematics that describe things beyond what our universe has to offer should be a…

This is a fine and defensible (although not mainstream) viewpoint with several adherents among mathematicians and various levels of success in making it formal and precise. See e.g. https://en.wikipedia.org/wiki/Finitism Doron Zeilberger would like to pat you on the back.

How do finitists describe the decimal representation of the fraction 1/3?

Re: List of Statements Independent of ZFC

#44

Earlier quoted context omitted.

It is easy to prove for finite sets (just count) but much harder for infinite ones. For example, which has more subsets, the integers or the positive integers? How about the integers and the reals? 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/Al…

Another example of why mathematics are a wrong abstraction to be optimally useful. Mathematics should have bounds in the same way as our universe has bounds. Any theorem that has a different behavior if something is infinite doesn't matter at all and is a waste of time for real engineers who solve things in the real world. The niche of mathematics that describe things beyond what our universe has to offer should be a…

Since you feel so strongly about it, let me argue that you're simply wrong:

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.

Re: List of Statements Independent of ZFC

#45
post #3

A very interesting discussion about this topic that also includes many examples and references is available on MathOverflow: 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 i…

Cantor bad.

Please don't post unsubstantive comments here.

Re: List of Statements Independent of ZFC

#46

Is there any ELI5-type explanation for us non-mathers? Whenever I see stuff like this, I start trying to actually understand it, then fail miserably just trying to google terms I'm not familiar with. Is advanced knowledge of these math principles required to understand the significance of this page, or why it is interesting?

[The following isn't really "like you're five", but given how long it is already that's probably just as well.]

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.

Re: List of Statements Independent of ZFC

#47

Earlier quoted context omitted.

It is easy to prove for finite sets (just count) but much harder for infinite ones. For example, which has more subsets, the integers or the positive integers? How about the integers and the reals? 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/Al…

Another example of why mathematics are a wrong abstraction to be optimally useful. Mathematics should have bounds in the same way as our universe has bounds. Any theorem that has a different behavior if something is infinite doesn't matter at all and is a waste of time for real engineers who solve things in the real world. The niche of mathematics that describe things beyond what our universe has to offer should be a…

The most prolific contemporary proponent of this view is probably Norman Wildberger, who takes a very unconventional approach and tries to build everything without real numbers, which he doesn't believe make physical or logical sense and therefore shouldn't be used as a basis for anything.

He's very nearly a minority of one, mind you.

Re: List of Statements Independent of ZFC

#48

Earlier quoted context omitted.

Could you give a use case?

All of calculus.

It's possible to do quite a lot without infinities in calculus and trigonometry, whether it makes sense to bother is another question.

https://en.m.wikipedia.org/wiki/Rational_trigonometry

Re: List of Statements Independent of ZFC

#49

I recall once I read the short book "The Philosophy of Set Theory" [1] since I like philosophy and have an interest in Math. It contains much of the history that lead up to the decision to base significant portions of the soundness of mathematics on top of set theory (and by proxy: Cantor's work on infinities). My recollection is fuzzy since it was years ago but I recall it starts at Zeno's paradox and follows along…

I’m not sure that any side won. ZFC is merely a game with clearly defined rules that lots of people have agreed to play, but it is not the only game, by a long stretch.

Re: List of Statements Independent of ZFC

#50

Earlier quoted context omitted.

It is easy to prove for finite sets (just count) but much harder for infinite ones. For example, which has more subsets, the integers or the positive integers? How about the integers and the reals? 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/Al…

Another example of why mathematics are a wrong abstraction to be optimally useful. Mathematics should have bounds in the same way as our universe has bounds. Any theorem that has a different behavior if something is infinite doesn't matter at all and is a waste of time for real engineers who solve things in the real world. The niche of mathematics that describe things beyond what our universe has to offer should be a…

Yes, my current inclination would be to define truth (in a practical sense) as that which is computable. Everything else belongs to the realm of fiction or fantasy.

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.

Post reply on HN