In this note, we prove that every definably connected, definably compact abelian definable group G in an o-minimal expansion of a real closed field with dim(G) = 4 is definably homeomorphic to a torus of the same dimension. Moreover, in the semialgebraic case the result holds for all dimensions.

We work in the category of locally definable groups in an o-minimal expansion of a field. Eleftheriou and Peterzil conjectured that every definably generated abelian connected group G in this category is a cover of a definable group. We prove that this is the case under a natural convexity assumption inspired by the same authors, which in fact gives a necessary and sufficient condition. The proof is based on the study of the zero-dimensional compatible subgroups of G. Given a locally definable connected group G (not necessarily definably generated), we prove that the n-torsion subgroup of G is finite and that every zero-dimensional compatible subgroup of G has finite rank. Under a convexity hypothesis we show that every zero-dimensional compatible subgroup of G is finitely generated.

Keywords: 2009wy32e8 003,and phrases,covers,discrete subgroups,locally definable groups,o-minimalit,partially supported by prin

We study the thresholds for the emergence of various properties in random subgraphs of (N,<). In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.

It is known that a definably compact group G is an extension of a compact Lie group L by a divisible torsion-free normal subgroup. We show that the o-minimal higher homotopy groups of G are isomorphic to the corresponding higher homotopy groups of L. As a consequence, we obtain that all abelian definably compact groups of a given dimension are definably homotopy equivalent, and that their universal covers are contractible.

We study the model theory of “covers” of groups H definable in an o-minimal structure M. We pose the question of whether any finite central extension G of H is interpretable in M, proving some cases (such as when H is abelian) as well as stating various equivalences. When M is an o-minimal expansion of the reals (so H is a definable Lie group) this is related to Milnor’s conjecture [15], and many cases are known. We also prove a strong relative Lω1,ω -categoricity theorem for universal covers of definable Lie groups, and point out some notable differences with the case of covers of complex algebraic groups (studied by Zilber and his students).

Keywords: ams subject classification,categoricity,central extension,o-minimal,primary 03c64,secondary 22e15,universal cover

A metric space X is straight if for each finite cover of X by closed sets, and for each real valued function f on X, if f is uniformly continuous on each set of the cover, then f is uniformly continuous on the whole of X. A locally connected space is straight iff it is uniformly locally connected (ULC). It is easily seen that ULC spaces are stable under finite products. On the other hand the product of two straight spaces is not necessarily straight. We prove that the product X × Y of two metric spaces is straight if and only if both X and Y are straight and one of the following conditions holds: (a) both X and Y are precompact; (b) both X and Y are locally connected; (c) one of the spaces is both precompact and locally connected. In particular, when X satisfies (c), the product X × Z is straight for every straight space Z . Finally, we characterize when infinite products of metric spaces are ULC and we completely solve the problem of straightness of infinite products of ULC spaces.

By recent work on some conjectures of Pillay, each definably compact group in a saturated o-minimal structure is an extension of a compact Lie group by a torsion free normal divisible subgroup, called its infinitesimal subgroup. We show that the infinitesimal subgroup is cohomologically acyclic. This implies that the functorial correspondence between definably compact groups and Lie groups preserves the cohomology.

Keywords: 2006-08,and phrases,association for symbolic logic,c 2009,cohomology,dgicyt mtm2005-02865,geometr,geor,groups,o-minimality,partially supported by the,project,ıa real

The topology of definable sets in an o-minimal expansion of a group is not fully understood due to the lack of a triangulation theorem. Despite the general validity of the cell decomposition theorem, we do not know whether any definably compact set is a definable CW-complex. Moreover the closure of an o-minimal cell can have arbitrarily high Betti numbers. Nevertheless we prove that the cohomology groups of a definably compact set over an o-minimal expansion of a group are finitely generated and invariant under elementary extensions and expansions of the language.

Keywords: mathematics subject classification 2010,o-minimality,primary 03c64,secondary 55n30,shelf cohomology

