Comments on Pourquoi e et π paraissent-ils plus aléatoires que génériques ?

SM (2023-08-01T20:00:47Z)

Petite remarque sur le fait que les locales sont assez cools sur ces histoires d'aléatoire et de généricité. On peut parler de la plus petite sous-locale de mesure pleine ou de la plus petite sous-locale dense : elle est sans point mais non-triviale, et on peut considérer que la première capture l'essence de la mesure choisie et l'autre l'essence de la généricité topologique. Cette essence n'est capturée par aucun point mais se balade "entre les points", ou plutôt est capturée par les identifications entre ouverts.

Cf. l'article 'Measure, randomness and sublocales" d'Alex Simpson.

jonas (2018-09-13T22:22:22Z)

Either I'm too tired to find it, or you don't have a link from this post to your closely related question on Mathoverflow: <URL: https://mathoverflow.net/questions/176488/ > Can we define an “empirically generic” real number?

Ruxor (2018-02-23T18:04:33Z)

@Fab:

Le fait qu'un ensemble négligeable puisse avoir la puissance du continu ne devrait pas tellement surprendre : c'est juste que ça ne mesure pas la même chose ; ça ne surprend pas que dans ℝ² ce soit le cas (une droite a le même cardinal que le plan), et par ailleurs, dans ℕ on peut avoir des parties infinies extrêmement « éparses » (l'ensemble des puissances de 2 a densité nulle, par exemple), donc ça ne devrait pas sembler trop bizarre qu'une partie négligeable de ℝ puisse avoir le cardinal de ℝ (l'ensemble de Cantor = ensemble des nombres entre 0 et 1 dont un développement en base 3 ne comporte aucun 1, fournit un exemple explicite).

C'est déjà plus remarquable qu'un ensemble négligeable puisse être comaigre : c'est vraiment une différence d'opinion flagrante entre la mesure et la catégorie.

Une autre chose surprenante concerne la notion d'ensemble fortement négligeable : N est dit fortement négligeable si pour toute suite de réels strictement positifs on peut recouvrir N par une suite d'intervalles dont la longueur est inférieure au réel donné correspondant (je veux dire, la longueur du n-ième intervalle est inférieure au n-ième réel donné). Une caractérisation équivalente (ce n'est pas évident) est que N+M n'est jamais égal à ℝ si M est maigre. Un ensemble dénombrable est fortement négligeable et un ensemble fortement négligeable est négligeable. La réciproque de la deuxième implication est facile à réfuter : l'ensemble de Cantor n'est pas fortement négligeable. En revanche, la réciproque de la première est… indécidable dans ZFC (ça s'appelle le problème de Borel, voir <URL: http://en.wikipedia.org/wiki/Strong_measure_zero_set >).

Concernant le fait qu'on puisse ou non « résoudre » l'hypothèse du continu, c'est quelque chose sur quoi les théoricien des ensembles ont des avis assez différents, voir <URL: http://mathoverflow.net/questions/23829/solutions-to-the-continuum-hypothesis >. Certains pensent que ça a un sens qu'elle soit vraie ou fausse, et qu'il faut chercher des axiomes plus forts permettant de trancher naturellement la question, certains pensent que la question est déjà tranchée dans un sens ou dans l'autre, certains pensent que ça n'a pas de sens et qu'il n'y a pas une vérité platonique unique dans le monde de la théorie des ensembles (c'est ma position à moi : je note que pour ce qui est des [énoncés du premier ordre sur les] entiers naturels, en revanche, je pense qu'il y a une vérité absolue) ; et il y a quantité de variantes sur chacune de ces positions.

Fab (2018-02-23T00:15:16Z)

Très très bel article aussi ! Lecture entremelée avec ton article du 10/02/18 sur l'approximation diophantienne. Une découverte que ces catégories topologiques auxquelles je ne connaissais rien (!). Très jolie quasi-dualité avec les ensembles mesurables, m'enfin bon, j'étais tout de même parti dans ma lecture, campé sur mes positions, qu'on ne me fera pas avaler que pour parler des "gros" ensembles, M. Eriab serait aussi bien placé due M. Eugsebel … jusqu'à ce que j'apprenne

… qu'un ensemble négligeable peut avoir la puissance du continu (comme l'ensemble des nombres de Liouville). Ça alors… Voilà, je doute.

Bon, il y aurait de l'indécidabilité de l'hypothèse du continu derrière ça que j'en ne serais pas très étonné.

Bon, j'ose la question un peu hors-sujet (qui n'est certainement pas bien posée) (il faudra que je relise ton papier sur le vrai et le prouvable) : cette hypothèse du continu HR, peut-on considérer que

[HR est vraie ou HR est fausse dans une certaine extension de ZF ou ZFC, et c'est le travail du logicien voire du mathématicien de déterminer une extension "raisonnable" de la théorie des ensembles permettant de trancher la question]

Ou bien l'assertion ci-dessus est fausse ou imprécise ou ambiguë, dans le sens qu'il serait possible de trouver par exemple une extension "raisonnables" où HR est vraie ET une extension "raisonnable" où HR est fausse (certes, le mot "raisonnable" est à définir). Bref y a-t-il une vérité relative ou absolue sur HR (certes indécidable dans ZF et ZFC) ? Voire une vérité mais qui ne serait elle-même peut-être pas prouvable ("HR est vraie ou fausse mais cele ne sera jamais démontré") (ou encore à un niveau meta supplémentaire, la dernière assertion étant elle-même non démontrable,etc.)

J'avoue que je n'ai pas encore les idées très claires sur le sujet.

Couard Anonyme (2014-07-30T07:15:44Z)

@DM
Ton commentaire a assez peu de lien avec l'entrée de DAM mais puisqu'on s'autorise à digresser chez autrui sans vergogne…

Non seulement les problèmes industriels ne sont pas aléatoires mais en plus nous avons une manière biaisée de les poser.

C'est ainsi que le simplexe dual est significativement plus rapide sur les problèmes industriels que le simplexe primal alors qu'ils ont image en miroir l'un de l'autre. L'explication est que nous posons la plupart de nos problèmes sous forme de minimisation du coût et non de par exemple de maximisation de la productivité (ou du dual du coût).

Ptitboul (2014-07-29T09:14:59Z)

Mon intuition c'est que π ou e sont des nombres naturels dans les mathématiques continues (géométrie / analyse). Et que la notion de nombre générique ne vit pas dans ce type de mathématiques. Donc ça serait surprenant qu'ils soient pseudo-génériques, alors que ça ne surprend pas qu'ils soient pseudo-aléatoires.
Ce qui est cohérent avec ta remarque sur l'inexistence de nombres «naturels» pseudo-génériques, car les nombres «naturels» sont ceux issus des mathématiques continues. Les nombres construits par arguments de diagonalisation, par exemple, sont issus des mathématiques discrètes (en premier lieu la logique), non ?

DM (2014-07-25T18:00:37Z)

Au Vienna Summer of Logic, il y a eu un panel où l'on se posait (au fond) la question suivante: les solveurs ont un comportement très différent sur les instances SAT que l'on veut résoudre effectivement pour prouver la correction de circuits ou de logiciels et sur les instances aléatoires (pour la distribution la plus évidente sur 3SAT), on sait en partie pourquoi et quand les instances aléatoires sont dures mais en revanche on ne sait pas pourquoi les instances « industrielles » ne sont pas si dures que cela.

On s'en tire par un argument « elles découlent d'objets conçus par des humains, qui ont donc certaines régularités », mais ce n'est guère satisfaisant.

Ruxor (2014-07-24T20:48:54Z)

@f3et: Il y a des constructions explicites, oui (enfin, explicites… en utilisant l'oracle de l'arrêt), par des sortes de diagonalisations (en gros, on énumère les fermés d'intérieur vide calculables et on fait ce qu'il faut pour les éviter), qu'on peut aussi appliquer pour fabriquer des réels aléatoires : ça doit être expliqué dans le livre de Cooper ou celui de Lerman que j'ai cités ; mais je n'en connais pas qui ait de définition aussi simple que la constante de Chaitin. Pour les pseudogénériques, c'est encore plus mystérieux, et c'est un peu la question que je pose : je ne sais pas du tout comment on en fabriquerait (autrement qu'avec le même procédé ; on peut peut-être se limiter à une diagonalisation sur les primitifs récursifs, ce qui rendrait la construction théoriquement calculable, mais je ne sais vraiment pas faire un générateur pseudogénérique aussi facilement qu'un pseudoaléatoire).

f3et (2014-07-24T19:54:09Z)

Il est assez difficile de construire des nombres aléatoires, mais la constante de Chaitin (Omega) en est un. A-t-on une construction d'un réel générique? Ou, à défaut, d'un réel pseudo-générique ?

Ruxor (2014-07-24T13:52:20Z)

@jonas: Ooops, of course you're right. Fixed.

Frank Wolff (2014-07-24T12:33:04Z)

@YBM
C'est-à-dire que π contient la Bibliothèque de Babel.
Quand je pense que la Bibliothèque de Babel contient π…

jonas (2014-07-24T09:05:05Z)

This sentence looks like a mistake to me: "pour trouver $n^2$ bits 0 consécutifs dans une suite aléatoire, il faudra aller jusqu'au bit $n^2$ environ". It actually takes about $2^{n^2}$ bits to find such an infix.

YBM (2014-07-23T20:21:28Z)

Le caractère normal de π a donné l'idée à un développeur assez chafouin d'une implémentation assez originale d'un système de fichier :

https://github.com/philipl/pifs

(don't do this at home ! En voulant sauvegarder un fichier de deux ou trois mots avec vi, je n'ai jamais pu redémarrer mon système sinon brutalement)

Ted (2014-07-23T11:15:54Z)

Article fascinant, merci beaucoup ! Ayant passé du temps à étudier les propriétés des réels aléatoires mais ne connaissant pas la notion duale présentée ici, j'ai appris tout un tas de choses vraiment passionnantes =)