J'ai l'idée de faire un (des?) threads sur les perdants de ce concours !
J'ai déjà parlé (un peu) de Yoneda sous le duel correspondant, quelqu'un·e a un perdant des seizièmes dont iel veut entendre parler ?
C'est parti pour le troisième, sur les théorèmes d'incomplétude de Gödel (qui ont inexplicablement perdu contre la formule de Bayes........)
Bon évidemment je commence par une petite anecdote : mon prof de sup nous les a (trèèèès vaguement) présentés en tout début de sup.
Il venait de nous raconter le premier, en expliquant (vaguement à nouveau) comment dire "je ne suis pas prouvable", et je lui demande alors si on ne venait pas de prouver cet énoncé (on venait de voir qu'on ne pouvait pas le démontrer !), et il me répond alors
"si T sait qu'elle est cohérente ! C'est le 2nd théorème d'incomplétude" et je n'avais (évidemment) pas tout compris, mais l'élégance de l'argument m'a marqué et ça m'a poussé à étudier pas mal de logique après coup. C'était une très bonne manière de se mettre en confiance
2è thread sur le concours de @SimonBillouet , aujourd'hui je parle d'un nouveau perdant, le théorème du rang.
Je commence par rappeler son énoncé:
soit E un espace vectoriel de dimension finie, F un espace vectoriel, et f : E -> F une application linéaire. Alors
dim E = dim(ker(f)) + rg(f), où rg(f) est la dimension de im(f) (qui est de dimension finie car E l'est, c'est pour ça qu'on n'a pas besoin d'hypothèses sur F)
Je rappelle aussi sa preuve, très simple, et qui va me permettre de dire des trucs un peu plus intéressants:
On prend un supplémentaire S de ker(f) dans E, et on remarque (c'est très facile) que la restriction de f à S est un isomorphisme S -> im(f), de quoi le résultat se déduit immédiatement. Mais allons un peu plus loin dans cette affaire. Remarquez en effet que j'ai pris un S
Du coup, premier thread sur l'un des perdants du concours de @SimonBillouet . Comme je l'ai dit il y en a beaucoup dont je voulais parler - parmi ceux qui ont été mentionnés dans les réponses à mon tweet, je ne me sens pas forcément qualifié pour parler de Church-Rosser, parce
que je connais pas grand chose aux questions de réécriture ou de confluence, donc ce serait plus quelque chose sur le lambda-calcul (j'ai essentiellement jamais travaillé sur les détails techniques d'implémentation en logique, ce que ce théorème me semble être - j'espère que des
logicien-ne-s pourront me raconter autre chose s'il y a autre chose). Autrement, on a mentionné Zorn et le théorème d'inversion locale. Je commence par Zorn parce que je préfère et que je me sens plus à l'aise aussi (je verrai si je fais l'inversion locale 😁)
Si on veut un exemple d'un théorème qui est prouvé sans axiome du choix et qui pourtant n'est pas "constructif", je pense qu'un bon exemple c'est le théorème de Cantor-Bernstein, et on le voit quand on veut l'appliquer.
Et sans surprise, sa non-constructivité vient... du tiers exclu ! L'exemple qui me frappe toujours c'est la bijection entre R et P(N) : c'est très facile de trouver des injections dans les deux sens;
et C-B nous fournit "explicitement" (si, si, regardez la preuve!) une bijection R-> P(N) à partir de ces injections. Pourtant, qui est capable de donner une formule pour cette bijection ? (formule à prendre en un sens un peu large, mais qui par exemple permet de déterminer f(pi))