We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko [19] et al. Although this definition of TIME as the maximum of a generally infinite family of numbers looks straightforward, at first glance, examples for which this maximum exists seem to be very rare. It is the main purpose of this paper to prove that, (...) nevertheless, the definition has a large number of important applications. Using the framework of TTE [40], we introduce computable metric spaces and computability on the compact subsets. We prove that every computable metric space has a c-proper c-admissible representation. We prove that Turing machine time complexity of a function computable relative to c-admissible c-proper representations has a computable bound on every computable compact subset. We prove that computably compact computable metric spaces have concise c-proper c-admissible representations and show by examples that many canonical representations are of this kind. Finally, we compare our definition with a similar one by Labhalla et al. [22]. Several examples illustrate the concepts. By these results natural and realistic definitions of computational complexity are now available for a variety of numerical problems such as image processing, integration, continuous Fourier transform or wave propagation. (shrink)

We give a systematic technical exposition of the foundations of the theory of computably compact metric spaces. We discover several new characterizations of computable compactness and apply these characterizations to prove new results in computable analysis and effective topology. We also apply the technique of computable compactness to give new and less combinatorially involved proofs of known results from the literature. Some of these results do not have computable compactness or compact spaces in their statements, (...) and thus these applications are not necessarily direct or expected. (shrink)

Computability theoretic aspects of Polish metric spaces are studied by adapting notions and methods of computable structure theory. In this dissertation, we mainly investigate index sets and classification problems for computably presentable Polish metric spaces. We find the complexity of a number of index sets, isomorphism problems, and embedding problems for computably presentable metric spaces. We also provide several computable structure theory results related to some classical Polish metric spaces such as the Urysohn (...) class='Hi'>space $\mathbb {U}$, the Cantor space $2^{\mathbb {N}}$, the Baire space $\mathbb {N}^{\mathbb {N}}$, and spaces of continuous functions.Abstract prepared by Teerawat Thewmorakot.E-mail: [email protected]. (shrink)

In this paper we give an axiomatisation of the concept of a computability structure with partial sequences on a many-sorted metric partial algebra, thus extending the axiomatisation given by Pour-El and Richards in [9] for Banach spaces. We show that every Banach-Mazur computable partial function from an effectively separable computable metric partial Σ-algebra A to a computable metric partial Σ-algebra B must be continuous, and conversely, that every effectively continuous partial function with semidecidable domain (...) and which preserves the computability of a computably enumerable dense set must be computable. Finally, as an application of these results we give an alternative proof of the first main theorem for Banach spaces first proved by Pour-El and Richards. (shrink)

In [14], we studied the computational behaviour of various first-order and modal languages interpreted in metric or weaker distance spaces. [13] gave an axiomatisation of an expressive and decidable metric logic. The main result of this paper is in showing that the technique of representing metric spaces by means of Kripke frames can be extended to cover the modal (hybrid) language that is expressively complete over metric spaces for the (undecidable) two-variable fragment of first-order logic with (...) binary pred-icates interpreting the metric. The frame conditions needed correspond rather directly with a Boolean modal logic that is, again, of the same expressivity as the two-variable fragment. We use this representation to derive an axiomatisation of the modal hybrid variant of the two-variable fragment, discuss the compactness property in distance logics, and derive some results on (the failure of) interpolation in distance logics of various expressive power. (shrink)

Lexical ambiguity is pervasive in language, and the nature of the representations of an ambiguous word's multiple meanings is yet to be fully understood. With a special focus on Chinese characters, the present study first established that native speaker's perception about a character's number of meanings was heavily influenced by the availability of its distinct word formations, while whether these meanings would be perceived to be closely related was driven by further conceptual analysis. These notions were operationalized as two computed (...) metrics, which assessed the degree of dispersion across individual word formations and the degree of propinquity across clusters of word formations, respectively, in a distributional semantic space. The observed correlations between the computed and the perceived metrics indicated that the utility of word formations to tap into meaning representations of Chinese characters was indeed cognitively plausible. The results have demonstrated the extent to which distributional semantics could inform about meaning representations of Chinese characters, which has theoretical implications for the representation of ambiguous words more generally. (shrink)

