6 ms·

If BB(745) is independent of ZFC can it even be called a value? It seems like you could easily run into paradoxes if you treated it like just any other value.

by im3w1l 3y ago

pas 3y ago
just because it's not provably constructable from axioms it doesn't mean it's not just a finite number. that's the really mindbreaking part in this. it's really just like 5. except 5 is provably constructable, describable, nameable. (most numbers are not, just as - for example - angle trisection is impossible with just a straightedge and a compass ) https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers#Definition_as_von_Neumann_ordinals https://en.wikipedia.org/wiki/Set-theoretic_definition_of_na... http://uu.diva-portal.org/smash/get/diva2:1715729/FULLTEXT01.pdf http://uu.diva-portal.org/smash/get/diva2:1715729/FULLTEXT01...
Kranar 3y ago
There is no paradox and yes, BB(745) is a specific integer, so it's nothing more than a sequence of finite digits. The fact BB(745) can't be constructed using ZFC only means that there is at least one Turing machine among the set of all 745 state Turing machines that runs forever, but can't be proven to run forever using the axioms of ZFC. You'd need a more powerful axiomatic system to prove that this Turing machine actually runs forever. This does not imply any kind of paradox or any kind of issue whatsoever in fact. It just means that ZFC is not powerful enough to prove that certain 745 state Turing Machines run forever.
- thaumasiotes 3y ago
  > The fact BB(745) can't be constructed using ZFC only means that [...] ...so what? The claim wasn't that BB(745) can't be constructed using ZFC, or that it's not computable. The claim was that its value is independent of ZFC, that the ZFC axioms do not make any logical implication about the value. This necessarily means that there are multiple possible values; if there were only one value, that value would be logically implied by ZFC regardless of whether it was provable in ZFC. I should also note that these two observations are not compatible with each other: > BB(745) is a specific integer, so it's nothing more than a sequence of finite digits > BB(745) can't be constructed using ZFC All finite digit sequences can be constructed.
  - Kranar 3y ago
    >This necessarily means that there are multiple possible values; if there were only one value, that value would be logically implied by ZFC regardless of whether it was provable in ZFC. This is a false statement. The fact that BB(745) can't be constructed using ZFC does not mean that it has multiple values. All it means is that there is at least one Turing Machine that never halts but can't be proven to run forever using ZFC, that is it. BB(745) is one specific integer, there is nothing really special about ZFC in this sense, it's just one axiomatic system that happens to be very useful as the foundation of most of the mathematics that is studied, but one could just as easily work with a different axiomatic system instead. There are values of BB(n) that have no construction using Peano arithmetic but do have a construction in ZF, and there are values of BB(n) that do not have a construction in ZF but have one in ZFC, and there are values of BB(n) that do not have a construction in ZFC but do have one in ZFC + Inaccessible Cardinal Axiom, so on so forth. ZFC does not have some kind of authoritative status in the universe of mathematics; it's possible that an alien race is doing mathematics using a far more powerful axiomatic system in which case BB(745) is constructible but BB(7450) is not. >All finite digit sequences can be constructed. A construction is a proof that provides a means of calculating a given value [1]. The set of all theorems that can be enumerated in ZFC do not contain a construction for the value of BB(745). [1] https://en.wikipedia.org/wiki/Constructive_proof https://en.wikipedia.org/wiki/Constructive_proof
    - thaumasiotes 3y ago
      > A construction is a proof that provides a means of calculating a given value [1]. The set of all theorems that can be enumerated in ZFC do not contain a construction for the value of BB(745). Of course they do. They just don't contain a proof that that value has the relevant properties that define the Busy Beaver sequence. There's a big difference between constructing the value 107 and proving that that same value satisfies a given set of constraints.
      - Kranar 3y ago
        We'll agree to disagree on this point then. My stance is you're using the word construction in a more layman like manner whereas I am using it in the more formal sense. It's not a particularly big deal either way.
tromp 3y ago
BB(745) is some specific number N. Numbers cannot be independent of ZFC. Only boolean valued formulas can be. In this case, the relevant formula F expresses that all 745 state TMs that do not halt within N steps, will never halt. Assuming consistency of ZFC, formula F is true but unprovable in ZFC, and thus independent. Another formula G expresses that some specific 745 state TM halts in exactly N steps. Formula G is true and provable in ZFC. F and G together imply that BB(745) = N.

