Comments on C'est dur, la récurrence

Dionysos (2013-08-01T20:59:50Z)

Tu as écrit (réagir à un post d'environs dix ans suscite quelque perplexité dans le temps à employer, "tu avais écrit" m'est passé par l'esprit) :
" Et si on l'écrivait, il faudrait expliquer pourquoi quand il s'agit de voir l'hérédité (« (∀n)((P(n))⇒(P(n+1))) »), on doit supposer pour un certain n que P(n) est vrai alors que c'est écrit « pour tout n""
Eh bien non, je ne vois vraiment pas la difficulté. Il est écrit "pour tout n" qui est muni de la propriété P et la formule se borne à une pure implication du type si P(x) alors il s'ensuit que c'est vrai pour son successeur. Quelle tension ou problème y a-t-il avec le fait qu'il faut aussi s'assurer que c'est effectivement cette propriété se vérifie pour le premier nombre de manière à donner un point d'ancrage effectif à la moulinette de la validation consécutive sur les autres nombres ??? C'est comme si tu soutenais que les élèves de Deug sont incapables de saisir ce qu'est une implication basée sur une supposition du type de ce qu'on fait spontanément en lisant de la SF. Ex: si dans le monde d'Asimov la psychohistoire de Seldon continue à dérouler ses prévisions malgré l'événement imprévisible du Mulet, alors c'est que la seconde fondation existe. L'implication est saisie par tout lecteur et pourtant il n'accorde aucunement que le mulet ou la science psychohistorique ont quelque réalité authentique.

Anonymous Coward #177 (denis) (2003-10-23T21:29:57Z)

Comment ça, "rien que pour nous piéger"? Il a bien dit qu'il s'adressait aux mathématiciens ricanants dans le fond, non? Et, de fait, peu de profs de maths (et même peu de mathématiciens non spécialement formés à la théorie des ensembles) reconnaissent sans effort l'axiome de fondation ainsi déguisé…

Anonymous Coward #95 (garoo) (2003-10-22T11:59:06Z)

Moi, j'avais envisagé que X pouvait contenir des ensembles aussi, mais je me suis dit que c'était tellement inattendu et confus que le Professeur Madore n'aurait pas fait ça sans le dire, comme ça, juste pour nous piéger :)

Ghalys (2003-10-22T08:02:28Z)

Désolé, je n'avais pas songé que z puisse être à la fois élément et ensemble.

Ghalys honteux qui retourne débuguer sur son territoire.

Ruxor (2003-10-21T17:38:12Z)

Touriste: Bravo, c'est en effet une formulation de l'axiome de fondation (non, rien à voir avec Asimov…) ! Tu gagnes 200 zorkmids et le droit de rejouer. Pourquoi l'ai-je formulé de cette façon ? Pour illustrer le fait que l'axiome de fondation est un principe d'induction (précisément, le principe d'induction bien-fondée, portant sur la relation d'appartenance), de même que la récurrence.

Le principe de récurrence dit quoi ? Que pour prouver une propriété pour tout entier naturel n, il suffit de la prouver pour 0 et de la prouver pour k+1, et que, de plus, dans ce dernier cas, on peut la supposer déjà vérifiée pour k. Le principe d'induction bien-fondée dit quoi ? Que pour prouver une propriété (en l'occurrence celle d'appartenir au sous-ensemble y) pour tout élément z d'un ensemble x, on peut la supposer déjà vérifiée pour tous les éléments (t) de x qui appartiennent aussi à z. C'est très rusé. Et si on veut prouver qu'une propriété est vraie pour tous les ensembles, on peut à chaque fois supposer que la propriété est déjà vérifiée pour tous les éléments de l'ensemble en question. (Il y a aussi un principe de définition par induction bien-fondée, à côté du principe de définition par récurrence.)

(Il se trouve aussi que la formulation que j'ai écrite est la seule façon valable d'affirmer l'axiome de fondation en logique intuitionniste, mais là ça devient carrément des maths ésotériques.)

Ghalys: Non, non, je ne me suis pas trompé dans ce que j'ai écrit, c'est bien z appartient à x et pas z sous-ensemble de x que je voulais écrire. Le truc est justement que les ensembles ne sont pas forcément bien typés en « objets », « ensembles d'objets », « ensembles d'ensembles d'objets », etc, mais qu'il est tout à fait permis de mélanger les niveaux, et d'avoir un ensemble qui a des éléments en commun avec certains de ses propres éléments. (De toute façon, si on croit à l'évangile selon ZF, un ensemble ne peut contenir que d'autres ensembles, qui à leur tour, etc, sauf que ça finit toujours pas s'arrêter et c'est justement ce que dit l'axiome de fondation.) Cet énoncé porte précisément sur ce genre de choses, et ça n'aurait donc pas beaucoup de sens de tenter de mettre des petites lettres pour les éléments et des grandes lettres pour les ensembles.

Mais j'avoue que j'ai choisi cet énoncé exprès parce qu'il est abscons, oui, quand même.

Anonymous Coward #168 (Arezki) (2003-10-21T16:53:36Z)

Je trouve très amusante cette invitation au débat succédant à la note "Fallait-il dire quelque chose".

Anonymous Coward #169 (LN) (2003-10-21T15:01:47Z)

Ah la récurrence ! Quand j'ai appris cela en TS, le prof prenait la lettre k pour la partie hérédité. Je trouve qque cela était plus clair…
Mais, je me souviens surtout en BAC+3, aux USA, 3 fois 2 heures de cours sur des récurrences de base, avec des étudiants largués qui ont fini par apprendre par coeur les récurrences vues, en espérant que le jour de l'examen on redemanderait la même… Sur ma copie, j'ai eu l'appréciation du prof "très clair et très bonne, bravo !" (en français dans le texte)

Anonymous Coward #168 (Arezki) (2003-10-21T14:55:25Z)

C'est peut-être parce que x est un ensemble d'ensembles.

Anonymous Coward #95 (garoo) (2003-10-21T13:09:33Z)

Euh, par rapport à ta dernière équation…
- z est une partie de x et je ne comprends pas (comme Ghalys, visiblement) pourquoi tu écris appartenance au lieu d'inclusion, ou il y a une nuance qui m'échappe ?
(si c'est la deuxième solution, oublier la question suivante)
- que y soit x tout entier ou non, comment un z pour lequel "tout élément de x qui est dans z est aussi dans y" peut ne pas être dans y ?

Tiens un touriste (2003-10-21T12:13:25Z)

Je crains que les (certains) enseignants du secondaire n'aient une part de responsabilité dans ce que nous infligent les étudiants qu'ils ont (dé)formés avant de les transmettre à l'Université.

Ainsi (ce n'est pas de première main mais d'une collègue fiable) une étudiante de cette année prétend de façon crédible (car suffisamment précise) que, pour introduire le calcul dans P(n) implique P(n+1), son enseignant de terminale lui demandait de commencer par "Supposons P(n) vraie pour un n quelconque" "et qu'il trouvait très important qu'on écrive bien le quelconque" ce qui est un bel exemple de formulation qu'on est bien embêté pour noter quand on corrige des copies d'examen, parce que c'est ambigu à souhait.

Et la formulation alambiquée de l'axiome de fondation à la fin, c'est juste une initiative personnelle (réussie) pour amuser les lecteurs du blog, ou c'est effectivement utilisé quelque part sous cette forme ? (Note pour monsieur Ghalys, il y a un axiome pas forcément enseigné dans toutes les universités qui dit que "monsieur Madore ne se trompe jamais").

Ghalys (2003-10-21T11:53:11Z)

Je comprends tes pauvres élèves!
Tu utilises à mon humble avis beaucoup trop de parenthèses et pas assez d'espaces:
( P(0) ∧ (∀n, P(n)⇒P(n+1)) ) ⇒ (∀n, P(n))
est plus compréhensible que:
((P(0))∧((∀n)((P(n))⇒(P(n+1)))))⇒((∀n)(P(n)))

De même les profs qui sont gentils avec leurs élèves utilisent une convention de notation presque canonique qui dit que "on utilise des majuscules pour les ensembles et des minuscules pour les éléments de l'ensemble".
Ainsi :
( ∀X, ∀Y, Y⊆X ⇒ ( (∀Z, Z∈X⇒( (∀t, t∈X⇒(t∈Z⇒t∈Y)) ⇒ Z∈Y )) ⇒ Y=X ) )
est un peu mieux que:
(∀x)(∀y)((y⊆x)⇒(((∀z)((z∈x)⇒(((∀t)((t∈x)⇒((t∈z)⇒(t∈y))))⇒(z∈y))))⇒(y=x)))

Tu te serais ainsi apercu que tu t'es trompé et que tu voulais écrire :
(∀x)(∀y)((y⊆x)⇒(((∀z)((z⊆x)⇒(((∀t)((t∈x)⇒((t∈z)⇒(t∈y))))⇒(z⊆y))))⇒(y=x)))

Mais bon, tu as le droit de choisir tes propres et non canoniques conventions de notation…

Anonymous Coward #164 (DH) (2003-10-21T11:24:47Z)

Je me souviens. La première fois qu'on m'a parlé de récurrence, c'était en première S, et la prof en avait donné une description purement algorithmique, sans dire pourquoi ça marchait. Ca me semblait mystérieux, surtout l'hypothèse d'initialisation. puis, En TS, on a eu une meilleure prof de maths (l'autre ne savait pas démontrer la formule du trinôme du second degré sans ses notes !), et elle nous a tout expliqué, sans faire de logique compliquée, et c'est rentyré tout seul. Tu as essayé l'explication "intuitive" (Si P_0 vrai, alors P_1 vrai. Si P_1 vrai, alors P_2, etc…)
?

Matoo (2003-10-21T09:16:53Z)

Salaud de PROF !!!!

(lol)


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: 015e04


Recent comments