If [Formula: see text] is a proper Polish metric space and [Formula: see text] is any countable dense submetric space of [Formula: see text], then the Scott rank of [Formula: see text] in the natural first-order language of metric spaces is countable and in fact at most [Formula: see text], where [Formula: see text] is the Church–Kleene ordinal of [Formula: see text] which is the least ordinal with no presentation on [Formula: see text] computable from (...) [Formula: see text]. If [Formula: see text] is a rigid Polish metric space and [Formula: see text] is any countable dense submetric space, then the Scott rank of [Formula: see text] is countable and in fact less than [Formula: see text]. (shrink)

We examine conditions under which, in a computable topological space, a semicomputable set is computable. It is known that in a computable metric space a semicomputable set S is computable if S is a continuum chainable from a to b, where a and b are computable points, or S is a circularly chainable continuum which is not chainable. We prove that this result holds in any computable topological space.

We consider how to represent the measurable sets in an infinite measure space. We use sequences of simple measurable sets converging under metrics to represent general measurable sets. Then we study the computability of the measure and the set operators of measurable sets with respect to such representations.

In this paper we give an axiomatisation of the concept of a computability structure with partial sequences on a many‐sorted metric partial algebra, thus extending the axiomatisation given by Pour‐El and Richards in [9] for Banach spaces. We show that every Banach‐Mazur computable partial function from an effectively separable computable metric partial Σ‐algebraAto a computable metric partial Σ‐algebraBmust be continuous, and conversely, that every effectively continuous partial function with semidecidable domain and which preserves the (...) computability of a computably enumerable dense set must be computable. Finally, as an application of these results we give an alternative proof of the first main theorem for Banach spaces first proved by Pour‐El and Richards. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space (...) of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form [Formula: see text] where [Formula: see text] is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, [Formula: see text], and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance [Formula: see text] from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic. Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics. (shrink)

We analyse the connection between the computability and continuity of functions in the case of homomorphisms between topological algebraic structures. Inspired by the Pour-El and Richards equivalence theorem between computability and boundedness for closed linear operators on Banach spaces, we study the rather general situation of partial homomorphisms between metric partial universal algebras. First, we develop a set of basic notions and results that reveal some of the delicate algebraic, topological and effective properties of partial algebras. Our main computability (...) concepts are based on numerations and include those of effective metric partial algebras and effective partial homomorphisms. We prove a general equivalence theorem that includes a version of the Pour-El and Richards Theorem, and has other applications. Finally, the Pour-El and Richards axioms for computable sequence structures on Banach spaces are generalised to computable partial sequence structures on metric algebras, and we prove their equivalence with our computability model based on numerations. (shrink)

We analyse the connection between the computability and continuity of functions in the case of homomorphisms between topological algebraic structures. Inspired by the Pour-El and Richards equivalence theorem between computability and boundedness for closed linear operators on Banach spaces, we study the rather general situation of partial homomorphisms between metric partial universal algebras. First, we develop a set of basic notions and results that reveal some of the delicate algebraic, topological and effective properties of partial algebras. Our main computability (...) concepts are based on numerations and include those of effective metric partial algebras and effective partial homomorphisms. We prove a general equivalence theorem that includes a version of the Pour-El and Richards Theorem, and has other applications. Finally, the Pour-El and Richards axioms for computable sequence structures on Banach spaces are generalised to computable partial sequence structures on metric algebras, and we prove their equivalence with our computability model based on numerations. (shrink)

In this paper we study intrinsic notions of “computability” for open and closed subsets of Euclidean space. Here we combine together the two concepts, computability on abstract metric spaces and computability for continuous functions, and delineate the basic properties of computable open and closed sets. The paper concludes with a comprehensive examination of the Effective Riemann Mapping Theorem and related questions.

Every second-countable regular topological space X is metrizable. For a given “computable” topological space satisfying an axiom of computable regularity M. Schröder [10] has constructed a computable metric. In this article we study whether this metric space can be considered computationally as a subspace of some computable metric space [15]. While Schröder's construction is “pointless”, i. e., only sets of a countable base but no concrete points are known, for (...) a computable metric space a concrete dense set of computable points is needed. But there may be no computable points in X. By converging sequences of basis sets instead of Cauchy sequences of points we construct a metric completion of a space together with a canonical representation equation image, equation image. We show that there is a computable embedding of in with computable inverse. Finally, we construct a notation of a dense set of points in with computable mutual distances and prove that the Cauchy representation of the resulting computable metric space is equivalent to equation image. Therefore, every computably regular space has a computable homeomorphic embedding in a computable metric space, which topologically is its completion. By the way we prove a computable Urysohn lemma. (shrink)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non-compact CSM. (...) Both results rely on having careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non-compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non-compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion-theoretic setting, then, for any such space X, there exists a Banach-Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (shrink)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space (CSM) without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non‐compact (...) CSM. Both results rely on having careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non‐compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non‐compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion‐theoretic setting, then, for any such space X, there exists a Banach‐Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

