5 ms·

Not the parent, but the argument uses quite a few assumptions (axioms) that may not be intuitive to everyone, but which are quite relevant when studying mathema

by smokel 3y ago

Not the parent, but the argument uses quite a few assumptions (axioms) that may not be intuitive to everyone, but which are quite relevant when studying mathematics at the foundational level. For example, why would one be able to create the diagonal set (those indices of the power set elements that do not contain that index as an element) and the enumeration of the power set (i.e. the entire list of possible sets of numbers) at the same time? The theorem proves that an enumeration of the power set cannot be made. Perhaps some sets cannot be constructed at will just by writing down its properties either? In computer land, one would quickly run into self-referential problems when constructing sets like these. For mathematics of this kind, most people agree that this is all fine, and one can derive interesting things from it. But one can also reject the approach and still do some elementary fun stuff. Then again, I might be completely misunderstanding all of this, and I love to be corrected. Edit: wording

openasocket 3y ago
I’m not sure there’s many axioms used. Given any set A, and a function from A to the power set, P(A), construct the set X = {a in A | a is not in f(a) }. Here all we’re using is the power set axiom to define the power set and the subset axiom schema to construct X. We claim there is no a such that f(a) = X. If there was such an a, is a in X? By construction, a is in X if and only if a is not in X, just by first order logic, which is a contradiction. Thus, X is not in the image of f, so f is not a bijection. Thus, there is no bijection from A to P(A). And that’s it. We don’t even need the axiom of choice
- deleted 3y ago
  [deleted]
- cubefox 3y ago
  You can't prove such a thing in ZFC [1]. ZFC's "power set axiom" is a misnomer. It doesn't imply the existence of infinite power sets. It just says if any set S exists and is a subset of an infinite set A, then S is element of a set P (the supposed "power set"). But the axiom doesn't imply the existence of "all" subsets of A. There is no way for first-order logic to state "every possible combination of elements of A forms a set". And Cantor's theorem stating that there is no mapping f from A onto P merely means that the mapping f itself can't exist inside a model of ZFC. [2] [1] Or any other theory of first-order logic. [2] This is explained in more detail in Stewart Shapiro's book "Foundation without Foundationalism" p. 114f.
  - openasocket 3y ago
    I’m uncertain what your point is. Like I said, in ZFC, there is no bijection from A to its power set. I don’t think anything you’ve stated contradicts that. Are there alternative axiom systems in which you can construct such a bijection?
    - cubefox 3y ago
      There is no bijection (surjection, to be more general) from A to P inside your ZFC model even if both A and P are assumed to be countable. The bijection we talk about here would be just another object inside the model. So you can't infer from the lack of such an object that P is uncountable.
      - openasocket 3y ago
        Yeah, Cantors theorem is a theorem written in the language of ZFC set theory. In other axiom systems it may not be true. But you can also say that about literally every theorem beyond, like, modus ponens. Is that the point you are trying to make?
        cubefox 3y ago
        The point is simply that it doesn't imply the existence of uncountable sets in ZFC. Modus ponens is different. The semantic entailment relation ⊨ between (P→Q, P) and Q is valid iff there is no model such that the former is true and the latter is false. Which is a sentence in plain English. It doesn't require the existence of some object that is mapping the premises to the conclusion inside the model. It doesn't even require the existence of a syntactic deduction rule (⊢) that tells you from (P→Q, P) to infer Q.
        ginnungagap 3y ago
        It is a theorem of ZFC that uncountable sets exist and every model of ZFC will have a set that the model believes to be uncountable. It doesn't matter than the metatheory might believe that model to be countable (why should the metatheory have the correct notion of what it means to be countable anyway?).

by smokel 3y ago

openasocket 3y ago

I’m not sure there’s many axioms used. Given any set A, and a function from A to the power set, P(A), construct the set X = {a in A | a is not in f(a) }. Here all we’re using is the power set axiom to define the power set and the subset axiom schema to construct X. We claim there is no a such that f(a) = X. If there was such an a, is a in X? By construction, a is in X if and only if a is not in X, just by first order logic, which is a contradiction. Thus, X is not in the image of f, so f is not a bijection. Thus, there is no bijection from A to P(A). And that’s it. We don’t even need the axiom of choice

deleted 3y ago
[deleted]
cubefox 3y ago
You can't prove such a thing in ZFC [1]. ZFC's "power set axiom" is a misnomer. It doesn't imply the existence of infinite power sets. It just says if any set S exists and is a subset of an infinite set A, then S is element of a set P (the supposed "power set"). But the axiom doesn't imply the existence of "all" subsets of A. There is no way for first-order logic to state "every possible combination of elements of A forms a set". And Cantor's theorem stating that there is no mapping f from A onto P merely means that the mapping f itself can't exist inside a model of ZFC. [2] [1] Or any other theory of first-order logic. [2] This is explained in more detail in Stewart Shapiro's book "Foundation without Foundationalism" p. 114f.
- openasocket 3y ago
  I’m uncertain what your point is. Like I said, in ZFC, there is no bijection from A to its power set. I don’t think anything you’ve stated contradicts that. Are there alternative axiom systems in which you can construct such a bijection?
  - cubefox 3y ago
    There is no bijection (surjection, to be more general) from A to P inside your ZFC model even if both A and P are assumed to be countable. The bijection we talk about here would be just another object inside the model. So you can't infer from the lack of such an object that P is uncountable.
    - openasocket 3y ago
      Yeah, Cantors theorem is a theorem written in the language of ZFC set theory. In other axiom systems it may not be true. But you can also say that about literally every theorem beyond, like, modus ponens. Is that the point you are trying to make?
      - cubefox 3y ago
        The point is simply that it doesn't imply the existence of uncountable sets in ZFC. Modus ponens is different. The semantic entailment relation ⊨ between (P→Q, P) and Q is valid iff there is no model such that the former is true and the latter is false. Which is a sentence in plain English. It doesn't require the existence of some object that is mapping the premises to the conclusion inside the model. It doesn't even require the existence of a syntactic deduction rule (⊢) that tells you from (P→Q, P) to infer Q.
        ginnungagap 3y ago
        It is a theorem of ZFC that uncountable sets exist and every model of ZFC will have a set that the model believes to be uncountable. It doesn't matter than the metatheory might believe that model to be countable (why should the metatheory have the correct notion of what it means to be countable anyway?).