1. Introduction
The concept of a trivial set is fundamental in topology and set theory. It is the base for many theorems such as the Zermelo-Fraenkel Set Theory. In classical topology, various techniques and theorems allow our research group to unravel and compute fundamental groups for various spaces. However, when considering constructive mathematics, where the existence of a concept requires the construction of a corresponding algorithm, the tools become significantly limited. This paper focuses on the triviality of fundamental groups of constructive compact topological spaces and will further explore the existence of computer algorithms mentioned above.
2. Definition
Definition 1 (Metric Space). Let (X, d) be an ordered pair of a set X, which is the basic formation of metric space. A metric function \( d:X×X→R \) satisfies the axioms below for arbitrary \( x,y,z∈X \) :
1. d(x, y) equals to zero precisely when x = y;
2. d(x, y) equals to d(y, x), and note that their values are both non-negative;
3. d(x, z) ≤ d(x, y) + d(y, z), which satisfies the so alleged Triangular Inequality.
4. Definition 2 (Homotopy). Given 2 continuous maps \( f and g: X ↦Y \) continuous \( H:X×[0,1]↦Y \) is called a homotopy between \( f \) and g if \( H(x,0)=f(x) \) while \( H(x,1)=g(x) \) .
Definition 3 (Fundamental Group). A fundamental group, denoted as \( {π_{1}}(x), \) of a manifold(specifically, topological space) is a group of equivalence classes of based loops in basis X considering homotopy.
Definition 4 (ϵ-net). Let M = (X, d) be a metric space, thus we pick \( ϵ∈{R^{+}} \) . Accordingly, an \( ϵ \) - net for M, denoted Nϵ, is a set of vertices S ∈ X that satisfies \( X⊆\bigcup _{x∈S}B(x,ϵ) \) , where B(x, ϵ) represents the open ball of x with a radius \( ϵ \) in M.
Definition 5 (Closure). The closure of a subset \( S⊂X \) a topological space X, denoted \( \bar{ S} \) , is an intersection of all closed subsets of X that contain S, i.e. \( \bigcap _{S⊆C}C \) where C is closed in X.
Definition 6 (Interior). The interior of \( S⊂X ( \) denoted as \( int(S) \) ), a subset of a topological space X, is the union of all open subsets of X that are contained in S, i.e. \( \bigcup _{O⊆S}O \) where O is open in X.
Definition 7 (Boundary). The boundary of a subset \( S⊂X \) in a topological space X
is the closure of S minus the interior of S, i.e. \( \bar{ S}∖int(S) \) .
Definition 8 (Constructive Compact Topology Space). A Constructive Compact Topological space is the collection of algorithmically generated epsilon nets for all rational epsilons. One can think of the resulting set as the closure of the union of the epsilon nets described above.
Definition 9 (Deformation Retract). Given an abstract topological space X and its subset \( S⊂X \) , S is a deformation retract of X if there is a retraction r: \( X↦S \) , i.e. r restricted to S is the identity map idS, and that r is homotopic to idX when r is viewed as a map from X into itself.
Definition 10 (Turing Machines). A Turing machine is a conceptual machine proposed by Turing. Its memory is stored in an infinite tape. Beginning with an input, the tape is surrounded by infinitely many blank cells, which keeps on running until it halts.
Definition 11 (Halting problem). Representing one of the decision problems in computability theory, the halting problem questions if a given Turing machine T will be eventually capable of halting (stopping running) when offered a specific input or keep on executing indefinitely. As early as 1936, such a problem was studied by Alan Turing that no universal algorithm can crack the halting problem for every feasible Turing machines and inputs [1,2].
3. Literature review
There are two main schools of constructive analysis [3]. A A. Markov Jr., as introduced in Kushner’s 1966 paper has made great contributions to constructive mathematics and was the representative for one of those schools [4]. In this paper, Kushner outlines the main features of Markov’s constructive mathematics (MCM), emphasizing the study of constructive processes and objects, the use of a special constructive logic, and the rejection of actual infinity in favor of potential realizability [4]. He also compares Markov’s approach with Bishop’s Constructivism and Brouwer’s Intuitionism and concludes that Markov’s focus on algorithms and computability distinguished his work from others [4]. Other works from Markov include the Markov Algorithm in theoretical computer science and the proof for undecidability of an algorithm that determines if two given polyhedra are Homeomorphic [5]. Despite works from Markov, we have also reviewed works from American mathematician - Errett Bishop. In his 1967 book and a later revision, Bishop not only aimed to provide proofs of important theory but also proved to other mathematicians like Hermann Weyl, that a constructive approach is feasible also for real analysis [6,7].
Other works we have reviewed include Kushner’s [8] textbook on constructive mathematical analysis which provides a general overview of important concepts in constructive mathematics. Waaldijk [9] links constructive mathematics with recursive mathematics and intuitionism and provides new definitions, such as that of” locally compact,” which align more closely with classical and intuitionistic mathematics. Poincaré’s work, originally published in 1895 and compiled in” Papers on Topology” [10], laid the groundwork for the concept of the fundamental group, which has become a crucial tool in algebraic topology. The initial version of algebraic topology by Poincaré is characterized by the fact that topological concepts can be expressed and interpreted through algebratic relations and operations, which fosters an impressive integration of Geometry and Algebra. [10]. This concept connects algebra with the topology of spaces, allowing for the classification of topological spaces based on their properties under continuous transformations.
The halting problem is a central topic in the theory of computation and this research project. Turing’s seminal 1937 paper established the definition of Turing Machines and proved the undecidability of the halting problem, which remains a foundational result in computability theory [1,2]. Studies like those by Bienvenu et al.[11] and Köhler et al. [12] explore the possibility of solving the halting problem for “most” inputs, despite its undecidability, discussing optimal machines and approximations within real-world programming languages.
The literature covers a broad spectrum from the theoretical underpinnings of computability with Turing Machines and the halting problem to the foundations of constructive mathematics and algebraic topology. These works collectively contribute to a deeper understanding of the limitations and possibilities within mathematics and computation.
To explore the limitations and possibilities of solving topological problems via theoretical computation methods, we plug in a canonical problem on the computation of the fundamental group of a given set, unveiling the thinking process in a computer’s” brain”. By employing computational methods like Turing machine and ϵ-net to grind the problem, we finally reveal that it is impossible (with today’s computational methods) to solve our problem. This result points out that we should develop another computational method of thinking in a different way to be capable of solving topological problems related to fundamental groups. With modern computational methods, we are only capable of seeing the tip of the island of Topology World. Still, it can be a promising assistant tool for us to explore topology problems.
4. Main theorem and Its proof
4.1. Theorem
There is no decision program that, given a constructive compact topological space K, can always determine whether \( {π_{1}}(K) \) is trivial or not.
4.2. Proof
For the sake of contradiction, assume that we ha a decision program D, that given any computer program that generates a constructive compact topological space K, can determine whether π1(K) is trivial.
Let G denote the computer program that generates a metric subspace inside. B = [0, 1]2 ⊂ \( {R^{2}} \) for our decision program to determine. Since a computer program is finite, it can be fed as a proper input to decision algorithm D.
Start executing arbitrary Turing machine \( T \) with input 0 for 1 second per iteration, after iteration \( n \) , \( G \) does the following:
If \( T \) does not halt after iteration n,
\( K \) = \( \overline{\bigcup _{i≤n}{N_{\frac{1}{{2^{i}}}}}} \) ,
where we take \( {N_{\frac{1}{{2^{i}}}}}=\lbrace (\frac{p}{{2^{i}}},\frac{q}{{2^{i}}})∣0≤p,q≤{2^{i}}\rbrace \) . ( \( p \) , \( q \) non-negative integers).
That is, \( K=\overline{\bigcup _{i≤n}\lbrace (\frac{p}{{2^{i}}},\frac{q}{{2^{i}}})∣0≤p,q≤{2^{i}}\rbrace } \) ,
Observe that \( \overline{\bigcup _{n∈N}{N_{\frac{1}{{2^{n}}}}}}={[0,1]^{2}} \) since the union set is dense in \( {[0,1]^{2}} \) . So when \( T \) never halts, \( K \) = \( {[0,1]^{2}} \) , which has a trivial fundamental group (due to linear homotopy).
If \( T \) has halted after n seconds, if this is the first iteration after which \( T \) has halted, adopt and fix \( {B^{ \prime }}=B∖{(0,\frac{1}{{2^{n}}})^{2}} \) , and denote this n as n’. That is, after this point all \( {N_{ϵ}} \) are taken in \( {B^{ \prime }} \) instead of \( B \) for all future iterations. Note all the previous \( n-1 ϵ \) -nets, when viewed as subsets of \( {B^{ \prime }} \) , also satisfy the conditions that the \( ϵ \) balls with the vertices as centers cover \( {B^{ \prime }} \) hence they are also \( ϵ-nets of B \prime \) for \( ϵ≥1/{2^{n}} \) .
Take \( K=\overline{\bigcup _{i≤n}{N_{\frac{1}{{2^{i}}}}}} \) , , where
\( {N_{\frac{1}{{2^{i}}}}}=\lbrace (\frac{p}{{2^{i}}},\frac{q}{{2^{i}}})∣0≤p,q≤{2^{i}} and (\frac{p}{{2^{i}}},\frac{q}{{2^{i}}})∈{B^{ \prime }}\rbrace \)
That is \( K=\overline{\bigcup _{i≤n}\lbrace (\frac{p}{{2^{i}}},\frac{q}{{2^{i}}})∣0≤p,q≤{2^{i}} and (\frac{p}{{2^{i}}},\frac{q}{{2^{i}}})∈{B^{ \prime }}\rbrace } \)
In the halting case, the union set is also dense in \( {B^{ \prime }} \) , which is simply a solid square but without the part \( {(0,\frac{1}{{2^{n \prime }}})^{2}} \) , Hence \( K={B^{ \prime }} \) . Note the hollow square of side length \( \frac{1}{{2^{n \prime }}} \) , that is the boundary of \( {[0,\frac{1}{{2^{n \prime }}}]^{2}} \) which resides inside of B' is a deformation retract of \( {B^{ \prime }} \) in an obvious way: for each \( b∈{B^{ \prime }} \) , shrink it, in a continuous fashion towards \( (0,0) \) along the straight line connecting \( (0,0) \) and \( b \) until getting to the desired hollow square. Since fundamental groups of a topological space and its deformation retract are isomorphic, \( {π_{1}}(K) \) is isomorphic to the fundamental group of the hollow square (homeomorphic to \( {S^{1}} \) ), which is isomorphic to \( (Z,+) \) .
Now \( G \) is defined in a way such that the resultant space it generates has a fundamental group which is trivial precisely when \( T \) belongs to non-halting case. Thus \( D \) also serves as a decision problem for the halting problem for arbitrary Turing Machine \( T \) , contradicting that the halting set is undecidable. So such \( D \) cannot possibly exist.
5. Conclusion
A generating program is constructed in our study in such a way that effectively relates the halting problem to deciding whether the fundamental group of a constructive compact topological space is trivial, showing that such a decision program for our problem cannot possibly exist. In fact, through similar constructions, the undecidability of other properties about the fundamental group of a constructive compact topological space can be concluded as well.
One such property would be the presentation of the fundamental group. If we puncture n hollow squares in the interior of the original square and proceed on the remaining space, the resultant space would have a deformation retract of a wedge of n squares, which would have a fundamental group of free products of n copies of (Z, +). Note both (Z, +) and the trivial group have only one generator, but such a free product has more than one generator. This would allow us to conclude that there is no decision program for telling whether the fundamental group of a constructive compact topological space has more than one generator.
By exploring the existence and limitations of these algorithms, this research contributes to a deeper understanding of the computational aspects of topology and set theory. It also provides a foundation for future studies that seek to develop or refine algorithms capable of operating within the constraints of constructive mathematics, thereby expanding the scope and applicability of these mathematical frameworks.
Acknowledgement
We would like to express our deepest gratitude to Dr. Viktor Chernov who jointly with Vladimir Chernov created this problem. We also thank the Neoscholar company that organized this research program.
References
[1]. Turing, A. (1937). On computable numbers, with an application to the entscheidungs problem. Proceedings of the London Mathematical Society, s2-42(1).
[2]. Turing, A. (1938). On computable numbers, with an application to the entscheidungsproblem. a correction. Proceedings of the London Mathematical Society, s2-43(1).
[3]. Troelstra, A. (1977). Aspects of constructive mathematics. Studies in Logic and the Foundations of Mathematics.
[4]. Kushner, B. A. (1996). Kurt Gödel and the constructive mathematics of A.A. Markov. Lecture Notes in Logic, 50–63.
[5]. Markov, A., German, C., and Herken, R. (1958). Insolubility of the problem of homeomorphy.
[6]. Bishop, E, and Bridges, D. S. (1967). Constructive Analysis. Springer.
[7]. Bishop, E., & Beeson, M. (2013). Foundations of constructive analysis. Ishi Press International.
[8]. Kushner, B. A. (1984). Lectures on constructive mathematical analysis. London Mathematical Society.
[9]. Waaldijk, F. (2005). On the foundations of constructive mathematics – especially in relation to the theory of continuous functions. Foundations of Science, 10(3).
[10]. Poincare, H. (2010). Papers on topology: Analysis situs and its five supplements. American Mathematical Society; London Mathematical Society.
[11]. Bienvenu, L., D. D. . S. A. (2016). Generic algorithms for halting problem and optimal machines revisited. Logical Methods in Computer Science, 12(2).
[12]. Köhler, S., S. C. . Z. M. (2005). On approximating real-world halting problems. Lecture Notes in Computer Science.
Cite this article
Jin,E.;Li,Y.;Qian,X.;Yao,K.;Yu,S. (2025). Nonexistence of Algorithm Deciding if the Fundamental Group of an Arbitrary Constructive Compact Set is Trivial. Theoretical and Natural Science,108,38-42.
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]. Turing, A. (1937). On computable numbers, with an application to the entscheidungs problem. Proceedings of the London Mathematical Society, s2-42(1).
[2]. Turing, A. (1938). On computable numbers, with an application to the entscheidungsproblem. a correction. Proceedings of the London Mathematical Society, s2-43(1).
[3]. Troelstra, A. (1977). Aspects of constructive mathematics. Studies in Logic and the Foundations of Mathematics.
[4]. Kushner, B. A. (1996). Kurt Gödel and the constructive mathematics of A.A. Markov. Lecture Notes in Logic, 50–63.
[5]. Markov, A., German, C., and Herken, R. (1958). Insolubility of the problem of homeomorphy.
[6]. Bishop, E, and Bridges, D. S. (1967). Constructive Analysis. Springer.
[7]. Bishop, E., & Beeson, M. (2013). Foundations of constructive analysis. Ishi Press International.
[8]. Kushner, B. A. (1984). Lectures on constructive mathematical analysis. London Mathematical Society.
[9]. Waaldijk, F. (2005). On the foundations of constructive mathematics – especially in relation to the theory of continuous functions. Foundations of Science, 10(3).
[10]. Poincare, H. (2010). Papers on topology: Analysis situs and its five supplements. American Mathematical Society; London Mathematical Society.
[11]. Bienvenu, L., D. D. . S. A. (2016). Generic algorithms for halting problem and optimal machines revisited. Logical Methods in Computer Science, 12(2).
[12]. Köhler, S., S. C. . Z. M. (2005). On approximating real-world halting problems. Lecture Notes in Computer Science.