Animals navigate through three-dimensional environments, but we argue that the way they encode three-dimensional spatial information is shaped by how they use the vertical component of space. We agree with Jeffery et al. that the representation of three-dimensional space in vertebrates is probably bicoded (with separation of the plane of locomotion and its orthogonal axis), but we believe that their suggestion that the vertical axis is stored (that is, not containing distance or direction metrics usable for novel computations) (...) is unlikely, and as yet unsupported. We describe potential experimental protocols that could clarify these differences in opinion empirically. (shrink)

We consider topological pairs,, which have computable type, which means that they have the following property: if X is a computable topological space and a topological imbedding such that and are semicomputable sets in X, then is a computable set in X. It is known, e.g., that has computable type if M is a compact manifold with boundary. In this paper we examine topological spaces called graphs and we show that we can in a natural (...) way associate to each graph G a discrete subspace E so that has computable type. Furthermore, we use this result to conclude that certain noncompact semicomputable graphs in computable metric spaces are computable. (shrink)

In this article, we study an analogue of tt-reducibility for points in computable metric spaces. We characterize the notion of the metric tt-degree in the context of first-level Borel isomorphism. Then, we study this concept from the perspectives of effective topological dimension theory and of effective fractal dimension theory.

We investigate computational properties of propositional logics for dynamical systems. First, we consider logics for dynamic topological systems (W.f), fi, where W is a topological space and f a homeomorphism on W. The logics come with ‘modal’ operators interpreted by the topological closure and interior, and temporal operators interpreted along the orbits {w, f(w), f2 (w), ˙˙˙} of points w ε W. We show that for various classes of topological spaces the resulting logics are not recursively enumerable (and so (...) not recursively axiomatisable). This gives a ‘negative’ solution to a conjecture of Kremer and Mints. Second, we consider logics for dynamical systems (W, f), where W is a metric space and f and isometric function. The operators for topological interior/closure are replaced by distance operators of the form ‘everywhere/somewhere in the ball of radius a, ‘for a ε Q +. In contrast to the topological case, the resulting logic turns out to be decidable, but not in time bounded by any elementary function. (shrink)

In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The (...) importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Kőnig's Lemma and hence to the Hahn—Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense. (shrink)

The study of Martin‐Löf randomness on a computable metric space with a computable measure has seen much progress recently. In this paper we study Martin‐Löf randomness on a more general space, that is, a computable topological space with a computable measure. On such a space, Martin‐Löf randomness may not be a natural notion because there is no universal test, and Martin‐Löf randomness and complexity randomness (defined in this paper) do not coincide (...) in general. We show that SCT3 is a sufficient condition for the existence and coincidence, and study how much we can weaken this condition. (shrink)

We present a survey of the recent applications of continuous domains for providing simple computational models for classical spaces in mathematics including the real line, countably based locally compact spaces, complete separable metric spaces, separable Banach spaces and spaces of probability distributions. It is shown how these models have a logical and effective presentation and how they are used to give a computational framework in several areas in mathematics and physics. These include fractal geometry, where new results on existence (...) and uniqueness of attractors and invariant distributions have been obtained, measure and integration theory, where a generalization of the Riemann theory of integration has been developed, and real arithmetic, where a feasible setting for exact computer arithmetic has been formulated. We give a number of algorithms for computation in the theory of iterated function systems with applications in statistical physics and in period doubling route to chaos; we also show how efficient algorithms have been obtained for computing elementary functions in exact real arithmetic. (shrink)

The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the (...) classical proof of the theorem itself. More precisely, we study computability properties of the uniform extension operator which maps each functional and subspace to the set of corresponding extensions. It turns out that this operator is upper semi-computable in a well-defined sense. By applying a computable version of the Banach–Alaoglu Theorem we can show that computing a Hahn–Banach extension cannot be harder than finding a zero in a compact metric space. This allows us to conclude that the Hahn–Banach extension operator is ${\bf {\Sigma^{0}_{2}}}$ -computable while it is easy to see that it is not lower semi-computable in general. Moreover, we can derive computable versions of the Hahn–Banach Theorem for those functionals and subspaces which admit unique extensions. (shrink)