By recent work on some conjectures of Pillay, each definably compact group G in a saturated o-minimal expansion of an ordered field has a normal “infinitesimal subgroup” G^00 such that the quotient G/G^00, equipped with the “logic topology”, is a compact (real) Lie group. Our first result is that the functor G → G/G^00 sends exact sequences of definably compact groups into exact sequences of Lie groups. We then study the connections between the Lie group G/G^00 and the o-minimal spectrum Spec(G) of G. We prove that G/G^00 is a topological quotient of Spec(G). We thus obtain a natural homomorphism Ψ∗ from the cohomology of G/G^00 to the (Cech-)cohomology of G. We show that if G^00 satisfies a suitable contractibility conjecture then G^00 is acyclic in Cech cohomology and Ψ∗ is an isomorphism. Finally we prove the conjecture in some special cases.

Keywords: and phrases,definable group,lie group,o-minimality,type-definable group

A metric space X is straight if for each finite cover of X by closed sets, and for each real valued function f on X, if f is uniformly continuous on each set of the cover, then f is uniformly continuous on the whole of X. The straight spaces have been studied in [A. Berarducci, D. Dikranjan, J. Pelant, An additivity theorem for uniformly continuous functions, Topology and its Applications 146–147 (2005) 339–352], which contains characterization of the straight spaces within the class of the locally connected spaces (they are the uniformly locally connected ones) and the class of the totally disconnected spaces (they coincide with the totally disconnected Atsuji spaces). We show that the completion of a straight space is straight and we characterize the dense straight subspaces of a straight space. In order to clarify further the relation between straightness and the level of local connectedness of the space we introduce two more intermediate properties between straightness and uniform local connectedness and we give various examples to distinguish them. One of these properties coincides with straightness for complete spaces and provides in this way a useful characterization of complete straight spaces in terms of the behaviour of the quasi-components of the space.

Keywords: locally connected,straight space,uc space,uniformly continuous,uniformly locally connected

We give a presentation of various results on zero-groups in o-minimal structures together with some new observations. In particular we prove that if G is a definably connected definably compact group in an o-minimal expansion of a real closed field, then for any maximal definably connected abelian subgroup T of G, G is the union of the conjugates of T. This can be seen as a generalization of the classical theorem that a compact connected Lie group is the union of the conjugates of any of its maximal tori.

We prove that if G is a group definable in a saturated o-minimal structure, then G has no infinite descending chain of type-definable subgroups of bounded index. Equivalently, G has a smallest (necessarily normal) type-definable subgroup G 00 of bounded index and G/G 00 equipped with the “logic topology” is a compact Lie group. These results give partial answers to some conjectures of the fourth author.

We consider metric spaces X with the nice property that any continuous function f:X → R which is uniformly continuous on each set of a finite cover of X by closed sets, is itself uniformly continuous. We characterize the spaces with this property within the ample class of all locally connected metric spaces. It turns out that they coincide with the uniformly locally connected spaces, so they include, for instance, all topological vector spaces. On the other hand, in the class of all totally disconnected spaces, these spaces coincide with the UC spaces.

Keywords: atsuji space,local connectedness,metric spaces,total disconnectedness,uniform continuity

Given an o-minimal structure M which expands a field, we define, for each positive integer d, a real-valued additive measure on a Boolean algebra of subsets of M^d and we prove that all the definable sets included in the finite part Fin(M^d) of M^d are measurable. When the domain of M is the real line we obtain Lebesgue measure, but restricted to a proper subalgebra of that of the Lebesgue measurable sets (the Jordan measurable sets). Our measure has good logical properties, being invariant under elementary extensions and under expansions of the language. In the final part of the paper we consider the problem of defining an analogue of the Haar measure for definably compact groups.

