1,720,971 research outputs found
Provability logic: models within models in Peano Arithmetic
Get PDFIn 1994 Jech gave a model-theoretic proof of Godel's second incompleteness theorem for Zermelo-Fraenkel set theory in the following form: ZF does not prove that ZF has a model. Kodarski showed that Jech's proof can be adapted to Peano Arithmetic with the role of models being taken by complete consistent extensions. In this note we take another step in the direction of replacing proof-theoretic by model-theoretic arguments. We show, without the need of formalizing the proof of the completeness theorem within PA, that the existence of a model of PA of complexity Sigma(0)(2) is independent of PA, where a model is identified with the set of formulas with parameters which hold in the model. Our approach is based on a new interpretation of the provability logic of Peano Arithmetic where rectangle phi is defined as the formalization of "phi is true in every Sigma(0)(2)-model"
On definably proper maps
Get PDFIn this paper we work in o-minimal structures with definable Skolem functions and show that a continuous definable map between Hausdorff locally definably compact definable spaces is definably proper if and only if it is proper morphism in the category of definable spaces. We give several other characterizations of definably proper including one involving the existence of limits of definable types. We also prove the basic properties of definably proper maps and the invariance of definably proper in elementary extensions and o-minimal expansions
Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
No full textValued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. The computational complexity of VCSPs depends on the set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of the complexity of infinite-domain VCSPs with piecewise linear homogeneous cost functions. Such VCSPs can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by reducing the problem to a finite-domain VCSP which can be solved using the basic linear program relaxation. It follows that VCSPs for submodular PLH cost functions can be solved in polynomial time; in fact, we show that submodular PLH functions form a maximally tractable class of PLH cost functions
Fundamental group in o-minimal structures with definable Skolem functions
No full textIn this paper we work in an arbitrary o-minimal structure with definable Skolem functions and prove that definably connected, locally definable manifolds are uniformly definably path connected, have an admissible cover by definably simply connected, open definable subsets and, definable paths and definable homotopies on such locally definable manifolds can be lifted to locally definable covering maps. These properties allow us to obtain the main properties of the general o-minimal fundamental group, including: invariance and comparison results; existence of universal locally definable covering maps; monodromy equivalence for locally constant o-minimal sheaves – from which one obtains, as in algebraic topology, classification results for locally definable covering maps, o-minimal Hurewicz and Seifert–van Kampen theorems
Submodular functions and valued constraint satisfaction problems over infinite domains
No full textValued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. It is desirable to classify the computational complexity of VCSPs depending on a fixed set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified in this sense. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear homogeneous cost functions. We remark that in this paper the infinite domain will always be the set of rational numbers. We show that such VCSPs can be solved in polynomial time when the cost functions are additionally submodular, and that this is indeed a maximally tractable class: adding any cost function that is not submodular leads to an NP-hard VCSP
Rotorcraft Flight Simulation to Support Aircraft Certification: Methodologies to Evaluate the Uncertainties on a Tiltrotor Model
Get PDFHigh temporal and spatial resolution X-band radar based system to monitor rainfall events and detect landslide risk in the Mediterranean area
Get PDFDuality between preferential attachment and static networks on hyperbolic spaces
Get PDFThere is a complex relation between the mechanism of preferential attachment, scale-free degree distributions and hyperbolicity in complex networks. In fact, both preferential attachment and hidden hyperbolic spaces often generate scale-free networks. We show that there is actually a duality between a class of growing spatial networks based on preferential attachment on the sphere and a class of static random networks on the hyperbolic plane. Both classes of networks have the same scale-free degree distribution as the Barabasi-Albert model. As a limit of this correspondence, the Barabasi-Albert model is equivalent to a static random network on an hyperbolic space with infinite curvature. © 2014 EPLA
Higher homotopy of groups definable in o-minimal structures
No full textIt 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
- …
