4 ms·

> Of course, I'll now fall back on godel's second incompleteness theorem and say that one cannot prove, inside ZFC, that ZFC is consistent. But if the above tur

> Of course, I'll now fall back on godel's second incompleteness theorem and say that one cannot prove, inside ZFC, that ZFC is consistent. But if the above turing machine halts, then we proved ZFC is consistent - a contradiction! No, the machine halts iff ZFC is inconsistent -- as you correctly stated up top. Somewhere along the way you got this reversed, looks like. There's the problem.

tybug 3y ago
You're right, I misstated this - but I don't think this is fatal. The other sibling commenters pointed out the real issue with my thinking. The argument goes the same even though I misspoke here. If the machine {halts, runs forever} then ZFC is consistent. But this is a contradiction; so ZFC must be inconsistent. Tada, I have an inconsistency proof! That was the implied next step which made me think my logic was clearly incorrect (which, it was).
- tux3 3y ago
  It's simpler than this still. If it runs forever (likely), then you will never be able to say anything about ZFC. If you see it halt, ZFC is inconsistent. If you never see it halt, you CAN'T conclude anything. But we could already do that under Gödel incompleteness, so there's nothing unusual there! If you write down random proofs on paper and find a correct proof that leads to contradiction, you've proved ZFC inconsistent, without using BB. If you keep trying forever and never find one, you'll never be able to conclude anything at any point, just like with watching the machine run
  - l33t7332273 3y ago
    > If it runs forever (likely), then you will never be able to say anything about ZFC. But if you run it for BB(754) many steps, you will know.
    - tux3 3y ago
      Yep. But I think it's easy to show that this is circular, since you can't know BB(754) without knowing whether it runs forever. And you can't prove that it'll run forever without seeing it go past BB(754) and still keep going BB(754) is X if ZFC is consistent, Y otherwise Since you can't prove that ZFC is consistent (only disprove), you can't know BB(754), which is the thing we were trying to use to determine whether ZFC is consistent in the first place! The definition doesn't make it obvious, but this is just the same as plain Gödel incompleteness, we can't get any extra info about ZFC even in principle (unless we happen to see it halt, by chance)
- bmacho 3y ago
  > You're right, I misstated this - but I don't think this is fatal. It is crucial at this types of results, when you search for a proof. There are a lot of things true, better make a table of it, instead of a wall of text: - If you observe the machine halting, ZFC is inconsistent. - If the machine hasn't halted yet, you don't know if ZFC is consistent or not. - If ZFC is inconsistent, the machine will eventually halt. (You have an upper bound for this, given a contradiction.) - If ZFC is consistent, then the machine won't halt ever. Also it is consistent with ZFC that this machine halts, since it is consistent with ZFC that ZFC has a contradiction. This means that if ZFC happens to be consistent, and you work in ZFC+contradiction, then you will know that your machine will eventually halt, yet it won't halt ever.
l33t7332273 3y ago
I don’t think that’s it. I think it’s easy to take such a machine and make a new one that halts iff ZFC is consistent. Call the machine that halts iff ZFC is inconsistent A. Now consider the machine which computes the following algorithm: Run A BB(754) times. If A halts, then run forever, else halt. If A halts then our machine runs forever, and vice versa. Thus, our machine halts when ZFC is consistent and our machine runs forever when A halts, so ZFC is consistent iff our machine halts. “Halts” doesn’t seem like a real word after writing that.
- meithecatte 3y ago
  How do you make the new machine compute BB(754)? BB is the canonical example of an uncomputable function, precisely because you can decide the halting problem if you can compute it (or any upper bound). Granted, BB may be computed for specific arguments, as OP mentions for 1–4, but the existence of the ZFC-dependent machine is, at least to me, a very good argument that the boundary of what's possible is much lower.
  - l33t7332273 3y ago
    Oh, sure. I was just pointing out that the hardness is in determining the busy beaver number and that it didn’t matter if your algorithm halts iff ZFC is consistent or if it’s an algorithm that halts iff ZFC is inconsistent.
    - dullcrisp 3y ago
      No, if you had an algorithm that (you could prove) halts iff ZFC is consistent, then if that algorithm halts, you’ll have a proof that ZFC is consistent, which isn’t possible. Thus, the existence of such an algorithm would be a contradiction that proves the inconsistency of ZFC. The problem with your construction is that it relies on knowing the value of BB(754), which is impossible to know so long as ZFC is consistent, since its value is dependent on the consistency of ZFC. Conversely, if ZFC is inconsistent, then there exists a (finite) proof of this fact, so the opposite case isn’t a problem. Essentially it’s like saying define X to be the length of the shortest proof of the inconsistency of ZFC, if one exists. If I could prove any upper bound on X, I could prove the consistency of ZFC, which, according to Gödel’s incompleteness theorem, would itself prove the inconsistency of ZFC.

