Mathematics and logic
My study of mathematics began with a wish to understand mathematical reasoning, but subsequently, and to my own surprise, solutions to difficult problems posed in mathematics arose.
The continuum and halting problems
What second order concepts tell us about the continuum
The continuum is that object that serves as the foundation of mathematical analysis - the differential and integral calculus. A well-known unsolved problem arising from the work of Cantor is that of the size of the continuum. The reason why this problem has gone unsolved in the C20th is due to the insistence on using first-order set theory. In this essay I explore the phenomenological and empirical foundations of the classical concept of the continuum, and then derive the continuum hypothesis from the second-order Axiom of Completeness. For a more detailed account of this work, please read the abstract and/or download the paper.
Solution to the Halting problem
Lagrange's theorem
The halting problem is the problem of determining whether a Turing machine will halt for a given input. One of the results of modern computing theory - we may imagine it written on a tablet of stone - is that the halting problem cannot be solved. However, this argument, a proof by contradiction, like any other argument has premises. Two of the hidden premises are (a) that there is no distinction between the potential and actual infinite, and (b) that proof by mathematical induction is a form of algorithm. The important point is to realise that there is a distinction between proving that we know something, and having an algorithm that computes a result. The impossibility proof, then, is a proof that any machine that computed an algorithm would need an actually infinite number of parts, and as this is impossible, a computer cannot be built to solve the problem. But this is only an impossiblity proof for compouters, not for the human mind. It turns out that a proof that the halting problem for any Turing machine can be solved is a relatively simple induction on the number of states of a Turing machine. Furthermore, as Turing machines decompose into cycles, and these are connected with permutation groups, there is a deep connection between the solvability of the Halting problem and group theory. In a separate essay I analyse Lagrange's Theorem, that the order of a subgroup divides into the order of a group, and explain why Lagrange's theorem cannot be formalised in first-order logic, it having been remarked by Beson that it has so far resisted such a formulation.
I intend to rewrite these papers in the future, following a thorough review of Galois theory, as I wish to unconver the deep connection between Turing machines and group structure.
I intend to rewrite these papers in the future, following a thorough review of Galois theory, as I wish to unconver the deep connection between Turing machines and group structure.
Franciska by Peter Paul Fekete