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

Publié par

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


Publié le : mercredi 30 mai 2012
Lecture(s) : 34
Source : univ-orleans.fr
Nombre de pages : 5
Voir plus Voir moins
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
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi