10 ms·

List of Statements Independent of ZFC

104 points by killlameme99 7y ago

Rerarom 7y ago
Hopefully this will clear at least some of the Gödelian misconceptions that pop up from time to time here
- JadeNB 7y ago
  How? Misunderstandings about Gödel's theorem are unlikely to be due to a misunderstanding of the axioms of set theory (more likely of logical issues such as the technical meaning of 'incompleteness'), let alone to a lack of understanding of what statements are independent of a common set of axioms.
- utopian3 7y ago
  Which Gödel misconceptions?
triska 7y ago
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-reasonable-sounding-statements-that-are-independent-of-zfc/6594 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.
- sansnomme 7y ago
  Cantor bad.
  - egdod 7y ago
    What does this have to do with Cantor?
    - saagarjha 7y ago
      Cantor did work on cardinalities, presumably.
      - sansnomme 7y ago
        He practically invented the field.
        saagarjha 7y ago
        There's an implicit "because" at the front there, I know about Cantor's influence quite well ;)
    - GraemeL 7y ago
      ZFC was created to avoid the paradoxes inherent in Cantor's set theory work.
      - JadeNB 7y ago
        I think it's fairer to say that ZFC was a response to paradoxes in naïve set theory of the sort discovered by Russell than in response to Cantor; see, e.g., > In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. (https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory). Cantor discovered a rigorous basis for the intuitively paradoxical situation of two sets where it seems that one is manifestly bigger, but they are actually the same size; but I think that this work is best viewed as a resolution of the paradox, not a paradox itself.
  - dang 7y ago
    Please don't post unsubstantive comments here.
- egdod 7y ago
  That is a strange one.
  - yarg 7y ago
    Infinities are strange.
  - pvarangot 7y ago
    Try thinking about how you could probe that the integers have fewer subsets than the reals using ZFC.
    - Enginerrrd 7y ago
      That still feels intuitive. Like for any open interval there are uncountably many reals and a finite number of integers. It seems like nothing changes as you expand the interval.
      - rodamaral 7y ago
        The integers HAVE fewer subsets than the reals! Cantor's theorem tells us that the power set of any set has more elements than said set. It's also well known that the reals have the same cardinality as the power set of the integers. 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)|.
    - deleted 7y ago
      [deleted]
- The_rationalist 7y ago
  WTF I'm pretty sure I can prove that
  - ur-whale 7y ago
    >I'm pretty sure I can prove that For infinite sets of arbitrarily large cardinality?
    - The_rationalist 7y ago
      No I can't. But see my answer to correct_horse
  - correct_horse 7y ago
    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/Aleph_number https://en.wikipedia.org/wiki/Aleph_number
    - The_rationalist 7y ago
      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 an optional extension to the mathematical framework instead of being the default, in order to not pollute discussions.
      - new2628 7y ago
        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 https://en.wikipedia.org/wiki/Finitism Doron Zeilberger would like to pat you on the back.
- ur-whale 7y ago
  So, does that mean that one can assume this to be true and build a perfectly consistent theory, or conversely assume it to be false (with - say - at least one counter-example) and build another perfectly consistent theory?
  - deleted 7y ago
    [deleted]
  - karatinversion 7y ago
    Yes, this is the exact meaning of “independent from” here.
  - deepsun 7y ago
    Well, it's not possible to prove the consistency, thanks to Godel. Maybe one of your new theories would contain a statement, inconsistent with the rest of ZFC.
    - CrazyStat 7y ago
      This is incorrect. It absolutely is possible to prove consistency, what Gödel tells us is that in any consistent logic system there are true but unprovable (in that system) statements. For this particular list, the statements have been proven to both be consistent with ZFC and for their negations to be consistent with ZFC.
      - ithinkso 7y ago
        This is first incompleteness theorem. What deepsun was referring to is second incompleteness theorem - in a consistent system F the statement 'F is consistent' is in fact unprovable (in F).
    - ginnungagap 7y ago
      When we say that a statement P is independent of ZFC what we're really saying is "if ZFC is consistent, then P is independent of ZFC (hence both ZFC+P and ZFC+not P are consistent)". 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
- ginnungagap 7y ago
  It gets worse than that, by Easton's theorem, except for two mild restrictions provable on ZFC, the function that sends a regular cardinal to the cardinality of its powerset can be anything
