En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK

Logic and Foundations 126 résultats

Filtrer
Sélectionner : Tous / Aucun
Q
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
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

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
The theorem of Büchi-Bruyère states that a subset of $N^d$ is $b$-recognizable if and only if it is $b$-definable. As a corollary, the first-order theory of $(N,+,V_b)$ is decidable (where $V_b(n)$ is the largest power of the base $b$ dividing $n$). This classical result is a powerful tool in order to show that many properties of $b$-automatic sequences are decidable. The first part of my lecture will be devoted to presenting this result and its applications to $b$-automatic sequences. Then I will move to $b$-regular sequences, which can be viewed as a generalization of $b$-automatic sequences to integer-valued sequences. I will explain bow first-order logic can be used to show that many enumeration problems of $b$-automatic sequences give rise to corresponding $b$-regular sequences. Finally, I will consider more general frameworks than integer bases and (try to) give a state of the art of the research in this domain.[-]
The theorem of Büchi-Bruyère states that a subset of $N^d$ is $b$-recognizable if and only if it is $b$-definable. As a corollary, the first-order theory of $(N,+,V_b)$ is decidable (where $V_b(n)$ is the largest power of the base $b$ dividing $n$). This classical result is a powerful tool in order to show that many properties of $b$-automatic sequences are decidable. The first part of my lecture will be devoted to presenting this result and its ...[+]

68R15 ; 11B85 ; 68Q45 ; 03B25

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
2y
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

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

Prikry type forcing and combinatorial properties - Sinapova, Dima (Auteur de la Conférence) | CIRM H

Multi angle

We will analyze consequences of various types of Prikry forcing on combinatorial properties at singular cardinals and their successors, focusing on weak square and simultaneous stationary reflection. The motivation is how much compactness type properties can be obtained at successors of singulars, and especially the combinatorics at $\aleph_{\omega+1}$.

03E04 ; 03E35 ; 03E55

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

From forcing models to realizability models - Fontanella, Laura (Auteur de la Conférence) | CIRM H

Multi angle

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

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

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

Post-edited

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

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

The undecidability of the domino problem - Jeandel, Emmanuel (Auteur de la Conférence) | CIRM H

Multi angle

One of the most fundamental problem in tiling theory is to decide, given a surface, a set of tiles and a tiling rule, whether there exist a way to tile the surface using the set of tiles and following the rules. As proven by Berger in the 60's, this problem is undecidable in general.
When formulated in terms of tilings of the discrete plane by unit tiles with colored constraints, this is called the Domino Problem and was introduced by Wang in an effort to solve satisfaction problems for ??? formulas by translating the problem into a geometric problem.
In this course, we will give a brief description of the problem and to the meaning of the word “undecidable”, and then give two different proofs of the result.[-]
One of the most fundamental problem in tiling theory is to decide, given a surface, a set of tiles and a tiling rule, whether there exist a way to tile the surface using the set of tiles and following the rules. As proven by Berger in the 60's, this problem is undecidable in general.
When formulated in terms of tilings of the discrete plane by unit tiles with colored constraints, this is called the Domino Problem and was introduced by Wang in an ...[+]

03D35 ; 05B45

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

An introduction to Walnut - lecture 2 - Rampersad, Narad (Auteur de la Conférence) | CIRM H

Multi angle

Walnut is computer software, written in Java, that implements an algorithm to decide the truth of first-order logic statements in an extension of Presburger arithmetic known as Buchi arithmetic. It can be used to prove a wide variety of results in combinatorics on words and number theory. In this course we will give an introduction to the theory behind Walnut, examples of the types of results that can be proved with it, and exercises for participants to get some hands-on training on how to use Walnut.[-]
Walnut is computer software, written in Java, that implements an algorithm to decide the truth of first-order logic statements in an extension of Presburger arithmetic known as Buchi arithmetic. It can be used to prove a wide variety of results in combinatorics on words and number theory. In this course we will give an introduction to the theory behind Walnut, examples of the types of results that can be proved with it, and exercises for ...[+]

68R15 ; 68Q45 ; 03F30

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

Automatic actions - Bartholdi, Laurent (Auteur de la Conférence) | CIRM H

Multi angle

I will present a general notion of automatic action, based on Büchi automata, and show how it unifies a large number of subclasses, in particular the automatic groups by Cannon, Thurston et al., the transducer groups by Aleshin, Grigorchuk, Sushchansky, Sidki et al., and substitutional subshifts. I will present some algorithms for these groups, and in particular show under an extra condition (boundedness) that their orbit relation is computable. This will have strong decidability consequences, such as that the order problem, aperiodicity, minimality, etc. for automatic transformations is decidable.[-]
I will present a general notion of automatic action, based on Büchi automata, and show how it unifies a large number of subclasses, in particular the automatic groups by Cannon, Thurston et al., the transducer groups by Aleshin, Grigorchuk, Sushchansky, Sidki et al., and substitutional subshifts. I will present some algorithms for these groups, and in particular show under an extra condition (boundedness) that their orbit relation is computable. ...[+]

68Q45 ; 20F65 ; 20F10 ; 37B05

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
Sélection Signaler une erreur