F Nous contacter


0

Logic and Foundations  | enregistrements trouvés : 33

O

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

Post-edited  Distributive Aronszajn trees
Rinot, Assaf (Auteur de la Conférence) | CIRM (Editeur )

It is well-known that the statement "all $\aleph_1$-Aronszajn trees are special'' is consistent with ZFC (Baumgartner, Malitz, and Reinhardt), and even with ZFC+GCH (Jensen). In contrast, Ben-David and Shelah proved that, assuming GCH, for every singular cardinal $\lambda$: if there exists a $\lambda^+$-Aronszajn tree, then there exists a non-special one. Furthermore:
Theorem (Ben-David and Shelah, 1986) Assume GCH and that $\lambda$ is singular cardinal. If there exists a special $\lambda^+$-Aronszajn tree, then there exists a $\lambda$-distributive $\lambda^+$-Aronszajn tree.
This suggests that following stronger statement:
Conjecture. Assume GCH and that $\lambda$ is singular cardinal.
If there exists a $\lambda^+$-Aronszajn tree,
then there exists a $\lambda$-distributive $\lambda^+$-Aronszajn tree.

The assumption that there exists a $\lambda^+$-Aronszajn tree is a very mild square-like hypothesis (that is, $\square(\lambda^+,\lambda)$).
In order to bloom a $\lambda$-distributive tree from it, there is a need for a toolbox, each tool taking an abstract square-like sequence and producing a sequence which is slightly better than the original one.
For this, we introduce the monoid of postprocessing functions and study how it acts on the class of abstract square sequences.
We establish that, assuming GCH, the monoid contains some very powerful functions. We also prove that the monoid is closed under various mixing operations.
This allows us to prove a theorem which is just one step away from verifying the conjecture:

Theorem 1. Assume GCH and that $\lambda$ is a singular cardinal.
If $\square(\lambda^+,<\lambda)$ holds, then there exists a $\lambda$-distributive $\lambda^+$-Aronszajn tree.
Another proof, involving a 5-steps chain of applications of postprocessing functions, is of the following theorem.

Theorem 2. Assume GCH. If $\lambda$ is a singular cardinal and $\square(\lambda^+)$ holds, then there exists a $\lambda^+$-Souslin tree which is coherent mod finite.

This is joint work with Ari Brodsky. See: http://assafrinot.com/paper/29
It is well-known that the statement "all $\aleph_1$-Aronszajn trees are special'' is consistent with ZFC (Baumgartner, Malitz, and Reinhardt), and even with ZFC+GCH (Jensen). In contrast, Ben-David and Shelah proved that, assuming GCH, for every singular cardinal $\lambda$: if there exists a $\lambda^+$-Aronszajn tree, then there exists a non-special one. Furthermore:
Theorem (Ben-David and Shelah, 1986) Assume GCH and that $\lambda$ is singular ...

03E05 ; 03E65 ; 03E35 ; 05C05

In recent papers by Alon et al. and Fox et al. it is demonstrated that families of graphs with a semialgebraic edge relation of bounded complexity have strong regularity properties and can be decomposed into very homogeneous semialgebraic pieces up to a small error (typical example is the incidence relation between points and lines on a real plane, or higher dimensional analogues). We show that in fact the theory can be developed for families of graphs definable in a structure satisfying a certain model theoretic property called distality, with respect to a large class of measures (this applies in particular to graphs definable in arbitrary o-minimal theories and in p-adics). (Joint work with Sergei Starchenko.) In recent papers by Alon et al. and Fox et al. it is demonstrated that families of graphs with a semialgebraic edge relation of bounded complexity have strong regularity properties and can be decomposed into very homogeneous semialgebraic pieces up to a small error (typical example is the incidence relation between points and lines on a real plane, or higher dimensional analogues). We show that in fact the theory can be developed for families of ...

03C45 ; 03C60 ; 03C64

Post-edited  Wrapping in exact real arithmetic
Müller, Norbert (Auteur de la Conférence) | CIRM (Editeur )

A serious problem common to all interval algorithms is that they suffer from wrapping effects, i.e. unnecessary growth of approximations during a computation. This is essentially connected to functional dependencies inside vectors of data computed from the same inputs. Reducing these effects is an important issue in interval arithmetic, where the most successful approach uses Taylor models.
In TTE Taylor models have not been considered explicitly, as they use would not change the induced computability, already established using ordinary interval computations. However for the viewpoint of efficiency, they lead to significant improvements.
In the talk we report on recent improvements on the iRRAM software for exact real arithmetic (ERA) based on Taylor models. The techniques discussed should also easily be applicable to other software for exact real computations as long as they also are based on interval arithmetic.
As instructive examples we consider the one-dimensional logistic map and a few further discrete dynamical systems of higher dimensions
Joint work with Franz Brauße, Trier, and Margarita Korovina, Novosibirsk.
A serious problem common to all interval algorithms is that they suffer from wrapping effects, i.e. unnecessary growth of approximations during a computation. This is essentially connected to functional dependencies inside vectors of data computed from the same inputs. Reducing these effects is an important issue in interval arithmetic, where the most successful approach uses Taylor models.
In TTE Taylor models have not been considered ...

68Q25 ; 03D60 ; 65Y15

In the first part, we describe the canonical model structure on the category of strict $\omega$-categories and how it transfers to related subcategories. We then characterize the cofibrant objects as $\omega$-categories freely generated by polygraphs and introduce the key notion of polygraphic resolution. Finally, by considering a monoid as a particular $\omega$-category, this polygraphic point of view will lead us to an alternative definition of monoid homology, which happens to coincide with the usual one. In the first part, we describe the canonical model structure on the category of strict $\omega$-categories and how it transfers to related subcategories. We then characterize the cofibrant objects as $\omega$-categories freely generated by polygraphs and introduce the key notion of polygraphic resolution. Finally, by considering a monoid as a particular $\omega$-category, this polygraphic point of view will lead us to an alternative definition ...

18D05 ; 18G55 ; 18G50 ; 18G10

We discuss classical realizability, a branch of mathematical logic that investigates the computational content of mathematical proofs by establishing a correspondence between proofs and programs. Research in this field has led to the development of highly technical constructions generalizing the method of forcing in set theory. In particular, models of realizability are models of ZF, and forcing models are special cases of realizability models.

03E70 ; 03F50 ; 03F55

Recent work has clarified how various natural second-order set-theoretic principles, such as those concerned with class forcing or with proper class games, fit into a new robust hierarchy of second-order set theories between Gödel-Bernays GBC set theory and Kelley-Morse KM set theory and beyond. For example, the principle of clopen determinacy for proper class games is exactly equivalent to the principle of elementary transfinite recursion ETR, strictly between GBC and GBC+$\Pi^1_1$-comprehension; open determinacy for class games, in contrast, is strictly stronger; meanwhile, the class forcing theorem, asserting that every class forcing notion admits corresponding forcing relations, is strictly weaker, and is exactly equivalent to the fragment $\text{ETR}_{\text{Ord}}$ and to numerous other natural principles. What is emerging is a higher set-theoretic analogue of the familiar reverse mathematics of second-order number theory. Recent work has clarified how various natural second-order set-theoretic principles, such as those concerned with class forcing or with proper class games, fit into a new robust hierarchy of second-order set theories between Gödel-Bernays GBC set theory and Kelley-Morse KM set theory and beyond. For example, the principle of clopen determinacy for proper class games is exactly equivalent to the principle of elementary transfinite recursion ETR, ...

03E60 ; 03E30 ; 03C62

N. Hindman, I. Leader and D. Strauss proved that if $2^{\aleph_0}<\aleph_\omega$ then there is a finite colouring of $\mathbb{R}$ so that no infinite sumset $X+X$ is monochromatic. Now, we prove a consistency result in the other direction: we show that consistently relative to a measurable cardinal for any $c:\mathbb{R}\to r$ with $r$ finite there is an infinite $X\subseteq \mathbb{R}$ so that $c\upharpoonright X+X$ is constant. The goal of this presentation is to discuss the motivation, ideas and difficulties involving this result, as well as the open problems around the topic. Joint work with P. Komj‡th, I. Leader, P. Russell, S. Shelah and Z. Vidny‡nszky. N. Hindman, I. Leader and D. Strauss proved that if $2^{\aleph_0}<\aleph_\omega$ then there is a finite colouring of $\mathbb{R}$ so that no infinite sumset $X+X$ is monochromatic. Now, we prove a consistency result in the other direction: we show that consistently relative to a measurable cardinal for any $c:\mathbb{R}\to r$ with $r$ finite there is an infinite $X\subseteq \mathbb{R}$ so that $c\upharpoonright X+X$ is constant. The goal of this ...

