We study finite -colourable structures with an underlying pregeometry. The probability measure that is usedcorresponds to a process of generating such structures by which colours are first randomly assigned to all1-dimensional subspaces and then relationships are assigned in such a way that the colouring conditions aresatisfied but apart from this in a random way. We can then ask what the probability is that the resulting structure,where we now forget the specific colouring of the generating process, has a given property. With this measurewe get the following results: (1) A zero-one law. (2) The set of sentences with asymptotic probability 1 has anexplicit axiomatisation which is presented. (3) There is a formula ξ (x, y) (not directly speaking about colours)such that, with asymptotic probability 1, the relation “there is an -colouring which assigns the same colourto x and y” is defined by ξ (x, y). (4) With asymptotic probability 1, an -colourable structure has a unique-colouring (up to permutation of the colours).

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Algebra, Geometry and Logic.

An algebra is effective if its operations are computable under some numbering. When are two numberings of an effective partial algebra equivalent? For example, the computable real numbers form an effective field and two effective numberings of the field of computable reals are equivalent if the limit operator is assumed to be computable in the numberings (theorems of Moschovakis and Hertling). To answer the question for effective algebras in general, we give a general method based on an algebraic analysis of approximations by elements of a finitely generated subalgebra. Commonly, the computable elements of a topological partial algebra are derived from such a finitely generated algebra and form a countable effective partial algebra. We apply the general results about partial algebras to the recursive reals, ultrametric algebras constructed by inverse limits, and to metric algebras in general.

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Algebra, Geometry and Logic.

Spitters, Bas

Metric complements of overt closed sets2011In: Mathematical logic quarterly, ISSN 0942-5616, E-ISSN 1521-3870, Vol. 57, no 4, p. 373-378Article in journal (Refereed)

Abstract [en]

We show that the set of points of an overt closed subspace of a metric completion of a Bishop-locally compact metric space is located. Consequently, if the subspace is, moreover, compact, then its collection of points is Bishop-compact.

Let V be a finite relational vocabulary in which no symbol has arity greater than 2. Let math formula be countable V-structure which is homogeneous, simple and 1-based. The first main result says that if math formula is, in addition, primitive, then it is strongly interpretable in a random structure. The second main result, which generalizes the first, implies (without the assumption on primitivity) that if math formula is “coordinatized” by a set with SU-rank 1 and there is no definable (without parameters) nontrivial equivalence relation on M with only finite classes, then math formula is strongly interpretable in a random structure.

The localic completion of a metric space induces a canonical notion of continuous map between metric spaces. It is shown that these maps are continuous in the sense of Bishop constructive mathematics, i.e., uniformly continuous near every compact image.

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Algebra, Geometry and Logic.

In a previous paper we constructed a full and faithful functor M from the category of locally compact metric spaces to the category of formal topologies (representations of locales). Here we show that for a real-valued continuous function f,M (f) factors through the localic positive reals if, and only if, f has a uniform positive lower bound on each ball in the locally compact space. We work within the framework of Bishop constructive mathematics, where the latter notion is strictly stronger than point-wise positivity.