We study the uniform computational content of different versions of the Baire category theorem in the Weihrauch lattice. The Baire category theorem can be seen as a pigeonhole principle that states that a complete metric space cannot be decomposed into countably many nowhere dense pieces. The Baire category theorem is an illuminating example of a theorem that can be used to demonstrate that one classical theorem can have several different computational interpretations. For one, we distinguish two different logical (...) versions of the theorem, where one can be seen as the contrapositive form of the other one. The first version aims to find an uncovered point in the space, given a sequence of nowhere dense closed sets. The second version aims to find the index of a closed set that is somewhere dense, given a sequence of closed sets that cover the space. Even though the two statements behind these versions are equivalent to each other in classical logic, they are not equivalent in intuitionistic logic, and likewise, they exhibit different computational behavior in the Weihrauch lattice. Besides this logical distinction, we also consider different ways in which the sequence of closed sets is “given.” Essentially, we can distinguish between positive and negative information on closed sets. We discuss all four resulting versions of the Baire category theorem. Somewhat surprisingly, it turns out that the difference in providing the input information can also be expressed with the jump operation. Finally, we also relate the Baire category theorem to notions of genericity and computably comeager sets. (shrink)

Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature | K | ≤ 1. Let Met (M) = Riem(M)/Diff(M) be the space of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met (M) such as the diameter. They showed that for every Turing machine T e , e ∈ ω, there is a sequence (uniformly effective in e) of (...) homology n-spheres {P k e } k ∈ ω which are also hypersurfaces, such that P k e is diffeomorphic to the standard n-sphere S n (denoted P k e ≈ diff S n ) iff T e halts on input k, and in this case the connected sum N k e =M ♯ P k e ≈ diff M , so N k e ∈ Met(M), and N k e is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time σ e (k) of T e on inputs y i } ∈ ω of c.e. sets so that for all i the settling time of the associated Turing machine for A i dominates that for A i + 1 , even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization." From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural complexity of the geometry and topology, not merely undecidability results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use nontrivial information about c.e. sets, the Soare sequence {A i } i ∈ ω above, not merely G öodel's c.e. noncomputable set K of the 1930's; and (3) without using computability theory there is no known proof that local minima exist even for simple manifolds like the torus T 5 (see §). (shrink)

Starting with D. Scott's work on the mathematical foundations of programming language semantics, interest in topology has grown up in theoretical computer science, under the slogan `open sets are semidecidable properties'. But whereas on effectively given Scott domains all such properties are also open, this is no longer true in general. In this paper a characterization of effectively given topological spaces is presented that says which semidecidable sets are open. This result has important consequences. Not only follows the classical Rice-Shapiro (...) Theorem and its generalization to effectively given Scott domains, but also a recursion theoretic characterization of the canonical topology of effectively given metric spaces. Moreover, it implies some well known theorems on the effective continuity of effective operators such as P. Young and the author's general result which in its turn entails the theorems by Myhill-Shepherdson, Kreisel-Lacombe-Shoenfield and Ceĭtin-Moschovakis, and a result by Eršov and Berger which says that the hereditarily effective operations coincide with the hereditarily effective total continuous functionals on the natural numbers. (shrink)

For most of its history, mathematics was fairly constructive: • Euclidean geometry was based on geometric construction. • Algebra sought explicit solutions to equations. Analysis, probability, etc. were focused on calculations. Nineteenth century developments in analysis challenged this view. A sequence (an) in a metric space is said Cauchy if for every ε > 0, there is an m such that for every n, n ≥ m, d (a n , a n ) < ε.