tybug 3y ago

You're right, I misstated this - but I don't think this is fatal. The other sibling commenters pointed out the real issue with my thinking. The argument goes the same even though I misspoke here. If the machine {halts, runs forever} then ZFC is consistent. But this is a contradiction; so ZFC must be inconsistent. Tada, I have an inconsistency proof! That was the implied next step which made me think my logic was clearly incorrect (which, it was).

tux3 3y ago
It's simpler than this still. If it runs forever (likely), then you will never be able to say anything about ZFC. If you see it halt, ZFC is inconsistent. If you never see it halt, you CAN'T conclude anything. But we could already do that under Gödel incompleteness, so there's nothing unusual there! If you write down random proofs on paper and find a correct proof that leads to contradiction, you've proved ZFC inconsistent, without using BB. If you keep trying forever and never find one, you'll never be able to conclude anything at any point, just like with watching the machine run
- l33t7332273 3y ago
  > If it runs forever (likely), then you will never be able to say anything about ZFC. But if you run it for BB(754) many steps, you will know.
  - tux3 3y ago
    Yep. But I think it's easy to show that this is circular, since you can't know BB(754) without knowing whether it runs forever. And you can't prove that it'll run forever without seeing it go past BB(754) and still keep going BB(754) is X if ZFC is consistent, Y otherwise Since you can't prove that ZFC is consistent (only disprove), you can't know BB(754), which is the thing we were trying to use to determine whether ZFC is consistent in the first place! The definition doesn't make it obvious, but this is just the same as plain Gödel incompleteness, we can't get any extra info about ZFC even in principle (unless we happen to see it halt, by chance)
bmacho 3y ago
> You're right, I misstated this - but I don't think this is fatal. It is crucial at this types of results, when you search for a proof. There are a lot of things true, better make a table of it, instead of a wall of text: - If you observe the machine halting, ZFC is inconsistent. - If the machine hasn't halted yet, you don't know if ZFC is consistent or not. - If ZFC is inconsistent, the machine will eventually halt. (You have an upper bound for this, given a contradiction.) - If ZFC is consistent, then the machine won't halt ever. Also it is consistent with ZFC that this machine halts, since it is consistent with ZFC that ZFC has a contradiction. This means that if ZFC happens to be consistent, and you work in ZFC+contradiction, then you will know that your machine will eventually halt, yet it won't halt ever.

l33t7332273 3y ago

I don’t think that’s it. I think it’s easy to take such a machine and make a new one that halts iff ZFC is consistent. Call the machine that halts iff ZFC is inconsistent A. Now consider the machine which computes the following algorithm: Run A BB(754) times. If A halts, then run forever, else halt. If A halts then our machine runs forever, and vice versa. Thus, our machine halts when ZFC is consistent and our machine runs forever when A halts, so ZFC is consistent iff our machine halts. “Halts” doesn’t seem like a real word after writing that.

meithecatte 3y ago
How do you make the new machine compute BB(754)? BB is the canonical example of an uncomputable function, precisely because you can decide the halting problem if you can compute it (or any upper bound). Granted, BB may be computed for specific arguments, as OP mentions for 1–4, but the existence of the ZFC-dependent machine is, at least to me, a very good argument that the boundary of what's possible is much lower.
- l33t7332273 3y ago
  Oh, sure. I was just pointing out that the hardness is in determining the busy beaver number and that it didn’t matter if your algorithm halts iff ZFC is consistent or if it’s an algorithm that halts iff ZFC is inconsistent.
  - dullcrisp 3y ago
    No, if you had an algorithm that (you could prove) halts iff ZFC is consistent, then if that algorithm halts, you’ll have a proof that ZFC is consistent, which isn’t possible. Thus, the existence of such an algorithm would be a contradiction that proves the inconsistency of ZFC. The problem with your construction is that it relies on knowing the value of BB(754), which is impossible to know so long as ZFC is consistent, since its value is dependent on the consistency of ZFC. Conversely, if ZFC is inconsistent, then there exists a (finite) proof of this fact, so the opposite case isn’t a problem. Essentially it’s like saying define X to be the length of the shortest proof of the inconsistency of ZFC, if one exists. If I could prove any upper bound on X, I could prove the consistency of ZFC, which, according to Gödel’s incompleteness theorem, would itself prove the inconsistency of ZFC.