1. Introduction
Constructive mathematics deals with strict use of constructive proofs and axioms which are used to form more intricate proofs. Contrary to classical mathematics, which seeks to prove theorems and conjectures without generally considering its complement, constructive mathematics requires mathematicians to not only use a certain way of thinking to formulate a path to the proof but also create certain assumptions that make sense among them (thus the existence of axioms). Instead of dealing with abstract ideas, this area of mathematics utilizes intuitive, mathematical understanding to make a better sense of our world.
Proofs in constructive mathematics include systematic processes that can be used to support the validity of its arguments in a realistic way. This algorithmic way of thinking enables mathematicians to not utterly reject past proofs but to reconsider them in a different point of view. Constructive mathematics is popular within the realms of computer science where algorithms and logical thinking is crucial to its development.
The US school of mathematics was founded by Bishop[1] and the Russian school of mathematics was founded by Markov and Shanin. While these schools studied constructive mathematics, each school have different rules and guidelines for forming proofs and ideas. One example of such relates to Markov’s principle[2], which states that if the inapplicability of an algorithm U to some input x has been refuted, then the algorithm is applicable to that input x. The Russian school permitted the use of Markov’s principle, also known as constructive choice, which sometimes allows mathematicians to argue by contradiction. On the other hand, the US school generally does not accept Markov’s principle, with one reason being that it does not tell how long it would take for an algorithm to terminate successfully given some inputs.
A Constructive Sequence of Rational Numbers (CSRN) is an algorithm that transforms every natural number into its respective rational number. Constructive Real Numbers can be defined as a set of two programs: A computer-generated Cauchy sequence of numbers and a convergence regulator, which ensures the convergence of the sequence of numbers. The reason that we have the convergence regulator is because we can never truly predict what the next values of the Cauchy sequence will be, which is like how we can never know whether a flipped coin will be heads or tails despite the preconceived knowledge that the theoretical chance is 50 percent for each outcome. Therefore, the convergence regulator is used to ensure the predictability of the values of the generated Cauchy sequence. A constructive separable metric space is defined as a set of points where the distances between them can be described as a constructive real number within a topological space.
This research explores the ideas of boundaries and open sets while applying the knowledge of undecidability, topological spaces, and mathematical programs. Our general approach to proving whether a given point is outside or on its boundary is to find the undecidability of such program, meaning that it realistically cannot halt in a finite amount of time. Building on the ideas that Alan Turing had developed in 1936, we construct such theoretical program and test whether it can uphold the presented conditions.
2. Definition
Computable function: A function 𝑓 with natural arguments and values is called computable if there exists an algorithm that computes𝑓, that is, an algorithm 𝐴 such that[3]:
If 𝑓(𝑛) is defined for a certain natural 𝑛, then the algorithm 𝐴 halts on the input 𝑛 and prints 𝑓(𝑛)
If 𝑓(𝑛) is undefined, then the algorithm 𝐴 does not halt on the input 𝑛.
Decidability: A set 𝑋 of natural numbers is called decidable if there exists an algorithm that determines whether an arbitrarily given natural number n belongs to the set 𝑋. Such an algorithm must terminate for any 𝑛 and give one of the two answers “yes” or “no”.
Topology: A family 𝜉 of sets where the intersection of any two members of 𝜉 is a member of 𝜉 and the union of any collection of members of 𝜉 is a member of 𝜉.
Union of the collection of the member sets is a member of 𝜉.
Intersection of finitely many elements of 𝜉 is a member of 𝜉.
Empty set and the whole space are members of 𝜉.
Topological space: Defined as a pair (𝑋, 𝜉) where 𝜉 is a topology for set 𝑋.
Closed set: A subset 𝐴 of a topological space (𝑋, 𝜉) is closed if and only if its relative complement 𝑋\𝐴 is open, implying that a set is open if and only if its complement is closed[4].
Open set: A subset 𝐴 of X of a topological space (𝑋, 𝜉) is an open set of 𝑋 if and only if 𝐴 belongs to X.
Neighborhood: The neighborhood of a point is an open set containing it.
Interior point: A point 𝑥 of a subset 𝐴 of a topological space is an interior point of 𝐴 if and only if there is an open subset of A containing x. The set of all interior points of 𝐴 is the interior of 𝐴, denoted 𝐴°
Boundary: The boundary of subset 𝐴 of a topological space 𝑋 is the set of all points x which are interior to neither 𝐴 nor 𝑋 ~ 𝐴.
Exterior: The exterior of a set 𝐵, denoted by 𝐸𝑥𝑡 𝐵, is the interior of the complement of the set 𝐵.
3. Main theorem
For a General Constructive Topological space and a closed set S in it and a point 𝑝, it is not possible to algorithmically tell if the point 𝑝 is in the exterior of S or on the boundary.
3.1. Construction of algorithm Y and X
We let Y be an unextendible algorithm where it cannot necessarily cover all integer inputs and we first assume that this algorithm certainly exists. The fact that this algorithm is unextendible implies that the domain of this program is undecidable, meaning that there exists no algorithm such that it can make decisions through this domain.
We also let X be an algorithm such that it has domain Z. For every second, this algorithm will produce a closed set Fs, where s is the respective second that the closed set was produced from. Throughout the run of this algorithm, we will define Fs depending on whether Y(n) had stopped. We also define the number of seconds passed as t and choose the number 1 as an arbitrary number for this proof (though any number could be chosen like 0).
Construction of our program:
Let us run program Y:
1.If algorithm Y(n) did not stop at t seconds, then let Fs = [1, s + 1], (s < t)
2.If algorithm Y(n) does stop at t seconds, then let Fs be:
a.[1.5, s+1] for (s ≥ t)
b.[1, s + 1] for (s < t)
Let us concurrently run X:
1.If X detects program Y as never terminating, then X will return the intersection of the sets that are outputted so far: ([1, 2] ∩ [1, 3] ∩ [1, 4] ∩ … ∩ [1, t])
2If X detects program Y as terminated, then X will return the intersection of the sets that are outputted by Y: [1, 2] ∩ [1, 3] ∩ [1, 4] ∩ … ∩ [1, t] ∩ [1.5, 2] ∩ [1.5, 3] …
Given the executions of these two programs we can deduce that:
If Y never stops, then ∩ts=1 Fs = [1, 2]
If Y stops at some point, then ∩ts=1 Fs = [1.5, 2]
Note: these intersections done above are closed sets since intersection of closed sets are closed.
Therefore, by definition, our arbitrary number 1 is on the boundary of [1, 2] and exterior of [1.5, 2]. We can say that if the program never stops, then our arbitrary number 1 is on the boundary of the intersection generated by X, and if the program stops, then the arbitrary number is on the exterior (namely, not part of the set) of the set generated by X.
3.2. Proof of our final result
In this section, we employ a reductio ad absurdum argument to establish the nonexistence of the algorithm A(S, p), which purportedly determines whether a point p lies on the boundary or in the exterior of a closed set S .
To illustrate the contradiction inherent in this assumption, we consider the previously defined algorithms Y and X. The algorithm Y operates on integer inputs and is characterized as unextendible, while the algorithm X concurrently generates closed sets based on the behavior of Y. Specifically, we define the closed sets produced by X as follows:
1. If Y(n) does not terminate after t seconds, then X will return the intersection of the sets generated up to that point: ∩ts=1[1, s + 1] = [1, 2].
2. Conversely, if Y(n) terminates at t seconds, then X will return the intersection of the sets generated by Y up to that moment: ∩ts=1[1, s + 1] ∩ ∩∞s=t+1[1.5, s + 1] = [1.5, 2].
Thus, we arrive at two distinct scenarios based on the behavior of Y:
- In the case where Y does not halt, the intersection yields [1, 2].
- In the event that Y halts, the intersection yields [1.5, 2].
It is noteworthy that these intersections are closed sets, as the intersection of closed sets remains closed. Consequently, we can deduce that if Y does not terminate, the point 1 is situated on the boundary of the set [1, 2]. Conversely, if Y does terminate, the point 1 resides in the exterior of the set [1.5, 2].
This leads us to a contradiction: if the algorithm A(S, p) were to exist, it would imply a consistent method to ascertain the position of p relative to the closed set S. However, our construction demonstrates that the behavior of Y engenders an undecidable scenario, thereby proving that no such algorithm A(S, p) can exist.
4. Conclusion
This paper has rigorously established the nonexistence of a universal algorithm capable of determining whether a point lies on the boundary or in the exterior of a closed set within the framework of constructive separable metric spaces. A constructive separable metric space is defined as an algorithmically given set of points with the distances between them being computable real numbers (CRNs) and with a countable, algorithmically given topological base. Importantly, the real line of constructive real numbers serves as an example of such a space.
Building on the undecidability of the Halting Problem[5,6] , we have shown that for a vast class of constructive separable topological metric spaces[7], including the real line of constructive real numbers, it is not possible to algorithmically determine whether a given point is on the boundary of a set or in its exterior. This finding underscores the profound connections between computability theory and topology, particularly within the realm of constructive mathematics.
Moreover, while there may be specific subclasses of closed constructive sets where algorithmic methods are effective[8], this study concludes that such methods cannot be universally applied. The inherent undecidability of these problems invites further theoretical exploration into the boundaries of computability in this context, potentially leading to the development of more advanced frameworks or identifying conditions that allow for decidable cases.
Acknowledgment
We sincerely express our thanks to Viktor Chernov and Vladimir Chernov who formulated this problem and to Neoscholar company for organizing the summer program where the problem was studied.
References
[1]. E. Bishop, D. Bridges: Constructive analysis Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 279 Springer-Verlag, Berlin (1985)[1,5]
[2]. B. A. Kushner: Lectures on constructive mathematical analysis (in Russian) Monographs in Mathematical Logic and Foundations of Mathematics. Iz- dat. “Nauka”, Moscow, 1973. 447 pp., English translation in Translations of Mathematical Monographs, 60 American Mathematical Society, Providence. [2]
[3]. Shen, A., and Nikolai Konstantinovich Vereshchagin. Computable Functions. American Mathematical Society, 2003. [3]
[4]. Kelly, John L. General Topology John L. Kelly. Springer, 1975. [4]
[5]. A. M. Turing: Corrections, Proc. Lond. Math. Soc., ser. 2, 43 (1937), 544-546 [5]
[6]. E. Bishop, D. Bridges: Constructive analysis Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 279 Springer-Verlag, Berlin (1985)
[7]. N. A. Sanin (Shanin): Constructive real numbers and constructive functional spaces (in Russian) Trudy Mat. Inst. Steklov 67 (1962) 15–294. English translation in Amer. Math. Soc., Providence R.I. (1968) [6]
[8]. N. Vereshchagin & A. Shen: Algorithms and randomness. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (1999), pp. 12–21. IEEE. [7]
Cite this article
Fan,J.;Li,J. (2025). Proof of the Nonexistence of an Algorithm That Tells If a Point Is on a Closed Set’s Boundary or Exterior. Theoretical and Natural Science,108,88-91.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 4th International Conference on Computing Innovation and Applied Physics
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).
References
[1]. E. Bishop, D. Bridges: Constructive analysis Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 279 Springer-Verlag, Berlin (1985)[1,5]
[2]. B. A. Kushner: Lectures on constructive mathematical analysis (in Russian) Monographs in Mathematical Logic and Foundations of Mathematics. Iz- dat. “Nauka”, Moscow, 1973. 447 pp., English translation in Translations of Mathematical Monographs, 60 American Mathematical Society, Providence. [2]
[3]. Shen, A., and Nikolai Konstantinovich Vereshchagin. Computable Functions. American Mathematical Society, 2003. [3]
[4]. Kelly, John L. General Topology John L. Kelly. Springer, 1975. [4]
[5]. A. M. Turing: Corrections, Proc. Lond. Math. Soc., ser. 2, 43 (1937), 544-546 [5]
[6]. E. Bishop, D. Bridges: Constructive analysis Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 279 Springer-Verlag, Berlin (1985)
[7]. N. A. Sanin (Shanin): Constructive real numbers and constructive functional spaces (in Russian) Trudy Mat. Inst. Steklov 67 (1962) 15–294. English translation in Amer. Math. Soc., Providence R.I. (1968) [6]
[8]. N. Vereshchagin & A. Shen: Algorithms and randomness. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (1999), pp. 12–21. IEEE. [7]