03E02 ; 03E35 ; 05D10

On introduira la logique modale épistémique avec des exemples (enfants sales, etc.). On abordera la notion de logique modale et de structure de Kripke. On évoquera le problème de satisfiabilité et la méthode de tableau. Ensuite, nous verrons comment mettre à jour un modèle de Kripke. Nous verrons d'abord les annonces publiques. Puis nous verrons comment modéliser quelques actes de communications à l'aide des modèles d'actions. Une démonstration des enfants sales et du puzzle des prisonniers avec des "agents intelligents" sera présentée. On introduira la logique modale épistémique avec des exemples (enfants sales, etc.). On abordera la notion de logique modale et de structure de Kripke. On évoquera le problème de satisfiabilité et la méthode de tableau. Ensuite, nous verrons comment mettre à jour un modèle de Kripke. Nous verrons d'abord les annonces publiques. Puis nous verrons comment modéliser quelques actes de communications à l'aide des modèles d'actions. Une démonstration ...

In 1971 Baumgartner showed it is consistent that any two $\aleph_1$-dense subsets of the real line are order isomorphic. This was important both for the methods of the proof and for consequences of the result. We introduce methods that lead to an analogous result for $\aleph_2$-dense sets.

Keywords : forcing - large cardinals - Baumgartner isomorphism - infinitary Ramsey principles - reflection principles

03E35 ; 03E05 ; 03E50 ; 03E55 ; 03E57

The "untwisted" Anosov-Katok diffeomorphisms of the torus or the disk are a source of interesting and counterintuitive measure preserving diffeomorphisms. This talk will present work showing just how broad this class is by giving a general symbolic representation of the AK diffeomorphisms that encodes, for example, all odometer based diffeomorphisms.

The combinatorics of successors of singular cardinals presents a number of interesting open problems. We discuss the interactions at successors of singular cardinals of two strong combinatorial properties, the stationary set reflection and the tree property. Assuming the consistency of infinitely many supercompact cardinals, we force a model in which both the stationary set reflection and the tree property hold at $\aleph_{\omega^2+1}$. Moreover, we prove that the two principles are independent at this cardinal, indeed assuming the consistency of infinitely many supercompact cardinals it is possible to force a model in which the stationary set reflection holds, but the tree property fails at $\aleph_{\omega^2+1}$. This is a joint work with Menachem Magidor.
Keywords : forcing - large cardinals - successors of singular cardinals - stationary reflection - tree property
The combinatorics of successors of singular cardinals presents a number of interesting open problems. We discuss the interactions at successors of singular cardinals of two strong combinatorial properties, the stationary set reflection and the tree property. Assuming the consistency of infinitely many supercompact cardinals, we force a model in which both the stationary set reflection and the tree property hold at $\aleph_{\omega^2+1}$. ...

03E05 ; 03E35 ; 03E55

Diophantine properties of subsets of $\mathbb{R}^n$ definable in an o-minimal expansion of the ordered field of real numbers have been much studied over the last few years and several applications to purely number theoretic problems have been made. One line of inquiry attempts to characterise the set of definable functions $f : \mathbb{R} \to \mathbb{R}$ having the property that $f(\mathbb{N}) \subset \mathbb{N}$. For example, a result of Thomas, Jones and myself shows that if the structure under consideration is $\mathbb{R}_{exp}$ (the real field expanded by the exponential function) and if, for all positive $r, f(x)$ eventually grows more slowly than $exp(x^r)$, then $f$ is necessarily a polynomial with rational coefficients. In this talk I shall improve this result in two directions. Firstly, I take the structure to be $\mathbb{R}_{an,exp}$ (the expansion of $\mathbb{R}_{exp}$ by all real analytic functions defined on compact balls in $\mathbb{R}^n$) and secondly, I allow the growth rate to be $x^N \cdot 2^x$ for arbitrary (fixed) $N$. The conclusion is that $f(x) = p(x) \cdot 2^x + q(x)$ for sufficiently large $x$, where $p$ and $q$ are polynomials with rational coefficients.

I should mention that over ninety years ago Pólya established the same result for entire functions $f : \mathbb{C} \to \mathbb{C}$ and that in 2007 Langley weakened this assumption to $f$ being regular in a right half-plane of $\mathbb{C}$. I follow Langley's method, but first we must consider which $\mathbb{R}_{an,exp}$-definable functions actually have complex continuations to a right half-plane and, as it turns out, which of them have a definable such continuation.
Diophantine properties of subsets of $\mathbb{R}^n$ definable in an o-minimal expansion of the ordered field of real numbers have been much studied over the last few years and several applications to purely number theoretic problems have been made. One line of inquiry attempts to characterise the set of definable functions $f : \mathbb{R} \to \mathbb{R}$ having the property that $f(\mathbb{N}) \subset \mathbb{N}$. For example, a result of ...

03C64 ; 26E05

The Pila-Wilkie theorem gives a bound on the number of rational points of bounded height lying on the transcendental part of a set definable in an o-minimal expansion of the real field. After discussing this result, I'll describe various classes of curves for which the Pila-Wilkie bound can be improved. I'll also give some examples and perhaps some applications.

03C64 ; 26E05

We will present some of the original definitions, results, and proof techniques about Pfaffian functions on the reals by Khovanskii.
A simple example of a Pfaffian function is an analytic function $f$ in one variable $x$ satisfying a differential equation $f^\prime = P(x,f)$ where $P$ is a polynomial in two variables. Khovanskii gives a notion of complexity of Pfaffian functions which in the example is just the degree of $P$. Using this complexity, he proves analogues of Bézout's theorem for Pfaffian curves (say, zero loci of Pfaffian functions in two variables), with explicit upper bounds in terms of the ocurring complexities.
We explain a recent application by J. Pila and others to a low-dimensional case of Wilkie's conjecture on rational points of bounded height on restricted Pfaffian curves. The result says that the number of rational points of height bounded by $T$, on a transcendental restricted Pfaffian curve, grows at most as a power of log$(T)$ as $T$ grows. This improves the typical upper bound $T^\epsilon$ in Pila-Wilkie's results in general o-minimal structures, the improvement being due to extra geometric Bézout-like control.
In the non-archimedean setting, I will explain analogues of some of these results and techniques, most of which are (emerging) work in progress with L. Lipshitz, F. Martin and A. Smeets. Some ideas in this case come from work by Denef and Lipshitz on variants of Artin approximation in the context of power series solution.
We will present some of the original definitions, results, and proof techniques about Pfaffian functions on the reals by Khovanskii.
A simple example of a Pfaffian function is an analytic function $f$ in one variable $x$ satisfying a differential equation $f^\prime = P(x,f)$ where $P$ is a polynomial in two variables. Khovanskii gives a notion of complexity of Pfaffian functions which in the example is just the degree of $P$. Using this ...

03C98 ; 14G05 ; 14H05 ; 58A17

The concept of a "transseries" is a natural extension of that of a Laurent series, allowing for exponential and logarithmic terms. Transseries were introduced in the 1980s by the analyst Écalle and also, independently, by the logicians Dahn and Göring. The germs of many naturally occurring real-valued functions of one variable have asymptotic expansions which are transseries. Since the late 1990s, van den Dries, van der Hoeven, and myself, have pursued a program to understand the algebraic and model-theoretic aspects of this intricate but fascinating mathematical object. A differential analogue of "henselianity" is central to this program. Last year we were able to make a significant step forward, and established a quantifier elimination theorem for the differential field of transseries in a natural language. My goal for this talk is to introduce transseries without prior knowledge of the subject, and to explain our recent work. The concept of a "transseries" is a natural extension of that of a Laurent series, allowing for exponential and logarithmic terms. Transseries were introduced in the 1980s by the analyst Écalle and also, independently, by the logicians Dahn and Göring. The germs of many naturally occurring real-valued functions of one variable have asymptotic expansions which are transseries. Since the late 1990s, van den Dries, van der Hoeven, and myself, have ...

03C10 ; 03C64 ; 26A12

