“Induction qu'est ce que c¸a veut dire et pourquoi s'y interesser Ensuite quelques rappels sur la theorie des ensembles

Description

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

• 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

Sujets

• Paradoxe de Russell

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 42
• Langue: Français

Extrait

Chapitre 0

Remarquespr´eliminaires

“Induction:”qu’estcequec¸aveutdireetpourquois’yinte´resser?Ensuite quelquesrappelssurlathe´oriedesensembles.

0.1 Qu’entendonpar “induction”?

Lemot“induction”estutilise´dansdessensdiff´erents.

Tradition logicophilosophique.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.amrofninronsuned´efinitiooCsndie´ tiqueclassiquer´ecursivedelafonctionfactorielle: fact(n) =six= 0alors1sinonn∗fact(n−1) •utvecae¸qucetescafrinfie´dederidd’ellemtentermeq’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)

•ectse’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 (coinduction) •epsdgrroi´pr´eetdnoiorpesnomtartsmeda´me

0.3Rappelsdethe´oriedesensembles

Appartenance :c’est le concept primitif. On l’exprime par des formules atomiquesx∈A.Ce’tsuscrcenoectpaltiurtsnocno’uqnsedeieor´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