Des souris et des pré-souris

Martial · July 2020

Hi everybody !!!
J'ai quelques questions.

1) Quelqu'un a-t-il déjà entendu parler de mouse ou de premouse en théorie des ensembles ?
2) Comment traduire ça en français ?
3) Qu'appelle-t-on exactement la "Wadge-determinacy" ?
Je connais un peu les travaux de Wadge, notamment ce qui concerne sa classification ramifiée des boréliens, mais je ne vois pas pourquoi (maintenant qu'on sait que les boréliens sont déterminés) il y aurait une détermination "à la Wadge".

Merci d'avance.
Martial.

Maxtimax · July 2020

1) et 2) : l'étymologie de "mouse" est une erreur de lecture (ou une coquille, je ne sais plus), suivi d'un amusement de la personne qui a introduit la notion, donc je pense que "souris" (et donc "présouris") est tout à fait légitime

Aucune idée pour 3)

Martial · July 2020

Merci Max

Thierry Poma · July 2020

Bonsoir,

Axiom of determinacy: axiome de détermination (voir les différents articles liés à ces notions)

Wadge-determinacy: peut se comprendre comme ceci : selon Wadge, le caractère déterminant (ou la détermination) (...) ; voire encore "la détermination selon Wadge".
Voici sa thèse.

Amicalement,

Thierry

christophe c · July 2020

@Martial, oui j'en ai entendu parler il y a 22 ou 23 ans, par Boban au sens où il m'a dit qu'il existait une notion qui s'appelle "mouse". Mais nous avons ensuite changé de sujet et il ne m'a pas dit ce que c'est.

Si $A,B$ sont deux parties de $2^\N$, le jeu suivant:

Lea joue $x_0$, puis Bob joue $y_0$, puis Lea joue $x_1$, puis Bob joue $y_1$,Lea joue $x_2$, puis Bob joue $y_2$, etc

et à la fin Lea gagne quand $A(x) = B(y)$

est le jeu de Wadge associé au couple $(A,B)$.

Quand Lea y Sgagne (ie a une stratégie infaillible pour gagner), on dit que $B<A$ en complexité de Wadge. Quand Bob y Sgagne, on dit que $B\leq nonA$.

D'après AD, on peut associer à chaque ensemble $X$ un ordinal $\sigma(X)$ tel que pour tous $X,Y$ :

1/ $X<Y$ et $X<nonY$ entraine $\sigma(X)<\sigma(Y)$

2/ $X<Y$ ou $Y\leq nonX$

2 est évident et 1 est facile en se rappelant que sous AD tout ensemble a la propriété de Baire (ie est un ouvert à un maigre près).

En conclusion, sous AD, il y a une sorte de bon ordre pour les complexités des parties de $\R$, définie de manière très naturelles via le fait qu'un ensemble est "pas plus complexe" qu'un autre s'il en est une image récipoque continue.

Je pense que "Wadge-determinacy" est l'exression qui abrège que les jeux précédents sont déterminés (ce qui n'implique pas a priori que tous les jeux le soient).

Martial · July 2020

@Thierry : merci pour la thèse de Wadge.

@Christophe : j'avais entendu parler des travaux de Wadge par Saint-Raymond en 1990 (de mieux en mieux !)...
Il nous avait fait un topo à peu près du même genre que le tien, sauf qu'il ne supposait pas AD mais travaillait dans ZFC et utilisait la détermination borélienne ***. Il classifiait donc ainsi tous les boréliens de $\mathbb{R}$, avec une borne de complexité qu'on appelle l'ordinal de Veblen et qui se balade quelque part entre $\omega_1$ et $\omega_2$.

Mon problème c'est que je ne comprends pas bien ton jeu.
Qu'est-ce que ça veut dire exactement $A(x)=B(y)$ ? Ça veut dire que $x \in A \Leftrightarrow y \in B$, c'est ça ?

*** Je pense que la thèse postée par Thierry (qui date de 1983) est une version remaniée de la thèse de Wadge initiale. Car à ma connaissance Wadge a soutenu avant 1975, donc à l'époque on ne savait pas encore de façon certaine si tous les boréliens sont déterminés. Et c'est pour ça qu'à l'époque la communauté internationale a attaché peu de crédits à ses travaux, car tout était basé sur la détermination borélienne.

christophe c · July 2020

Pour ta question c'est oui. De mon téléphone

Martial · July 2020

J'ai finalement trouvé la définition d'une souris, et je la trouve particulièrement absconse.
Soit $E$ un ensemble.
On pose $J_0[E]= \emptyset$.
$J_{\alpha +1} [E]$ = la clôture de $J_{\alpha}[E]$ par les fonctions qui sont rudimentaires dans $E$ (i.e. rudimentaires ou de la forme $x \mapsto x \cap E$.
$J_{\lambda}[E] =$ ce que tu penses pour $\lambda$ limite.

Définition : Une pré-souris $\mathcal{M}$ est un modèle de la forme $J_{\alpha}[E]$, où $E$ code une suite de plongements élémentaires dont les domaines sont des segments initiaux de $\mathcal{M}$.

Définition : Une souris est une pré-souris qui est suffisamment itérable.

Avec ça on est bien avancés.
C'est quoi une fonction rudimentaire ?
C'est quoi "suffisamment itérable" ?

Thierry Poma · July 2020

Bonjour Martial,

Je viens de t'envoyer deux choses sur ta messagerie.

Amicalement,

Thierry

Thierry Poma · July 2020

Cf. ceci.

Martial · July 2020

@Thierry : Bizarrement je n'ai pas reçu tes messages.

Thierry Poma · July 2020

@Martial : ton adresse dans ton profil est-elle la bonne ?

Martial · July 2020

@Thierry : ça y est j'ai compris (j'ai le cerveau lent en ce moment).
Je t'ai répondu par mail.

christophe c · July 2020

@Martial (je reviens sur la notion de complexité, pas des "mouses" que je ne connais pas, et que je regarderai quand on aura défini les "cats" :-X )

Le côté bien fondé de la complexité de Wadge n'est pas intrinsèque, il dépend de l'axiome du choix

Par contre tu as une notion de "cc-complexité", qui elle est édifiante et est TOUJOURS bien fondé, même en présence de l'axiome du choix. La seule chose qui change c'est sa largeur. Plus précisément en présence de AD elle est un ordre total et donc à nouveau, comme pour Wadge on peut associer un ordinal de complexité à chaque partie de IR.

Sa définition est la suivante: $A < B$ veut dire que tu peux continument savoir, en fonction de $u$ si $\{n\in \N \mid (p\mapsto u(2^n(2p+1)) )\in A\}$ est non vide avec l'oracle $B$.

De plus cette notion est édifiante pour "les gens" en ce qu'elle démontre que l'alternance de quantificateur est LE saut universel de complexité.

Des souris et des pré-souris

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 41