Diagonalization Without Sets
Avoiding actual infinities
Carl Gauss is of course beyond famous, but he had a view of infinity that was based on old ideas. He once wrote in a letter to Heinrich Schumacher in 1831:
so protestiere ich zuvörderst gegen den Gebrauch einer unendlichen Größe als einer vollendeten, welcher in der Mathematik niemals erlaubt ist. Das Unendliche ist nur eine façon de parler, indem man eigentlich von Grenzen spricht, denen gewisse Verhältnisse so nahe kommen als man will, während anderen ohne Einschränkung zu wachsen gestattet ist.
Today we want to show that the famous diagonal argument can be used without using infinite sets.
The issue that Gauss was troubled by was the notion of an actual infinite object. For those who do not read German—or French—Ken translates the above quotation as follows:
first of all I must protest against the use of an infinite magnitude as a completed quantity, which is never allowed in mathematics. The Infinite is just a mannner of speaking, in which one is really talking in terms of limits, which certain ratios may approach as close as one wishes, while others may be allowed to increase without restriction.
Georg Cantor famously created the theory of sets, the theory of actual infinite objects, and proved many amazing results about them. His proof that the subsets of the natural numbers are uncountable is a classic result, which we have talked about before and even in video.
Infinite Processes
Suppose that we reject the actual infinite. But we allow a process that goes on forever. This is like saying per Gauss that it is allowed to “increase without restriction.” This is certainly a reasonable position, and one that perhaps Gauss and those of his time would have accepted. Thus we will avoid actual infinite sets, and follow ancient mathematicians who felt that actual infinity was unreasonable, even dangerous. So let’s agree and look toward infinity as an unending process.
More precisely we will consider an infinite set as represented by a generator. From time to time, the generator outputs a natural number. They need not come in order, elements can be repeated, but they generate natural numbers. Thus we could imagine a generator that outputs
This puts out the even numbers—do you see the pattern?
The property that we fix on for a generator 
The Diagonal Argument Again
Suppose that we have a collection 
Let’s assume that all the generators 
The construction of 
Stage
: Consider
. Suppose the current largest element in
is
. Wait until
. Then put
into
.
We claim that
Open Problems
I wonder about this generator argument. Could those who rejected infinite sets had found this argument years before the creation of set theory? Or does it need a notion of unbounded computational process that wasn’t talked about until the late 1800s anyway? What do you think?
Note, we could even allow the generators themselves to be generated one at a time; this would avoid any actual infinity.
Loved this bit in the Gauss quote: “[infinity] is never allowed in mathematics”. It occurs to me that a tremendous amount of important mathematics has been done by identifying things that people think are not allowed, and finding ways to make them allowed. Square roots of negative numbers. The Dirac delta function. Non-standard analysis. And many other examples.
“subsets of the natural numbers are uncountable” — gotta fix something in that sentence.
“had found this argument” -> “have found this argument”
Prefix with “set of all” to be completely clear, but the sentence read fine to me.
I wonder if it’s possible to use such a definition for building a functor from the category of sets to some complexity-theoretic category. I had been trying to do this when I first tried to settle the P vs NP question. My original idea was to deduce the undecidability of P != NP from that of the continuum hypothesis. Though I soon gave up that project, the idea of a functor from an abstract world to a concrete one still seems interesting.
A nice functorial correspondence would be one that sends sets of ℵ₀ cardinality to polynomial problems and sets of 2↑ℵ₀ cardinality to NP-complete ones. In case the continuum hypothesis is false – as the current research on this problem suggests – the sets of intermediate cardinality ℵ₁ would be sent to NP-intermediate problems. So, should such a miraculous functor exist, the continuum hypothesis would be proved equivalent to P=NP.
I don’t have a reference handy, but I believe it’s been proven that the continuum hypothesis has no effect on the provability of arithmetical statements, which includes P v NP. So this approach couldn’t work, unfortunately.
Thank you for your answer Luke. My own “too good to be true” heuristic approach leads me to the same conclusion. 🙂
My mistake, for the above “proof” only meant that P=NP implied CH. Even if those questions are technically disconnected from each other, such arguments sometimes work on an intuitive level.
Nothing much new here, and you don’t need “generators”. Just consider functions N -> 2. In ZF functions are encoded as sets of pairs of course, but if “generators” are not to be considered infinitary then neither should functions.
However, you will quickly run into problems of computability if you want to make anything serious of this.
Do you perhaps also want some more careful wording about generators of generators, to avoid the comprehension of the infinite set of generators {G_1, G_2, …}?
Sorry, I somehow missed reading the very last line of the post.
One interesting connection here is that what you’re describing as processes is often referenced in the functional programming community as “codata”, a term derived from “coinduction” which describes the generator itself. Coinduction is the standard technique for modeling divergent (or at least, non-obviously convergent) computations in strongly normalizing calculi. Not would processes have been more palatable than sets to Gauss, they are also more palatable than sets to modern functional purists. 🙂
What you proved is that for every r.e. collection of infinite r.e. sets there is in a uniform way a distinct infinite recursive set. Recursion theory was founded only many years after Cantor’s set theory. Though its concepts are elementary, more elementary than set theory, their formalization was apparently more remote. Gauss and Dedekind used intuitively notions of effectiveness, but never pinned them down to a formal computable process. In fact, it seems that the digression into set theory was a neccessay preparatory step for eventually coming up with Church’s thesis. Martin Davis pondered in 1982 the question of why Gödel didn’t have Churchs thesis. This is a bit tricky. Why Gauss did not, seems more easy to answer: The formal framework of mathematics was not sufficiently developed and available to him (the theorems proved in this framework could certainly also have been proved by Gauss or his contemporaries or even in the times of Eukild (who by the way had a notion of algorithm readily available)).
I was discussing the other day with someone, rather philosophically than mathematically, that there is no such thing as infinity in nature, speculating the fact that in engineering there is no such infinite process, while the only use for the mathematical concept of infinity is useful for studying limits of stuff. In short, something closer to what Gauss suggests. Although as I am not an engineer, but rather an enthusiast of mathematics, especially abstract algebra, I speculate more on infinity as a “necessary though unnatural” concept. Our capacity to perceive things “without ending”, like a line, or a plane, apart from viewing circularity as infinity, makes the concept of infinite as something that stands alone, disregarding the implications of a process that goes on and on. As I am a fan of constructivism and intuitionism, I tend to view mathematics in their manner. I would define infinity just like I define the concept of a set, solely by example, just because I need it. In my view, the infinity is older than mathematical analysis and set theory, by example the concept of line which holds an infinity of points. I would concentrate more on what practical necessity required the “construction” of infinity, and what other practical necessity has driven Gauss to protest against infinity as a complete quantity as he mentions.
For Gauss, the practical necessity was probably more psychological than anything else. He sought to preserve his consistent and powerful way of thinking without having to redo all the foundations. In general, success tends to make people more conservative – why change a winning team? But for Cantor, the practical necessity was certainly topological in the first place. He had to define some infinite subsets of the reals in order to carry out his studies on the convergence of trigonometric series. That’s why he was so eager to prove there was no intermediate cardinality between the integers and the reals. And as you know, in the end of his life he suffered from a mental disorder as a result. But one has to take risks sometimes…
The infinity is not yet completely understood into Mathematics, as we can see at http://www.andrebarbosa.eti.br/The_Size_of_the_Hilbert_Hotel_Computer.pdf, whereas its even stronger version is unavoidable if, for instance, we want to have an illusion from real randomness, as established in http://www.andrebarbosa.eti.br/The_Randomness_Delusion.pdf.
By different we mean that for each {G_{i}} there is some number {k} that {G_{i}} generates and {H} does not generate it.
Using that definition, the theorem is not true without the exclustion of generators of finite sets. Let {G_{n}} output {n,n,n,n,n…} then {G_{H_{1}}} does not gererate any number that {H} does not.
You introduce the exclusion of generators of finite sets as a simplifying assumption, but it is not. It is an essential precondition to the thoerem. “Feeble generators” are not trivial, they are the dificult case.
If you expand the deinition of different to include the case where {H} generates some number {k} that {G_{i}} does not, I think thoerem is true, but the proof is not as easy. You examime each {G_{i}} infinitely many times. On the {k}th visit output the least integer larger than any of the first {k} values of {G_{i}} and any prior values of {H}
Mathematicians in the semi-intuitionist school like Borel and Kronecker probably have thought about this. Talking to historians of mathematics like Penelope Maddy might help in finding more about the history of the argument.
What you refer to as generator is similar to what is called lawlike sequences in intuitionism.
We have defined two complexity classes which have a close relation with the notion of infinity.
The first one is:
We say that a language $L$ belongs to $UP_{\infty}$ if there exist an infinite sequence of languages $L_{1}, L_{2}, L_{3} \ldots$ where for each $i \in \mathbb{N}$ every language $L_{i}$ is in $UP$, has an infinite cardinality, the set $L_{i + 1} – L_{i}$ has infinite elements and $L_{i} \subset L_{i + 1}$ such that
\[\lim_{i \rightarrow \infty} L_{i} = L.\]
We call the complexity class $UP_{\infty}$ as $\textit{“infinite–UP”}$.
The second one:
We say that a language $L$ belongs to $P_{\infty}$ if there exist an infinite sequence of languages $L_{1}, L_{2}, L_{3} \ldots$ where for each $i \in \mathbb{N}$ every language $L_{i}$ is in $P$, has an infinite cardinality, the set $L_{i + 1} – L_{i}$ has infinite elements and $L_{i} \subset L_{i + 1}$ such that
\[\lim_{i \rightarrow \infty} L_{i} = L.\]
We call the complexity class $P_{\infty}$ as $\textit{“infinite–P”}$.
We have the result:
We define a problem that we call General Quadratic Congruences. We show General Quadratic Congruences is an $\textit{NP–complete}$ problem. Moreover, we prove General Quadratic Congruences is also in $\textit{infinite–UP}$. In addition, we define another problem that we call Simple Subset Product. We show Simple Subset Product is an $\textit{NP–complete}$ problem. Furthermore, we prove Simple Subset Product is also in $\textit{infinite–P}$.
My question is:
Can these properties of the NP-complete problems help us to understand better the P versus NP problem?
Let me know your answer, please…
At the same time, if you are interested in the proof of the result take a look in:
https://hal.archives-ouvertes.fr/hal-01490777v2/document
Thanks in advance…
In the previous comment the defined problems General Quadratic Congruences and Simple Subset Product are:
First problem:
$\textit{GENERAL QUADRATIC CONGRUENCES}$
INSTANCE: Positive integers $a$, $b$, $c$ and $d$, such that we have the prime factorization of $b$.
QUESTION: Is there a positive integer $x$ such that $x < c$ and $d \times x^{2} \equiv a (\mod b)$?
We denote this problem as $GQC$.
Second problem:
$\textit{SIMPLE SUBSET PRODUCT}$
INSTANCE: A list of numbers $L$ and a positive integer $k$ with its prime factorization, such that the prime factorization of $k$ does not contain any prime power with exponent greater than $1$.
QUESTION: Is there a subset of numbers from $L$ whose product is $k$?
We denote this problem as $SSP$.
Maybe you are interested to answer this question in:
http://cs.stackexchange.com/questions/71909/is-valid-the-notion-of-infinity-for-the-np-complete-problems
I hope this could sound interesting…