La lecture en ligne est gratuite
Télécharger
Chapitre 0
Remarquespr´eliminaires
Induction:questcequec¸aveutdireetpourquoisyinte´resser?Ensuite quelquesrappelssurlathe´oriedesensembles.
0.1 Qu’entendonpar “induction”?
Lemotinductionestutilise´dansdessensdi´erents.
Tradition logicophilosophique.ec,altsge`rellilssoygdLemeisArteto dinf´erenceModusPonens: PQ P Q Ilyaplusieursfa¸consdexploitercetter`egle:
d´eduction:para`eitdrPetPQtiudoe´dnQ. C’est la formulation (de´rivation)denouvellesconclusions. abduction :si on sait quePQet qu’on observeQ, alors on pourrait for mulerlhypoth`esePpour expliquer l’observation. C’est la formulation dhypoth`eses. induction :si chaque fois qu’on observeP, on observeQaussi, on peut formulerlhypoth`esescientiquequeledomaineobe´ita`laloiPQ. Cestlaformulationdere`glesg´ene´ralisantes:apprentissage,IA.
Cesensdumotinductionnestpasceluiauquelonsinte´resseradansce cours.
1
Traditionmath´ematique.
onconnaitlanotiondere´currence:
e´rrrrucecneius(s)ted´enitionpa ra´roipnercncerue:´ednsmoattr P(0) ⇒ ∀nNP(n) P(n)P(n+ 1)
Onpeutr´eexaminerlanotiondere´currencedansuncadreplusg´en´eral:celui delinduction.Cest`acesensdumotinductionquonvasint´eresser.
0.2Pourquoisyinte´resser?
De´nitionr´ecursivedefonction.amrofninronsuned´enitiooCsndie´ tiqueclassiquer´ecursivedelafonctionfactorielle: fact(n) =six= 0alors1sinonnfact(n1) utvecae¸qucetescafrine´dederiddellemtentermequeˆem? astpefunitcresntuoTlpuatcno!noiuqoane´ecetssuc,csiraledption d’un algorithme pour calculer les valeurs qu’une certaine fonction prend`achaquepointdesondomaine. oralusqleeltlesd`asponorrequiceuqitame´htamnoictonefbltari´eav cet algorithme? lpep:raxemefonctionsdecette´irpe´teedreorpsrpoiuvroutpeulvono qu’elle calcule bien la factorielle de son argument!
D´enitioninductivedetypes.´neestdentyessdpeonedoitunesilvuos de´nisdemani`ereinductive.Parexemples,leslistesdentiers:
type IntList = nil | int :: IntList
ou sa version polymorphique :
type List(a) = nil | a :: List(a)
ectseuevac¸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 atomiquesxA.Cetsuscrcenoectpaltiurtsnocnouqnsedeieor´eth sembles.
Axiome d’extension ::e´ge´tilanitld´eA=Bssix(xAxB) ABssix(xAxB) A=BssiABBA
Axiomedesp´ecication:si on a un ensembleAericadinatuunet´epr P, alors on peut former un nouvel ensembleBna`ilemade:ntvauieser
B={xA|P(x)}
Danslape´riodepre´axiomatiquedelath´eoriedesensembles,ontenaitpour ´evidentlexistencedununiversUest,cleustodesnuerida`elbmesne ensembles.Unecons´equencedelaxiomedesp´ecication,cestquecelanest pas possible. C’est le paradoxe de Russell : Supposons qu’il existe un ensembleUcontenant tous les ensembles. Alors, selonlaxiomedesp´ecication,enprenantA=UetP(x)x6∈x, on peut construire l’ensembleBsuivant : B={S|∈ US6∈S} Mais,commevouspouvezleve´rierenutilisantlade´nitiondeB, cet ensembleBrp´itee´eisupeoralacur: BBB6∈B
3
Donclhypothe`sedelexistencedeUdona.Oontiicadtrcncenoa`nue`enma prouve´,parlabsurde,quuntelUne peut pas exister. Toutecollectiondensemblesnestpasne´cessairementunensemble.Certaines collections sont plus vastes que des ensembles. Ce ne sont pas des ensembles;donconnepeutpasleurappliquere.g.laxiomedespe´cication pourconstruiredenouveauxensembles.One´viteainsileparadoxedeRussell.
Commentde´marrer?ta´hoeirdeseneesmbleonabesoinposirloiavur duneinexplicablecollection,onnapasbeaucoupavance´!Aulieudecela, on pose l’axiome suivant :
il existe un ensemble
Appelons cet ensembleAsuonA,.noolale`xia,grsacrˆiceitacdemo´pse pouvonsde´nirlensembleBsuivant :
B={xA|x6=x}
Best vide. Donc il existe un ensemble vide, qu’on noteraet on peut en prouverlunicit´egraˆcea`laxiomedextension.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´enirlintersectionABet l’unionABalement,siern´´esglu.PSest un ensemble d’ensembles, on pose : S={x| ∃AS, xA} S={x| ∀AS, xA}
Ensemble des parties d’un ensemble.(powerset) P(A) ={B|BA} A Au lieu deP(A.t2soitenuvno)rce´
Paireordonne´e.formelletd´eniropnueeen´onrdeoirapednoitonaltnem (a, bionenited´ecette,rpmilruis.)oPomsteiis.ci
4