Wilkie (Selecta Math. (N.S.) 5 (1999) 397) proved a “theorem of the complement” which implies that in order to establish the o-minimality of an expansion of R with C ∞ functions it suffices to obtain uniform (in the parameters) bounds on the number of connected components of quantifier free definable sets. He deduced that any expansion of R with a family of Pfaffian functions is o-minimal. We prove an effective version of Wilkie’s theorem of the complement, so in particular given an expansion of the ordered field R with finitely many C^∞ functions, if there are uniform and computable upper bounds on the number of connected components of quantifier free definable sets, then there are uniform and computable bounds for all definable sets. In such a case the theory of the structure is effectively o-minimal: there is a recursively axiomatized subtheory such that each of its models is o-minimal. This implies the effective o-minimality of any expansion of R with Pfaffian functions. We apply our results to the open problem of the decidability of the theory of the real ÿeld with the exponential function. We show that the decidability is implied by a positive answer to the following problem (raised by van den Dries (in: Logic: From Foundations to applications, Oxford Science Publ., Oxford University Press, New York, 1996, p. 137)): given a language L expanding the language of ordered rings, if an L-sentence is true in every L-structure expanding the ordered field of real numbers, then it is true in every o-minimal L-structure expanding any real closed field.

Keywords: o-minimality,pfa an functions,real exponentiation

Let M be an o-minimal expansion of an ordered field. Let φ be a formula in the language of ordered domains. In this note we establish some topological properties which are transferred from φM to φℝ and vice versa. Then, we apply these transfer results to give a new proof of a result of M. Edmundo—based on the work of A. Strzebonski—showing the existence of torsion points in any definably compact group defined in an o-minimal expansion of an ordered field.

We prove that every complete metric space X that is thin (i.e., every closed subspace has connected uniform quasi components) has the compact separation property (for any two disjoint closed connected subspaces A and B of X there is a compact set K disjoint from A and B such that every neighbourhood of K disjoint from A and B separates A and B). The real line and all compact spaces are obviously thin. We show that a space is thin if and only if it does not contain a certain forbidden configuration. Finally we prove that every metric UA-space (see [Rend. Instit. Mat. Univ. Trieste 25 (1993) 23–56]) is thin. The UA-spaces form a class properly including the Atsuji spaces.

Keywords: compact,metric spaces,quasi component,real-valued functions,thin spaces

The uniformly approachable functions introduced in [Quaestiones Math. 18 (1995) 381–396] are defined by a property stronger than continuity and weaker than uniform continuity, which is preserved under composition. (So they give rise to a category which sits between the category of metric spaces with all continuous functions and the category of metric spaces with all uniformly continuous functions.) Solving a problem left open in [Rend. Istit. Mat. Univ. Trieste 25 (1993) 23– 56], we give a complete characterization of the polynomial maps f : Rn → R which are uniformly approachable. They coincide with the polynomial maps f with distant fibers, i.e., such that any two distinct fibers f −1 (x) and f −1 (y) are at positive distance. The same holds more generally for any real valued function on Rn whose fibers have finitely many connected components. To prove this we show that every real valued continuous function with distant fibers on a uniformly locally connected metric space is uniformly approachable, and any (weakly) uniformly approachable function on Rn has “distant connected components of fibers”. We observe that a bounded continuous function f : Rn → R has distant fibers if and only if it is uniformly continuous. This suggests that for a reasonable metric space X the uniform continuity of a bounded continuous function f : X → R depends only on the fibers of f . We show that this is the case when X is connected and locally connected. A useful tool in the study of uniformly approachable functions on domains more general than Rn is given by the technique of “truncations” (g is a truncation of f if it is locally constant where it differs from f ). On Rn the functions with many uniformly continuous truncations coincide with the functions with distant connected components of fibers. We improve the technique of the magic set introduced in [Rend. Istit. Mat. Univ. Trieste 25 (1993) 23–56] and studied by M.R. Burke and K. Ciesielski showing that every continuous function with “small fibers” on a locally arcwise connected metric space X has a magic set M ⊂ X (i.e., every continuous g : X → R with g(M) ⊂ f (M) is a truncation of f )

Keywords: approachable functions,metric spaces,real valued functions,unicoherence