mturmon 7y ago
Some of this was familiar, but I also saw this: > 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!]
- ginnungagap 7y ago
  Another famous example of that kind is the existence of outer automorphisms of the Calkin algebra, which is a simple question about a naturally occuring object which turned out to be independent of ZFC by work of Farah and Weaver. 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!
daxfohl 7y ago
Why is it always zfc plus optionally something else? Is there anything other than zfc that creates an interesting starting point?
- triska 7y ago
  These are excellent questions! And yes, there is! For example, I highly recommend the paper Rethinking set theory by Tom Leinster: https://arxiv.org/abs/1212.6543 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-communities/maa-awards/writing-awards/chauvenet-prizes https://www.maa.org/programs-and-communities/member-communit...
  - QuesnayJr 7y ago
    Isn't Lawvere set theory equiconsistent with bounded Zermelo set theory? 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.
- andrepd 7y ago
  https://en.m.wikipedia.org/wiki/New_Foundations https://en.m.wikipedia.org/wiki/New_Foundations
- empath75 7y ago
  https://en.m.wikipedia.org/wiki/Univalent_foundations https://en.m.wikipedia.org/wiki/Univalent_foundations
maest 7y ago
What's a reasonable strategy of proving a statement like that is undecidable in ZFC? I think it must use some tools I'm unfamiliar with.
- The_rationalist 7y ago
  I believe it is what is called metalogical proofs
- deleted 7y ago
  [deleted]
- aetilley 7y ago
  To show that a sentence P is independent of a theory (that is, a set of sentences) T, generally one constructs or demonstrates the existence of a model of T + P and also produces a model of T + (not P). https://en.wikipedia.org/wiki/Model_theory https://en.wikipedia.org/wiki/Model_theory
- danharaj 7y ago
  Start with Forcing https://ncatlab.org/nlab/show/forcing https://ncatlab.org/nlab/show/forcing https://en.wikipedia.org/wiki/Forcing_(mathematics) https://en.wikipedia.org/wiki/Forcing_(mathematics)
- sn41 7y ago
  There are 2 popular ways. 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.
- lmm 7y ago
  Show that it implies the consistency of ZFC, and that its negation also does so. Or show that it's equivalent to a statement that's already on that list.
- 7y ago
etaioinshrdlu 7y ago
I love seeing pure math on HN. I think math is the purest expression of what it means to be curious. It sometimes gives us fun toys to build into whatever we are coding.
ArchReaper 7y ago
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?
- gjm11 7y ago
  [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.
reggieband 7y ago
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 to calculus and beyond. 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-Mathematics/dp/0486435202 https://www.amazon.com/Philosophy-Set-Theory-Introduction-Ma... 2. https://en.wikipedia.org/wiki/Logicomix https://en.wikipedia.org/wiki/Logicomix
- empath75 7y ago
  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.
est31 7y ago
In other news, there's recently been a mechanized proof for one of the ZFC independent problems: https://flypitch.github.io/papers/ https://flypitch.github.io/papers/ https://news.ycombinator.com/item?id=21823618 https://news.ycombinator.com/item?id=21823618
mirimir 7y ago
Might something like this be fscking unification in physics?
- drdeca 7y ago
  I doubt it. Physics doesn’t seem to have much which is clearly connected to proof systems. 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).
  - mirimir 7y ago
    Thanks. But doesn't that lead to systems with infinite numbers of axioms?
    - drdeca 7y ago
      If you want to add axioms in order to be able to show each of an infinite number of statements which are all independent of the initial axiom system, and also none of them follow from the rest of them, that could involve an infinite set of axioms, yes, 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.
joe_the_user 7y ago
One can write down a concrete polynomial p ∈ Z[x1,...x9] such that the statement "there are integers m1,...,m9 with p(m1,...,m9)=0" can neither be proven nor disproven in ZFC (assuming ZFC is consistent). 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.
- joe_the_user 7y ago
  OK, the way I'd figure it out is: for such a polynomial, you definitely can't find those integers. There isn't any concrete m1...m9 satisfying the condition. The stumbling block is you can't find a proof for this fact in ZFC. 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).
  - dodobirdlord 7y ago
    > OK, the way I'd figure it out is: for such a polynomial, you definitely can't find those integers. There isn't any concrete m1...m9 satisfying the condition. The stumbling block is you can't find a proof for this fact in ZFC. 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. https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html
    - Dylan16807 7y ago
      > If this were formalizable it would be a proof. A proof, but not a proof that can be expressed inside ZFC.