If CCM denotes the theory of compact complex spaces in the langauge of complex-analytic sets, then the theory of models of CCM equipped with an automorphism has a model companion, denoted by CCMA. The relationship to meromorphic dynamical systems is the same as that of ACFA to rational dynamical systems. I will discuss recent joint work with Martin Bays and Martin Hils that begins a systematic study of CCMA as an expansion of ACFA. Particular topics we consider include: stable embeddedness, imaginaries, and the Zilber dichotomy. If CCM denotes the theory of compact complex spaces in the langauge of complex-analytic sets, then the theory of models of CCM equipped with an automorphism has a model companion, denoted by CCMA. The relationship to meromorphic dynamical systems is the same as that of ACFA to rational dynamical systems. I will discuss recent joint work with Martin Bays and Martin Hils that begins a systematic study of CCMA as an expansion of ACFA. Particular ...

03C60 ; 03C45 ; 03C65 ; 32Jxx

It is by now well known that collections of compact (real-)analytic vector fields and locally connected trajectories thereof are mutually well behaved in a way that can be made precise via notions from mathematical logic, namely, by saying that the structure on the real field generated by the collection is o-minimal (that is, every subset of the real numbers definable in the structure is a finite union of points and open intervals). There are also many examples known where the assumption of analyticity or compactness can be removed, yet o-minimality still holds. Less well known is that there are examples where o-minimality visibly fails, but there is nevertheless a well-defined notion of tameness in place. In this talk, I will: (a) make this weaker notion of tameness precise; (b) describe a class of examples where the weaker notion holds; and (c) present evidence for conjecturing that there might be no other classes of examples of "non-o-minimal tameness". (Joint work with Patrick Speissegger.)
A few corrections and comments about this talk are available in the PDF file at the bottom of the page.
It is by now well known that collections of compact (real-)analytic vector fields and locally connected trajectories thereof are mutually well behaved in a way that can be made precise via notions from mathematical logic, namely, by saying that the structure on the real field generated by the collection is o-minimal (that is, every subset of the real numbers definable in the structure is a finite union of points and open intervals). There are ...

03C64 ; 34E05

Multi angle  Sets with few rational points
Comte, Georges (Auteur de la Conférence) | CIRM (Editeur )

In the spirit of famous papers by Pila & Bombieri and Pila & Wilkie, I will explain how to bound the number of rational points, with respect to their height, in various kinds of sets, such as transcendental sets definable in some o-minimal - or even not o-minimal - structure over the real field. I will emphazise the role played by bounds on derivatives and on sets of zeroes in this context.

03C98 ; 11D88 ; 14G05

The field of Laurent series (with real coefficients, say) has a natural derivation but is too small to be closed under integration and other natural operations such as taking logarithms of positive elements. The field has a natural extension to a field of generalized series, the ordered differential field of transseries, where these defects are remedied in a radical way. I will sketch this field of transseries. Recently it was established (Aschenbrenner, Van der Hoeven, vdD) that the differential field of transseries also has very good model theoretic properties. I hope to discuss this in the later part of my talk. The field of Laurent series (with real coefficients, say) has a natural derivation but is too small to be closed under integration and other natural operations such as taking logarithms of positive elements. The field has a natural extension to a field of generalized series, the ordered differential field of transseries, where these defects are remedied in a radical way. I will sketch this field of transseries. Recently it was established ...

12L12 ; 12H05 ; 03C60 ; 03C64

O-minimalism is the first-order theory of o-minimal structures, an important class of models of which are the ultraproducts of o-minimal structures. A complete axiomatization of o-minimalism is not known, but many results are already provable in the weaker theory DCTC given by definable completeness and type completeness (a small extension of local o-minimality). In DCTC, we can already prove how many results from o-minimality (dimension theory, monotonicity, Hardy structures) carry over to this larger setting upon replacing 'finite' by 'discrete, closed and bounded'. However, even then cell decomposition might fail, giving rise to a related notion of tame structures. Some new invariants also come into play: the Grothendieck ring is no longer trivial and the definable, discrete subsets form a totally ordered structure induced by an ultraproduct version of the Euler characteristic. To develop this theory, we also need another first-order property, the Discrete Pigeonhole Principle, which I cannot yet prove from DCTC. Using this, we can formulate a criterion for when an ultraproduct of o-minimal structures is again o-minimal. O-minimalism is the first-order theory of o-minimal structures, an important class of models of which are the ultraproducts of o-minimal structures. A complete axiomatization of o-minimalism is not known, but many results are already provable in the weaker theory DCTC given by definable completeness and type completeness (a small extension of local o-minimality). In DCTC, we can already prove how many results from o-minimality (dimension theory, ...

03C64

Nuage de mots clefs ici

Z