This textbook is designed for an Introduction to Proofs course organized around the themes of number and space. Concepts are illustrated using both geometric and number examples, while frequent analogies and applications help build intuition and context in the humanities, arts, and sciences. Sophisticated mathematical ideas are introduced early and then revisited several times in a spiral structure, allowing students to progressively develop rigorous thinking. Throughout, the presentation is enlivened with whimsical illustrations, apt quotations, and glimpses of mathematical history (...) and culture. Early chapters integrate an introduction to sets, logic, and beginning proof techniques with a first exposure to more advanced mathematical structures. The middle chapters focus on equivalence relations, functions, and induction. Carefully chosen examples elucidate familiar topics, such as natural and rational numbers and angle measurements, as well as new mathematics, such as modular arithmetic and beginning graph theory. The book concludes with a thorough exploration of the cardinalities of finite and infinite sets and, in two optional chapters, brings all the topics together by constructing the real numbers and other complete metric spaces. Designed to foster the mental flexibility and rigorous thinking needed for advanced mathematics, Introduction to Mathematics suits either a lecture-based or flipped classroom. A year of mathematics, statistics, or computer science at the university level is assumed, but the main prerequisite is the willingness to engage in a new challenge. (shrink)

The category of Scott-domains gives a computability theory for possibly uncountable topological spaces, via representations. In particular, every separable Banach-space is representable over a separable domain. A large class of topological spaces, including all Banach-spaces, is representable by domains, and in domain theory, there is a well-understood notion of parametrizations over a domain. We explore the link with parameter-dependent collections of spaces in e. g. functional analysis through a case study of "Lp" -spaces. We show that a well-known domain (...) representation of "Lp" as a metric space can be made uniform in the sense of parametrizations of domains. The uniform representations admit lifting of continuous functions and are effective in p. Dependent type constructions apply, and through the study of the sum and product spaces, we clarify the notions of uniformity and uniform computability. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space (CSM) without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non‐compact (...) CSM. Both results rely on having careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non‐compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non‐compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion‐theoretic setting, then, for any such space X, there exists a Banach‐Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

Image similarity metric, also known as metric learning in computer vision, is a significant step in various advanced image tasks. Nevertheless, existing well-performing approaches for image similarity measurement only focus on the image itself without utilizing the information of other modalities, while pictures always appear with the described text. Furthermore, those methods need human supervision, yet most images are unlabeled in the real world. Considering the above problems comprehensively, we present a novel visual similarity metric model named (...) PTF-SimCM. It adopts a self-supervised contrastive structure like SimSiam and incorporates a multimodal fusion module to utilize textual modality correlated to the image. We apply a cross-modal model for text modality rather than a standard unimodal text encoder to improve late fusion productivity. In addition, the proposed model employs Sentence PIE-Net to solve the issue caused by polysemous sentences. For simplicity and efficiency, our model learns a specific embedding space where distances directly correspond to the similarity. Experimental results on MSCOCO, Flickr 30k, and Pascal Sentence datasets show that our model overall outperforms all the compared methods in this work, which illustrates that the model can effectively address the issues faced and enhance the performances on unsupervised visual similarity measuring relatively. (shrink)

Abstract. The aim of this paper is to present a topological method for constructing discretizations (tessellations) of conceptual spaces. The method works for a class of topological spaces that the Russian mathematician Pavel Alexandroff defined more than 80 years ago. Alexandroff spaces, as they are called today, have many interesting properties that distinguish them from other topological spaces. In particular, they exhibit a 1-1 correspondence between their specialization orders and their topological structures. Recently, a special type of Alexandroff spaces was (...) used by Ian Rumfitt to elucidate the logic of vague concepts in a new way. According to his approach, conceptual spaces such as the color spectrum give rise to classical systems of concepts that have the structure of atomic Boolean algebras. More precisely, concepts are represented as regular open regions of an underlying conceptual space endowed with a topological structure. Something is subsumed under a concept iff it is represented by an element of the conceptual space that is maximally close to the prototypical element p that defines that concept. This topological representation of concepts comes along with a representation of the familiar logical connectives of Aristotelian syllogistics in terms of natural settheoretical operations that characterize regular open interpretations of classical Boolean propositional logic. In the last 20 years, conceptual spaces have become a popular tool of dealing with a variety of problems in the fields of cognitive psychology, artificial intelligence, linguistics and philosophy, mainly due to the work of Peter Gärdenfors and his collaborators. By using prototypes and metrics of similarity spaces, one obtains geometrical discretizations of conceptual spaces by so-called Voronoi tessellations. These tessellations are extensionally equivalent to topological tessellations that can be constructed for Alexandroff spaces. Thereby, Rumfitt’s and Gärdenfors’s constructions turn out to be special cases of an approach that works for a more general class of spaces, namely, for weakly scattered Alexandroff spaces. This class of spaces provides a convenient framework for conceptual spaces as used in epistemology and related disciplines in general. Alexandroff spaces are useful for elucidating problems related to the logic of vague concepts, in particular they offer a solution of the Sorites paradox (Rumfitt). Further, they provide a semantics for the logic of clearness (Bobzien) that overcomes certain problems of the concept of higher2 order vagueness. Moreover, these spaces help find a natural place for classical syllogistics in the framework of conceptual spaces. The crucial role of order theory for Alexandroff spaces can be used to refine the all-or-nothing distinction between prototypical and nonprototypical stimuli in favor of a more fine-grained gradual distinction between more-orless prototypical elements of conceptual spaces. The greater conceptual flexibility of the topological approach helps avoid some inherent inadequacies of the geometrical approach, for instance, the so-called “thickness problem” (Douven et al.) and problems of selecting a unique metric for similarity spaces. Finally, it is shown that only the Alexandroff account can deal with an issue that is gaining more and more importance for the theory of conceptual spaces, namely, the role that digital conceptual spaces play in the area of artificial intelligence, computer science and related disciplines. Keywords: Conceptual Spaces, Polar Spaces, Alexandroff Spaces, Prototypes, Topological Tessellations, Voronoi Tessellations, Digital Topology. (shrink)

It is shown that for compact metric spaces the following statements are pairwise equivalent: “X is Loeb”, “X is separable”, “X has a we ordered dense subset”, “X is second countable”, and “X has a dense set G = ∪{Gn : n ∈ ω}, ∣Gn∣ < ω, with limn→∞ diam = 0”. Further, it is shown that the statement: “Compact metric spaces are weakly Loeb” is not provable in ZF0 , the Zermelo-Fraenkel set theory without the axiom of (...) regularity, and that the countable axiom of choice for families of finite sets CACfin does not imply the statement “Compact metric spaces are separable”. (shrink)

We study conditions for a topological space to be metrizable, properties of metrizable spaces, and the role the axiom of choice plays in these matters.

The subject of the present article is the following fact. Consider an effective uniform space. A generally constructed metric from the uniformity has the property that a sequence from the space effectively converges with respect to the uniform topology if and only if it does with respect to the induced metric. This can be shown without assuming the computability of the metric.

In this paper we study the emergence of Minkowski space–time from a discrete causal network representing a classical information flow. Differently from previous approaches, we require the network to be topologically homogeneous, so that the metric is derived from pure event-counting. Emergence from events has an operational motivation in requiring that every physical quantity—including space–time—be defined through precise measurement procedures. Topological homogeneity is a requirement for having space–time metric emergent from the pure topology of causal (...) connections, whereas physically homogeneity corresponds to the universality of the physical law. We analyze in detail the case of 1+1 dimensions. If we consider the causal connections as an exchange of classical information, we can establish coordinate systems via an Einsteinian protocol, and this leads to a digital version of the Lorentz transformations. In a computational analogy, the foliation construction can be regarded as the synchronization with a global clock of the calls to independent subroutines in a parallel distributed computation. Thus the Lorentz time-dilation emerges as an increased density of leaves within a single tic-tac of a clock, whereas space-contraction results from the corresponding decrease of density of events per leaf. The operational procedure of building up the coordinate system introduces an in-principle indistinguishability between neighboring events, resulting in a network that is coarse-grained, the thickness of the event being a function of the observer's clock. The illustrated simple classical construction can be extended to space dimension greater than one, with the price of anisotropy of the maximal speed, due to the Weyl-tiling problem. This issue is cured if the causal network is quantum, as e.g. in a quantum cellular automaton, and isotropy is recovered by quantum coherence via superposition of causal paths. We thus argue that in a causal network description of space–time, the quantum nature of the network is crucial. (shrink)

§ 1. Introduction. In this communication we present some recent results on the classification of Polish metric spaces up to isometry and on the isometry groups of Polish metric spaces. A Polish metric space is a complete separable metric space.Our first goal is to determine the exact complexity of the classification problem of general Polish metric spaces up to isometry. This work was motivated by a paper of Vershik [1998], where he remarks : (...) “The classification of Polish spaces up to isometry is an enormous task. More precisely, this classification is not ‘smooth’ in the modern terminology.” Our Theorem 2.1 below quantifies precisely the enormity of this task.After doing this, we turn to special classes of Polish metric spaces and investigate the classification problems associated with them. Note that these classification problems are in principle no more complicated than the general one above. However, the determination of their exact complexity is not necessarily easier.The investigation of the classification problems naturally leads to some interesting results on the groups of isometries of Polish metric spaces. We shall also present these results below.The rest of this section is devoted to an introduction of some basic ideas of a theory of complexity for classification problems, which will help to put our results in perspective. Detailed expositions of this general theory can be found, e.g., in Hjorth [2000], Kechris [1999], [2001]. (shrink)

This project uses machine learning and computer vision techniques and a novel interactive visualization tool to provide street-level characterization of urban spaces such as safety and maintenance in urban neighborhoods. This is achieved by collecting and annotating street-view images, extracting objective metrics through computer vision techniques, and using crowdsourcing to statistically model the perception of subjective metrics such as safety and maintenance. For modeling human perception and scaling it up with a predictive algorithm, we evaluate perception predictions across two points (...) in time separated by economic changes in the urban core of Raleigh, North Carolina, in the aftermath of the 2008 Great Recession. We hypothesize specific socioeconomic processes can be substantially reflected in the built environment of cities and, thus, render themselves visible at the street level. This paper describes the process of incorporating subjective visual ratings across two datasets of temporally separated street-view images, an algorithm, and a visualization tool. This work serves as a case study for utilizing AI and visualization techniques in a richer characterization of urban spaces that includes both objective metrics such as income (that operates at a broader scale) and subjective metrics such as perception of individuals (that operates at a narrower scale at specific locations). We outline an interdisciplinary methodology to test this hypothesis in streetscape data from Raleigh, NC, from 2008 to 2020. We describe the results of training algorithms that utilized image features with crowdsourced human perception ratings. We provide a comparison of the results with income data. The analysis and interpretation of this comparison provide insight into the challenges and opportunities for using AI technology in characterizing changes in urban environments. One challenge is the ability of human domain experts to interpret the output of algorithms through manipulation and to integrate these results into their workflow. This is addressed with a novel interface designed for interactive analysis and visualization. We conclude with a discussion of some of the benefits and limitations of integrating AI models in the human expert’s decision-making process in the presence of both subjective and objective metrics. (shrink)

Fix an integer $r \ge 3$. We consider metric spaces on n points such that the distance between any two points lies in $\left\{ {1, \ldots,r} \right\}$. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left + o\left}.$Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. When r is (...) even, our structural characterization is more precise and implies that almost all such metric spaces have all distances at least $r/2$. As an easy consequence, when r is even, we improve the error term above from $o\left$ to $o\left$, and also show a labeled first-order 0-1 law in the language ${\cal L}_r $, consisting of r binary relations, one for each element of $[r]$. In particular, we show the almost sure theory T is the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in $\left\{ {r/2, \ldots,r} \right\}$.Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws. (shrink)

We study Polish spaces for which a set of possible distances $A \subseteq R^+$ is fixed in advance. We determine, depending on the properties of A, the complexity of the collection of all Polish metric spaces with distances in A, obtaining also example of sets in some Wadge classes where not many natural examples are known. Moreover we describe the properties that A must have in order that all Polish spaces with distances in that set belong to a given (...) class, such as zero-dimensional, locally compact, etc. These results lead us to give a fairly complete description of the complexity, with respect to Borel reducibility and again depending on the properties of A, of the relations of isometry and isometric embeddability between these Polish spaces. (shrink)

A metric space is said to be locally non-compact if every neighborhood contains a sequence that is eventually bounded away from every element of the space, hence contains no accumulation point. We show within recursive mathematics that a nonvoid complete metric space is locally non-compact iff it is without isolated points.The result has an interesting consequence in computable analysis: If a complete metric space has a computable witness that it is without (...) isolated points, then every neighborhood contains a computable sequence that is eventually computably bounded away from every computable element of the space. (shrink)

We show that metric spaces and continuous functions between them are domain representable using the category of Scott-Ershov domains. A notion of effectivity for metric spaces is thereby inherited from effective domain theory. It is shown that a separable metric space with an effective metric can be represented by an effective domain. For a class of spaces, including the Euclidean spaces, the usual notions of effectivity are obtained. The Banach fixed point theorem is a consequence (...) of the least fixed point theorem for domains. A notion of semieffective domains is introduced and used to give a new proof of Ceitin's theorem. (shrink)