If BB(745) is independent of ZFC can it even be called a value? It seems like you could easily run into paradoxes if you treated it like just any other value.

by im3w1l 3y ago

If BB(745) is independent of ZFC can it even be called a value? It seems like you could easily run into paradoxes if you treated it like just any other value.

pas 3y ago

just because it's not provably constructable from axioms it doesn't mean it's not just a finite number. that's the really mindbreaking part in this. it's really just like 5. except 5 is provably constructable, describable, nameable. (most numbers are not, just as - for example - angle trisection is impossible with just a straightedge and a compass ) https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers#Definition_as_von_Neumann_ordinals https://en.wikipedia.org/wiki/Set-theoretic_definition_of_na... http://uu.diva-portal.org/smash/get/diva2:1715729/FULLTEXT01.pdf http://uu.diva-portal.org/smash/get/diva2:1715729/FULLTEXT01...

Kranar 3y ago

There is no paradox and yes, BB(745) is a specific integer, so it's nothing more than a sequence of finite digits. The fact BB(745) can't be constructed using ZFC only means that there is at least one Turing machine among the set of all 745 state Turing machines that runs forever, but can't be proven to run forever using the axioms of ZFC. You'd need a more powerful axiomatic system to prove that this Turing machine actually runs forever. This does not imply any kind of paradox or any kind of issue whatsoever in fact. It just means that ZFC is not powerful enough to prove that certain 745 state Turing Machines run forever.

thaumasiotes 3y ago
> The fact BB(745) can't be constructed using ZFC only means that [...] ...so what? The claim wasn't that BB(745) can't be constructed using ZFC, or that it's not computable. The claim was that its value is independent of ZFC, that the ZFC axioms do not make any logical implication about the value. This necessarily means that there are multiple possible values; if there were only one value, that value would be logically implied by ZFC regardless of whether it was provable in ZFC. I should also note that these two observations are not compatible with each other: > BB(745) is a specific integer, so it's nothing more than a sequence of finite digits > BB(745) can't be constructed using ZFC All finite digit sequences can be constructed.
- Kranar 3y ago
  >This necessarily means that there are multiple possible values; if there were only one value, that value would be logically implied by ZFC regardless of whether it was provable in ZFC. This is a false statement. The fact that BB(745) can't be constructed using ZFC does not mean that it has multiple values. All it means is that there is at least one Turing Machine that never halts but can't be proven to run forever using ZFC, that is it. BB(745) is one specific integer, there is nothing really special about ZFC in this sense, it's just one axiomatic system that happens to be very useful as the foundation of most of the mathematics that is studied, but one could just as easily work with a different axiomatic system instead. There are values of BB(n) that have no construction using Peano arithmetic but do have a construction in ZF, and there are values of BB(n) that do not have a construction in ZF but have one in ZFC, and there are values of BB(n) that do not have a construction in ZFC but do have one in ZFC + Inaccessible Cardinal Axiom, so on so forth. ZFC does not have some kind of authoritative status in the universe of mathematics; it's possible that an alien race is doing mathematics using a far more powerful axiomatic system in which case BB(745) is constructible but BB(7450) is not. >All finite digit sequences can be constructed. A construction is a proof that provides a means of calculating a given value [1]. The set of all theorems that can be enumerated in ZFC do not contain a construction for the value of BB(745). [1] https://en.wikipedia.org/wiki/Constructive_proof https://en.wikipedia.org/wiki/Constructive_proof
  - thaumasiotes 3y ago
    > A construction is a proof that provides a means of calculating a given value [1]. The set of all theorems that can be enumerated in ZFC do not contain a construction for the value of BB(745). Of course they do. They just don't contain a proof that that value has the relevant properties that define the Busy Beaver sequence. There's a big difference between constructing the value 107 and proving that that same value satisfies a given set of constraints.
    - Kranar 3y ago
      We'll agree to disagree on this point then. My stance is you're using the word construction in a more layman like manner whereas I am using it in the more formal sense. It's not a particularly big deal either way.

tromp 3y ago

BB(745) is some specific number N. Numbers cannot be independent of ZFC. Only boolean valued formulas can be. In this case, the relevant formula F expresses that all 745 state TMs that do not halt within N steps, will never halt. Assuming consistency of ZFC, formula F is true but unprovable in ZFC, and thus independent. Another formula G expresses that some specific 745 state TM halts in exactly N steps. Formula G is true and provable in ZFC. F and G together imply that BB(745) = N.