Second order logic may be able to express all expressible statements in 3rd order logic, 4th order, up to any finite Nth order, but perhaps there exist ∞th order statements that 2nd order logic cannot express. Albeit, such statements could never be fully decidable and would thus be, at best, semidecidable or co-semidecidable. This may not be complete, but science works the same way.
Nope, 2nd-order logic can discuss Nth order where N is an infinite ordinal, as well [for some class of describable ordinals]. Maybe the argument could be made that 2nd-order logic cannot discuss a universe containing all the ordinals, and in that case maybe we could argue that set theory can, and is therefore more powerful. But this is not clear.
Independently of that, we might also believe that category theory can describe things beyond set theory, because category theory regularly investigates categories which correspond to “large” sets (such as the set of all sets). There are ways to put category theory into set theory, but these translate the “large” sets into “small” sets such as Grothendeik universes, so we could still argue that the semantics of category theory is bigger.
However, even if this is the case, it might be that 2nd-order logic can encode category theory in the same way that it can encode 3rd-order logic. We can add axioms to 2nd-order logic which describe non-standard set theories containing “big” sets, such as NF. This may allow for an “honest” account of category theory, in which categories really can be defined on “big” sets such as the set of all sets.
I don’t think they have anything to do with each other. Infinitary logic is first-order logic with infinite proof lengths. Second-order logic is finite proof lengths with quantification over predicates. I don’t know if there’s any particular known relation between what these two theories can express.
Third order logic talks about something that we don’t understand, and we don’t understand it in exactly the same way that the first-order aliens can’t understand second order logic.
One of the things third order logic might be able to do is determine the number of steps a Turing will take before halting in a constant-time algorithm.
Actually, the halting problem has been proven impossible, for if third order logic can be used to determine if/when a turing machine halts, a turing machine could run that on itself, but would take necessarily more than N steps to determine that it halts (where N is the number of steps it halts in), which contradicts. Third-order logic may be able to do the inconceivable, but not the noncomputable.
That’s not the standard proof, at least not the one I know: You haven’t proven that it would necessarily take more than N steps. The way it goes is that you assume there is a machine that halts iff the machine you give it runs forever given itself as input; now if you run it on itself, if it halts, it is wrong, and if it doesn’t halt, it is also wrong, meaning our assumption was wrong.
Turing machines can’t use third order logic. That might be a limitation of the programmer, or it might be a limitation of deterministic machines. A Turing machine can’t ever compute anything about it’s own output; third order logic might allow deterministic machines which can compute the results of their own output.
I suspect that there is a halting problem where the halting status of machines which only use second order logic cannot be computed in third order logic, just like limits cannot be computed in Peano arithmetic.
Second order logic may be able to express all expressible statements in 3rd order logic, 4th order, up to any finite Nth order, but perhaps there exist ∞th order statements that 2nd order logic cannot express. Albeit, such statements could never be fully decidable and would thus be, at best, semidecidable or co-semidecidable. This may not be complete, but science works the same way.
Nope, 2nd-order logic can discuss Nth order where N is an infinite ordinal, as well [for some class of describable ordinals]. Maybe the argument could be made that 2nd-order logic cannot discuss a universe containing all the ordinals, and in that case maybe we could argue that set theory can, and is therefore more powerful. But this is not clear.
Independently of that, we might also believe that category theory can describe things beyond set theory, because category theory regularly investigates categories which correspond to “large” sets (such as the set of all sets). There are ways to put category theory into set theory, but these translate the “large” sets into “small” sets such as Grothendeik universes, so we could still argue that the semantics of category theory is bigger.
However, even if this is the case, it might be that 2nd-order logic can encode category theory in the same way that it can encode 3rd-order logic. We can add axioms to 2nd-order logic which describe non-standard set theories containing “big” sets, such as NF. This may allow for an “honest” account of category theory, in which categories really can be defined on “big” sets such as the set of all sets.
I don’t think that infinitary logic is the same as ω-order logic.
Wouldn’t ω-order logic be a subset of infinitary logic? Or do I have it backwards?
I don’t think they have anything to do with each other. Infinitary logic is first-order logic with infinite proof lengths. Second-order logic is finite proof lengths with quantification over predicates. I don’t know if there’s any particular known relation between what these two theories can express.
Third order logic talks about something that we don’t understand, and we don’t understand it in exactly the same way that the first-order aliens can’t understand second order logic.
One of the things third order logic might be able to do is determine the number of steps a Turing will take before halting in a constant-time algorithm.
Actually, the halting problem has been proven impossible, for if third order logic can be used to determine if/when a turing machine halts, a turing machine could run that on itself, but would take necessarily more than N steps to determine that it halts (where N is the number of steps it halts in), which contradicts. Third-order logic may be able to do the inconceivable, but not the noncomputable.
That’s not the standard proof, at least not the one I know: You haven’t proven that it would necessarily take more than N steps. The way it goes is that you assume there is a machine that halts iff the machine you give it runs forever given itself as input; now if you run it on itself, if it halts, it is wrong, and if it doesn’t halt, it is also wrong, meaning our assumption was wrong.
Turing machines can’t use third order logic. That might be a limitation of the programmer, or it might be a limitation of deterministic machines. A Turing machine can’t ever compute anything about it’s own output; third order logic might allow deterministic machines which can compute the results of their own output.
I suspect that there is a halting problem where the halting status of machines which only use second order logic cannot be computed in third order logic, just like limits cannot be computed in Peano arithmetic.