The definable fundamental group of a definable set in an o-minimal expansion of a field is computed. This is achieved by proving the relevant case of the o-minimal van Kampen theorem. This result is applied to show that if the geometrical realization of a simplicial complex over an o-minimal expansion of a field is a definable manifold of dimension not 4, then its geometrical realization over the reals is a topological manifold.

Extensions of the simply typed lambda calculus have been used as a metalanguage to represent “higher order term algebras”, such as, for instance, formulas of the predicate calculus. In this representation bound variables of the object language are represented by bound variables of the metalanguage. This choice has various advantages but makes the notion of “recursive definition” on higher order term algebras more subtle than the corresponding notion on first order term algebras. Despeyroux, Pfenning and Schurmann pointed out the problems that arise in the proof of a canonical form theorem when one combines higher order representations with primitive recursion. In this paper we consider a stronger scheme of recursion and we prove that it captures all partial recursive functions on second order term alge- bras. We illustrate the system by considering typed programs to reduce to normal form terms of the untyped lambda calculus, encoded as ele- ments of a second order term algebra. First order encodings based on de Bruijn indexes are also considered. The examples also show that a version of the intersection type disciplines can be helpful in some cases to prove the existence of a canonical form. Finally we consider interpretations of our typed systems in the pure lambda calculus and a new goedelization the pure lambda calculus.

We develop an intersection theory for definable C^p -manifolds in an o-minimal expansion of a real closed field and we prove the invariance of the intersection numbers under definable C^p -homotopies (p > 2). In particular we define the intersection number of two definable submanifolds of complementary dimensions, the Brouwer degree and the winding numbers. We illustrate the theory by deriving in the o-minimal context the Brouwer fixed point theorem, the Jordan-Brouwer separation theorem and the invariance of the Lefschetz numbers under definable C^p -homotopies. A. Pillay has shown that any definable group admits an abstract manifold structure. We apply the intersection theory to definable groups after proving an embedding theorem for abstract definably compact C^p -manifolds. In particular using the Lefschetz fixed point theorem we show that the Lefschetz number of the identity map on a definably compact group, which in the classical case coincides with the Euler characteristic, is zero.

Keywords: o-minimality

Recent work on infinitary versions of the lambda calculus has shown that the infinite lambda calculus can be a useful tool to study the unsolvable terms of the classical lambda calculus. Working in the framework of the intersection type disciplines, we devise a type assignment system such that two terms are equal in the infinite lambda calculus iff they can be assigned the same types in any basis. A novel feature of the system is the presence of a type constant to denote the set of all terms of order zero, and the possibility of applying a type to another type. We prove a completeness and an approximation theorem for our system. Our results can be considered as a first step towards the goal of giving a denotational semantics for the lambda calculus which is suited for the study of the unsolvable terms. However, some noncontinuity phenomena of the infinite lambda calculus make a full realization construction of a filter model) a quite difficult task.

Keywords: infinite i-calculus

The field of generalized power series with real coefficients and exponents in an ordered abelian divisible group G is a classical tool in the study of real closed fields. We prove the existence of irreducible elements in the ring R((G≤0)) consisting of the generalized power series with non-positive exponents. The following candidate for such an irreducible series was given by Conway (1976): Sum_n t^(−1/n) + 1. Gonshor (1986) studied the question of the existence of irreducible elements and obtained necessary conditions for a series to be irreducible. We show that Conway’s series is indeed irreducible. Our results are based on a new kind of valuation taking ordinal numbers as values. If G = (R, +, 0, ≤) we can give the following test for irreducibility based only on the order type of the support of the series: if the order type α is either ω or of the form ω^ω^α and the series is not divisible by any monomial, then it is irreducible. To handle the general case we use a suggestion of M.-H. Mourgues, based on an idea of Gonshor, which allows us to reduce to the special case G = R. In the final part of the paper we study the irreducibility of series with finite support.