tomp 7y ago
I'm tempted to exclude the Axiom of Choice (AC) from any math I do, and instead include the Axiom of Determinacy (AD) [1] (which contradicts AC), so that all subsets of R^n are measurable [2] (thus precluding the Banach–Tarski paradox), and the Axiom of Dependent Choice (DC), which is weaker than AC but sufficient to develop most of real analysis. Like, I don't really care if not all vector spaces have a basis; it's enough for me that all interesting vector spaces do (I think). 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 https://en.wikipedia.org/wiki/Axiom_of_determinacy [2] https://en.wikipedia.org/wiki/Solovay_model https://en.wikipedia.org/wiki/Solovay_model [3] https://en.wikipedia.org/wiki/Axiom_of_choice#Statements_consistent_with_the_negation_of_AC https://en.wikipedia.org/wiki/Axiom_of_choice#Statements_con...
- ginnungagap 7y ago
  In fact it's an open problem (very likely the oldest open problem in set theory) whether in every model of not AC there is a set with such a paradoxical partition! Here's a nice introduction to the problem by Asaf Karagila http://karagila.org/2014/on-the-partition-principle/ http://karagila.org/2014/on-the-partition-principle/
- ot 7y ago
  "The Axiom of Choice is obviously true, the Well–ordering theorem is obviously false; and who can tell about Zorn’s Lemma?"
chrisweekly 7y ago
"The mathematical statements discussed below are provably independent of ZFC (the canonical axiomatic set theory of contemporary mathematics, consisting of the Zermelo–Fraenkel axioms plus the axiom of choice), assuming that ZFC is consistent. A statement is independent of ZFC (sometimes phrased "undecidable in ZFC") if it can neither be proven nor disproven from the axioms of ZFC." - TFA
- chrisweekly 7y ago
  "ZFC" is an esoteric acronym; I posted the quote from the article to help others because the title was entirely opaque to me.

104 points by killlameme99 7y ago

Rerarom 7y ago

Hopefully this will clear at least some of the Gödelian misconceptions that pop up from time to time here

JadeNB 7y ago
How? Misunderstandings about Gödel's theorem are unlikely to be due to a misunderstanding of the axioms of set theory (more likely of logical issues such as the technical meaning of 'incompleteness'), let alone to a lack of understanding of what statements are independent of a common set of axioms.
utopian3 7y ago
Which Gödel misconceptions?

triska 7y ago

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-reasonable-sounding-statements-that-are-independent-of-zfc/6594 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.

sansnomme 7y ago
Cantor bad.
- egdod 7y ago
  What does this have to do with Cantor?
  - saagarjha 7y ago
    Cantor did work on cardinalities, presumably.
    - sansnomme 7y ago
      He practically invented the field.
      - saagarjha 7y ago
        There's an implicit "because" at the front there, I know about Cantor's influence quite well ;)
  - GraemeL 7y ago
    ZFC was created to avoid the paradoxes inherent in Cantor's set theory work.
    - JadeNB 7y ago
      I think it's fairer to say that ZFC was a response to paradoxes in naïve set theory of the sort discovered by Russell than in response to Cantor; see, e.g., > In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. (https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory). Cantor discovered a rigorous basis for the intuitively paradoxical situation of two sets where it seems that one is manifestly bigger, but they are actually the same size; but I think that this work is best viewed as a resolution of the paradox, not a paradox itself.
- dang 7y ago
  Please don't post unsubstantive comments here.
egdod 7y ago
That is a strange one.
- yarg 7y ago
  Infinities are strange.
- pvarangot 7y ago
  Try thinking about how you could probe that the integers have fewer subsets than the reals using ZFC.
  - Enginerrrd 7y ago
    That still feels intuitive. Like for any open interval there are uncountably many reals and a finite number of integers. It seems like nothing changes as you expand the interval.
    - rodamaral 7y ago
      The integers HAVE fewer subsets than the reals! Cantor's theorem tells us that the power set of any set has more elements than said set. It's also well known that the reals have the same cardinality as the power set of the integers. 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)|.
  - deleted 7y ago
    [deleted]
