“Induction qu'est ce que c¸a veut dire et pourquoi s'y interesser Ensuite quelques rappels sur la theorie des ensembles
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Niveau: Supérieur
Chapitre 0 Remarques preliminaires “Induction :” qu'est-ce que c¸a veut dire et pourquoi s'y interesser ? Ensuite quelques rappels sur la theorie des ensembles. 0.1 Qu'entend-on par “induction” ? Le mot “induction” est utilise dans des sens differents. Tradition logico-philosophique. Le syllogisme d'Aristote, c'est la regle d'inference “Modus Ponens” : P ? Q P Q Il y a plusieurs fac¸ons d'exploiter cette regle : deduction : a partir de P et P ? Q on deduit Q. C'est la formulation (derivation) de nouvelles conclusions. abduction : si on sait que P ? Q et qu'on observe Q, alors on pourrait for- muler l'hypothese P pour expliquer l'observation. C'est la formulation d'hypotheses. induction : si chaque fois qu'on observe P , on observe Q aussi, on peut formuler l'hypothese scientifique que le domaine obeit a la loi P ? Q. C'est la formulation de regles generalisantes : apprentissage, IA. Ce sens du mot “induction” n'est pas celui auquel on s'interessera dans ce cours. 1
Voir
Chapitre 0 Remarques preliminaires “Induction :” qu'est-ce que c¸a veut dire et pourquoi s'y interesser ? Ensuite quelques rappels sur la theorie des ensembles. 0.1 Qu'entend-on par “induction” ? Le mot “induction” est utilise dans des sens differents. Tradition logico-philosophique. Le syllogisme d'Aristote, c'est la regle d'inference “Modus Ponens” : P ? Q P Q Il y a plusieurs fac¸ons d'exploiter cette regle : deduction : a partir de P et P ? Q on deduit Q. C'est la formulation (derivation) de nouvelles conclusions. abduction : si on sait que P ? Q et qu'on observe Q, alors on pourrait for- muler l'hypothese P pour expliquer l'observation. C'est la formulation d'hypotheses. induction : si chaque fois qu'on observe P , on observe Q aussi, on peut formuler l'hypothese scientifique que le domaine obeit a la loi P ? Q. C'est la formulation de regles generalisantes : apprentissage, IA. Ce sens du mot “induction” n'est pas celui auquel on s'interessera dans ce cours. 1
- paradoxe de russell
- consequence de l'axiome de specification
- ?a ?
- techniques d'induction et de point fixe
- paire ordonnee
- demonstration de proprietes de programmes
- axiome de specification
- formulation de regles generalisantes
Chapitre 0
Remarquespr´eliminaires
“Induction:”qu’estcequec¸aveutdireetpourquois’yinte´resser?Ensuite quelquesrappelssurlathe´oriedesensembles.
0.1 Qu’entendonpar “induction”?
Lemot“induction”estutilise´dansdessensdiff´erents.
Tradition logicophilosophique.e’c,altsge`rellilssoygdL’emeisArteto d’inf´erence“ModusPonens”: P⇒Q P Q Ilyaplusieursfa¸consd’exploitercetter`egle:
d´eduction:para`eitdrPetP⇒Qtiudoe´dnQ. C’est la formulation (de´rivation)denouvellesconclusions. abduction :si on sait queP⇒Qet qu’on observeQ, alors on pourrait for mulerl’hypoth`esePpour expliquer l’observation. C’est la formulation d’hypoth`eses. induction :si chaque fois qu’on observeP, on observeQaussi, on peut formulerl’hypoth`esescientifiquequeledomaineobe´ita`laloiP⇒Q. C’estlaformulationdere`glesg´ene´ralisantes:apprentissage,IA.
Cesensdumot“induction”n’estpasceluiauquelons’inte´resseradansce cours.
1
Traditionmath´ematique.
onconnaitlanotiondere´currence:
•e´rrrrucecneius(s)ted´efinitionpa •ra´roipnercncerue:´ednsmoattr P(0) ⇒ ∀n∈NP(n) P(n)⇒P(n+ 1)
Onpeutr´eexaminerlanotiondere´currencedansuncadreplusg´en´eral:celui del’induction.C’est`acesensdumot“induction”qu’onvas’int´eresser.
0.2Pourquois’yinte´resser?
De´finitionr´ecursivedefonction.amrofninronsuned´efinitiooCsndie´ tiqueclassiquer´ecursivedelafonctionfactorielle: fact(n) =six= 0alors1sinonn∗fact(n−1) •utvecae¸qucetescafrinfie´dederidd’ellemtentermeq’ueˆem? •astpefunitcresn’tuoTlpuatcno!noiuqo’ane´ece’tssuc,csiraledp tion d’un algorithme pour calculer les valeurs qu’une certaine fonction prend`achaquepointdesondomaine. •oralu’sqleeltlesd`asponorrequiceuqitame´htamnoictonefbltari´eav cet algorithme? •lpep:raxemefonctionsdecette´irpe´teedreorpsrpoiuvroutpeulvono qu’elle calcule bien la factorielle de son argument!
D´efinitioninductivedetypes.´neestdentyessdpeonedoitunesilvuos de´finisdemani`ereinductive.Parexemples,leslistesd’entiers:
type IntList = nil | int :: IntList
ou sa version polymorphique :
type List(a) = nil | a :: List(a)
•ectse’uevac¸euqtuqider? •raisonnement par induction structurelle (analyse par cas)
2
Plusge´n´eralement: fixe pour :
on utilisera les techniques d’induction et de point
•ntiq´emas:semmargorpedeu –fonctionnel (induction) –logique (coinduction) •epsdgrroi´pr´eetdnoiorpesnomtartsmeda´me
0.3Rappelsdethe´oriedesensembles
Appartenance :c’est le concept primitif. On l’exprime par des formules atomiquesx∈A.Ce’tsuscrcenoectpaltiurtsnocno’uqnsedeieor´eth sembles.
Axiome d’extension ::e´ge´’tilanitld´efi A=Bssi∀x(x∈A⇔x∈B) A⊆Bssi∀x(x∈A⇒x∈B) A=BssiA⊆B∧B⊆A
Axiomedesp´ecification:si on a un ensembleAericadinatuunet´epr P, alors on peut former un nouvel ensembleBna`ilemade:ntvauieser
B={x∈A|P(x)}
Danslape´riodepre´axiomatiquedelath´eoriedesensembles,ontenaitpour ´evidentl’existenced’ununiversU’est,cleustodesnuerida`elbmesne ensembles.Unecons´equencedel’axiomedesp´ecification,c’estquecelan’est pas possible. C’est le paradoxe de Russell : Supposons qu’il existe un ensembleUcontenant tous les ensembles. Alors, selonl’axiomedesp´ecification,enprenantA=UetP(x)≡x6∈x, on peut construire l’ensembleBsuivant : B={S|∈ US6∈S} Mais,commevouspouvezleve´rifierenutilisantlade´finitiondeB, cet ensembleBrp´itee´eisupeoralacur: B∈B⇔B6∈B
3
Doncl’hypothe`sedel’existencedeUdona.Oontiicadtrcncenoa`nue`enma prouve´,parl’absurde,qu’untelUne peut pas exister. Toutecollectiond’ensemblesn’estpasne´cessairementunensemble.Cer taines collections sont plus vastes que des ensembles. Ce ne sont pas des ensembles;donconnepeutpasleurappliquere.g.l’axiomedespe´cification pourconstruiredenouveauxensembles.One´viteainsileparadoxedeRus sell.
Commentde´marrer?ta´hoeirdeseneesmbleonabesoinposirloiavur d’uneinexplicable“collection”,onn’apasbeaucoupavance´!Aulieudecela, on pose l’axiome suivant :
il existe un ensemble
Appelons cet ensembleAsuonA,.noolale`xi’a,grsacrˆfiiceitacdemo´pse pouvonsde´finirl’ensembleBsuivant :
B={x∈A|x6=x}
Best vide. Donc il existe un ensemble vide, qu’on notera∅et on peut en prouverl’unicit´egraˆcea`l’axiomed’extension.PourtoutensembleAon a bien sur∅ ⊆A.
Singletons.neyorcedvuonmuaeonedunnensoS.insembles´eerdeseA est un ensemble, alors{A}est un ensemble.
Union et intersection.siAetBsont des ensembles, alors on peut en d´efinirl’intersectionA∩Bet l’unionA∪Balement,siern´´esglu.PSest un ensemble d’ensembles, on pose : ∪S={x| ∃A∈S, x∈A} ∩S={x| ∀A∈S, x∈A}
Ensemble des parties d’un ensemble.(powerset) P(A) ={B|B⊆A} A Au lieu deP(A.t2soitenuvno)rce´
Paireordonne´e.formelletd´efiniropnueeen´onrdeoirapednoitonaltnem (a, bionefinited´ecettefi,rpmilruis.)oPomsteiis.ci
4