We study the poset B(G) of all precompact Hausdorff group topologies on an infinite group G and its subposet B(G)w of topologies of weight w, extending earlier results of Berhanu, Comfort, Reid, Remus, Ross, Dikranjan, and others. We show that if B(G)w is non-empty and the power set of G/G' has the same size as the power set of G (in particular, if G is abelian) then the poset of all subsets of 2^G of size w can be embedded into B(G)w (and vice versa). So the study of many features (depth, height, width, size of chains, etc.) of the poset B(G)w is reduced to purely set-theoretical problems. We introduce a cardinal function Ded*(w) to measure the length of chains of subsets of cardinality w of a set of larger cardinality generalizing the well-known cardinal function Ded(w). We prove that Ded*(w) = Ded(w) iff the cofinality of Ded(w) is different from w^+ and we use earlier results of Mitchell and Baumgartncr to show that Ded*(aleph_1 ) = Ded(aleph_1) is independent of Zermelc+Fraenkel set theory (ZFC). We apply this result to show that it cannot be established in ZFC whether B(G)aleph_1 has chains of bigger size than those of the bounded chains. We prove that the poset B(G)aleph_0 of all Hausdorff metrizable group topologies on the group G = (direct sum of aleph_0 copies of Z/2Z) has uncountable depth, hence cannot be embedded into B(G)aleph_0. This is to be contrasted with the fact that for every infinite abelian group G the poset H(G) of all Hausdorff group topologies on G can be embedded into B(G). We also prove that it is independent of ZFC whether the poset H(G)aleph_0 has the same height as the poset B(G)aleph_0

We treat a general technique to obtain Church - Rosser extensions of the lambda-beta-calculus, based on the notion of “confining class” and on an infinitary version of lambda-calculus. We apply the technique to find a large class of terms which can be consistently equated to every other term, and we also show that many equations between lambda-terms can be consistently added to the the lambda-beta-calculus.

We define a model of the lambda-beta-calculus which is similar to the model of Boehm trees, but it does not identify all the unsolvable lambda-terms. The role of the unsolvable terms is taken by a much smaller class of terms which we call mute. Mute terms are those zero terms which are not beta-convertible to a zero term applied to something else. We prove that it is consistent with the lambda-beta-calculus to simultaneously equate all the mute terms to a fixed arbitrary closed term. This allows us to strengthen some results of Jacopini and Venturini Zilli concerning easy lambda-terms. Our results depend on an infinitary version of lambda-calculus. We set the foundations for such a calculus, which might turn out to be a useful tool for the study of non-sensible models of lambda-calculus.

Models of normal open induction are those normal discretely ordered rings whose nonnegative part satisfy Peano's axioms for open formulas in the language of ordered semirings. (Where normal means integrally closed in its fraction field.) In 1964 Shepherdson gave a recursive nonstandard model of open induction. His model is not normal and does not have any infinite prime elements. In this paper we present a recursive nonstandard model of normal open induction with an unbounded set of infinite prime elements.

We prove that if G is a Delta_0 definable function on the natural numbers and F(n) is the product of the first n values of G, then F is also Delta_0 definable. Moreover, the inductive properties of F can be proved inside the theory IDelta_0.

Given two closed lambda-terms A and B we consider the question whether the equation A = B is consistent with the lambda-beta-calculus. In general the problem is undecidable. However if A is a 0-term we can give good sufficient conditions for the consistency. This allows us to prove some counterintuitive results such as: (1) there is a closed lambda-term X which can be consistently equated to every closed lambda-term with the exception of the identity lambda x.x. (2) there is a closed lambda-term which can be consistenlty equated to every closed normal form, but not to the Curry fixed point operator Y.

Keywords: lambda-calculus

We define a general notion of (syntactic) unification, whose special cases are matching, unification, semi-unification, and weak-unification. We settle all the implications between the various cases of unification leading to a classification and a decidability result. We show that some distinctions holding for finite terms collapse for infinite terms. We give some positive results on the existence of most general weak-unifiers.

Let PLω be the provability logic of IΔ0 + ω1. We prove some containments of the form L ⊆ PLω < Th(C) where L is the provability logic of PA and Th(C) is a suitable class of Kripke frames.