The_rationalist 7y ago
WTF I'm pretty sure I can prove that
- ur-whale 7y ago
  >I'm pretty sure I can prove that For infinite sets of arbitrarily large cardinality?
  - The_rationalist 7y ago
    No I can't. But see my answer to correct_horse
- correct_horse 7y ago
  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/Aleph_number https://en.wikipedia.org/wiki/Aleph_number
  - The_rationalist 7y ago
    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 an optional extension to the mathematical framework instead of being the default, in order to not pollute discussions.
    - new2628 7y ago
      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 https://en.wikipedia.org/wiki/Finitism Doron Zeilberger would like to pat you on the back.
ur-whale 7y ago
So, does that mean that one can assume this to be true and build a perfectly consistent theory, or conversely assume it to be false (with - say - at least one counter-example) and build another perfectly consistent theory?
- deleted 7y ago
  [deleted]
- karatinversion 7y ago
  Yes, this is the exact meaning of “independent from” here.
- deepsun 7y ago
  Well, it's not possible to prove the consistency, thanks to Godel. Maybe one of your new theories would contain a statement, inconsistent with the rest of ZFC.
  - CrazyStat 7y ago
    This is incorrect. It absolutely is possible to prove consistency, what Gödel tells us is that in any consistent logic system there are true but unprovable (in that system) statements. For this particular list, the statements have been proven to both be consistent with ZFC and for their negations to be consistent with ZFC.
    - ithinkso 7y ago
      This is first incompleteness theorem. What deepsun was referring to is second incompleteness theorem - in a consistent system F the statement 'F is consistent' is in fact unprovable (in F).
  - ginnungagap 7y ago
    When we say that a statement P is independent of ZFC what we're really saying is "if ZFC is consistent, then P is independent of ZFC (hence both ZFC+P and ZFC+not P are consistent)". 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
ginnungagap 7y ago
It gets worse than that, by Easton's theorem, except for two mild restrictions provable on ZFC, the function that sends a regular cardinal to the cardinality of its powerset can be anything

mturmon 7y ago

Some of this was familiar, but I also saw this: > 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!]

ginnungagap 7y ago
Another famous example of that kind is the existence of outer automorphisms of the Calkin algebra, which is a simple question about a naturally occuring object which turned out to be independent of ZFC by work of Farah and Weaver. 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!

daxfohl 7y ago

Why is it always zfc plus optionally something else? Is there anything other than zfc that creates an interesting starting point?

triska 7y ago
These are excellent questions! And yes, there is! For example, I highly recommend the paper Rethinking set theory by Tom Leinster: https://arxiv.org/abs/1212.6543 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-communities/maa-awards/writing-awards/chauvenet-prizes https://www.maa.org/programs-and-communities/member-communit...
- QuesnayJr 7y ago
  Isn't Lawvere set theory equiconsistent with bounded Zermelo set theory? 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.
andrepd 7y ago
https://en.m.wikipedia.org/wiki/New_Foundations https://en.m.wikipedia.org/wiki/New_Foundations
empath75 7y ago
https://en.m.wikipedia.org/wiki/Univalent_foundations https://en.m.wikipedia.org/wiki/Univalent_foundations

maest 7y ago

What's a reasonable strategy of proving a statement like that is undecidable in ZFC? I think it must use some tools I'm unfamiliar with.

The_rationalist 7y ago
I believe it is what is called metalogical proofs
deleted 7y ago
[deleted]
aetilley 7y ago
To show that a sentence P is independent of a theory (that is, a set of sentences) T, generally one constructs or demonstrates the existence of a model of T + P and also produces a model of T + (not P). https://en.wikipedia.org/wiki/Model_theory https://en.wikipedia.org/wiki/Model_theory
danharaj 7y ago
Start with Forcing https://ncatlab.org/nlab/show/forcing https://ncatlab.org/nlab/show/forcing https://en.wikipedia.org/wiki/Forcing_(mathematics) https://en.wikipedia.org/wiki/Forcing_(mathematics)
sn41 7y ago
There are 2 popular ways. 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.
lmm 7y ago
Show that it implies the consistency of ZFC, and that its negation also does so. Or show that it's equivalent to a statement that's already on that list.
7y ago

etaioinshrdlu 7y ago

I love seeing pure math on HN. I think math is the purest expression of what it means to be curious. It sometimes gives us fun toys to build into whatever we are coding.

ArchReaper 7y ago

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?

gjm11 7y ago
[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.

reggieband 7y ago

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 to calculus and beyond. 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-Mathematics/dp/0486435202 https://www.amazon.com/Philosophy-Set-Theory-Introduction-Ma... 2. https://en.wikipedia.org/wiki/Logicomix https://en.wikipedia.org/wiki/Logicomix

empath75 7y ago
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.

est31 7y ago

In other news, there's recently been a mechanized proof for one of the ZFC independent problems: https://flypitch.github.io/papers/ https://flypitch.github.io/papers/ https://news.ycombinator.com/item?id=21823618 https://news.ycombinator.com/item?id=21823618

mirimir 7y ago

Might something like this be fscking unification in physics?

drdeca 7y ago
I doubt it. Physics doesn’t seem to have much which is clearly connected to proof systems. 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).
- mirimir 7y ago
  Thanks. But doesn't that lead to systems with infinite numbers of axioms?
  - drdeca 7y ago
    If you want to add axioms in order to be able to show each of an infinite number of statements which are all independent of the initial axiom system, and also none of them follow from the rest of them, that could involve an infinite set of axioms, yes, 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.

joe_the_user 7y ago

One can write down a concrete polynomial p ∈ Z[x1,...x9] such that the statement "there are integers m1,...,m9 with p(m1,...,m9)=0" can neither be proven nor disproven in ZFC (assuming ZFC is consistent). 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.

joe_the_user 7y ago
OK, the way I'd figure it out is: for such a polynomial, you definitely can't find those integers. There isn't any concrete m1...m9 satisfying the condition. The stumbling block is you can't find a proof for this fact in ZFC. 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).
- dodobirdlord 7y ago
  > OK, the way I'd figure it out is: for such a polynomial, you definitely can't find those integers. There isn't any concrete m1...m9 satisfying the condition. The stumbling block is you can't find a proof for this fact in ZFC. 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. https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html
  - Dylan16807 7y ago
    > If this were formalizable it would be a proof. A proof, but not a proof that can be expressed inside ZFC.

tomp 7y ago

I'm tempted to exclude the Axiom of Choice (AC) from any math I do, and instead include the Axiom of Determinacy (AD) [1] (which contradicts AC), so that all subsets of R^n are measurable [2] (thus precluding the Banach–Tarski paradox), and the Axiom of Dependent Choice (DC), which is weaker than AC but sufficient to develop most of real analysis. Like, I don't really care if not all vector spaces have a basis; it's enough for me that all interesting vector spaces do (I think). 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 https://en.wikipedia.org/wiki/Axiom_of_determinacy [2] https://en.wikipedia.org/wiki/Solovay_model https://en.wikipedia.org/wiki/Solovay_model [3] https://en.wikipedia.org/wiki/Axiom_of_choice#Statements_consistent_with_the_negation_of_AC https://en.wikipedia.org/wiki/Axiom_of_choice#Statements_con...

ginnungagap 7y ago
In fact it's an open problem (very likely the oldest open problem in set theory) whether in every model of not AC there is a set with such a paradoxical partition! Here's a nice introduction to the problem by Asaf Karagila http://karagila.org/2014/on-the-partition-principle/ http://karagila.org/2014/on-the-partition-principle/
ot 7y ago
"The Axiom of Choice is obviously true, the Well–ordering theorem is obviously false; and who can tell about Zorn’s Lemma?"

chrisweekly 7y ago

"The mathematical statements discussed below are provably independent of ZFC (the canonical axiomatic set theory of contemporary mathematics, consisting of the Zermelo–Fraenkel axioms plus the axiom of choice), assuming that ZFC is consistent. A statement is independent of ZFC (sometimes phrased "undecidable in ZFC") if it can neither be proven nor disproven from the axioms of ZFC." - TFA

chrisweekly 7y ago
"ZFC" is an esoteric acronym; I posted the quote from the article to help others because the title was entirely opaque to me.