The cop number c(G) of a graph G is an invariant connected with the genus and the girth. We prove that for a fixed k there is a polynomial-time algorithm which decides whether c(G) ≤ k. This settles a question of T. Andreae. Moreover, we show that every graph is topologically equivalent to a graph with c ≤ 2. Finally we consider a pursuit-evasion problem in Littlewood′s miscellany. We prove that two lions are not always sufficient to catch a man on a plane graph, provided the lions and the man have equal maximum speed. We deal both with a discrete motion (from vertex to vertex) and with a continuous motion. The discrete case is solved by showing that there are plane graphs of cop number 3 such that all the edges can be represented by straight segments of the same length.

Uniformly approachable (UA) functions are a common generalization of uniformly continuous functions an d perfect functions. We study UA-functions and UA-spaces i. e. those uniform spaces in which every real valued continuous function is UA. Such spaces properly include the UC-spaces (Atsuji spaces). We characterize the weakly-UA subspaces of the real line and give a new characterization of the UC spaces. We prove a topological result which implies, under the continuum hypothesis, the existence of a subset M of the the n-dimensional euclidean space R^n such that if two continuous functions f, g from R^n to R are are not constant on any open set and g(M) is a subset of f(M), then f=g.

We formalize a technique introduced by B"{o}hm and Piperno to solve systems of recursive equations in lambda calculus without the use of the fixed point combinator and using only normal forms. To this aim we introduce the notion of a canonical algebraic term rewriting system, and we show that any such system can be interpreted in the lambda calculus by the B"{o}hm - Piperno technique in such a way that strong normalization is preserved. This allows us to improve some recent results of Mogensen concerning efficient g"{o}delizations $godel{˜}: Lambda rightarrow Lambda$ of lambda calculus. In particular we prove that under a suitable g"{o}delization there exist two lambda terms $bf E$ (self-interpreter) and $bf R$ (reductor), both having a normal form, such that for every (closed or open) lambda term $M;$ ${bf E}godel{M} reduce M$ and if $M$ has a normal form $N$, then ${bf R}godel{M} reduce godel{N}$.

We prove that the theory IΔ0, extended by a weak version of the Δ0-Pigeonhole Principle, proves that every integer is the sum of four squares (Lagrange's theorem). Since the required weak version is derivable from the theory IΔ0 + ∀x (xlog(x) exists), our results give a positive answer to a question of Macintyre (1986). In the rest of the paper we consider the number-theoretical consequences of a new combinatorial principle, the ‘Δ0-Equipartition Principle’ (Δ0EQ). In particular we give a new proof, which can be formalized in IΔ0 + Δ0EQ, of the fact that every prime of the form 4n + 1 is the sum of two squares.

It is well known that in bounded arithmetic one can code sequences and recursive definitions using bounded formulas. We present a way of doing this with the help of a notion of pseudo-sequence. Pseudo sequences can be concatenated but do not possess a primitive for extracting the n-th element.

We consider the predicative modal provability logic of Peano Arithmetic where the interpretation of each atomic modal formulas is required to be belong to the set of arithmetic formulas of complexity Sigma_0^n. We show that for distinct values of n the corresponding modal formulas form a strict hierarchy and each of them is complete for the class Pi^0_2.

The notion of iteratively defined functions from and to heterogeneous term algebras is introduced as the solution of a finite set of equations of a special shape. Such a notion has remarkable consequences: (1) Choosing the second-order typed lambda- calculus (Lambsa for short) as a programming language enables one to represent algebra elements and iterative functions by automatic uniform synthesis paradigms, using neither conditional nor recursive constructs. (2) A completeness theorem for Lambda-terms with type of degree at most two and a companion corollary for Lambda-programs have been proved. (3) A new congruence relation for the last-mentioned Lambda-terms which is stronger than Lambda-convertibility is introduced and proved to have the meaning of a Lambda-program equivalence. Moreover, an extension of the paradigms to the synthesis of functions of higher complexity is considered and exemplified. All the concepts are explained and motivated by examples over integers, list- and tree-structures.