Formulations équivalentes du raisonnement par récurrence.

pseudoarallonge · 30/10/2014, 12h25

Bonjour,

Une discussion sur un autre fil a aboutit à une série de formulations du raisonnement par récurrence.

En particulier il a été avancé que

$\text{[math]}$

serait équivalent à dire que

Toute partie non vide de $\text{[math]}$ admet un plus petit élément.

Merci par avance à tous ceux qui pourront infirmer ou confirmer cette équivalence.

**Médiat** · 30/10/2014, 12h36

La première formulation est purement syntaxique, c'est l'axiome de récurrence qui fait partie des axiomes de Peano (par exemple), la seconde formulation est purement sémantique et concerne le modèle $\text{[math]}$ , ces deux formulations ne peuvent être équivalentes pour un théorie incomplète.

Par exemple le modèle (au sens de la relation d'ordre évidente) $\text{[math]}$ vérifie bien la deuxième condition, mais pas forcément la première.

**Amanuensis** · 30/10/2014, 12h41

Envoyé par Médiat

Par exemple le modèle (au sens de la relation d'ordre évidente) $\text{[math]}$ vérifie bien la deuxième condition, mais pas forcément la première.

? Quel est le plus petit élément de $\text{[math]}$ ?

(peut-être un problème de parenthésage?)

**Médiat** · 30/10/2014, 12h43

Il n'y en a pas, mais ce n'est pas contradictoire avec la formulation 1 qui ne parle que de $\text{[math]}$

A voir en vidéo sur Futura · Aujourd'hui

**Amanuensis** · 30/10/2014, 12h45

OK ; j'avais compris que N était remplacé par le nouvel ensemble dans la seconde assertion...

(Le mode de pensée en termes de modèle ne m'est pas naturel, et il est possible que ce soit le cas d'autres lecteurs.)

**Médiat** · 30/10/2014, 12h51

Envoyé par Amanuensis

OK ; j'avais compris que N était remplacé par le nouvel ensemble dans la seconde assertion...

Le résultat serait "pire", car il faudrait faire appel à la logique du 2nd ordre, alors que l'axiome de récurrence est du 1er ordre.

**Amanuensis** · 30/10/2014, 12h55

@pseudo-à-rallonge

Envoyé par pseudoarallonge

Merci par avance à tous ceux qui pourront infirmer ou confirmer cette équivalence.

Pas pour montrer une équivalence, mais juste un rapport entre les deux.

On peut "démontrer" le raisonnement par récurrence (attention aux " ") par l'absurde comme suit:

On suppose que le sous-ensemble $\text{[math]}$ est non vide. Il a un plus petit élément. Soit ce plus petit élément est 0, contradiction; soit il n'est pas nul, on le note k. k-1 existe, et est tel que P(k-1) est vrai par hypothèse, et on a donc $\text{[math]}$ , contradiction.

pseudoarallonge · 30/10/2014, 13h23

Envoyé par Amanuensis

Pas pour montrer une équivalence, mais juste un rapport entre les deux.

Une équivalence, c'est $\text{[math]}$ , mais un rapport je ne vois pas ce que cela signifie. Est ce une implication ?

Envoyé par Amanuensis

On suppose que le sous-ensemble $\text{[math]}$ est non vide.

Un proposition a le même statut qu'un élément ? Comment comprendre $\text{[math]}$ ? Cela signifie-t-il : Toute proposition est fausse?

Envoyé par Amanuensis

Il a un plus petit élément. Soit ce plus petit élément est 0, contradiction;

Pourquoi ?

Envoyé par Amanuensis

soit il n'est pas nul, on le note k. k-1 existe, et est tel que P(k-1) est vrai par hypothèse, et on a donc $\text{[math]}$ , contradiction.

OK...

**Amanuensis** · 30/10/2014, 13h38

Envoyé par pseudoarallonge

Une équivalence, c'est $\text{[math]}$ , mais un rapport je ne vois pas ce que cela signifie. Est ce une implication ?

Non, juste une piste, une raison, pourquoi quelqu'un a cité la notion de plus petit élément d'un s.e. de N en relation avec la démo par récurrence.

Comment comprendre $\text{[math]}$ ? Cela signifie-t-il : Toute proposition est fausse?

Non, juste P est faux pour n.

Pourquoi ?

Paraît plus évident que l'autre branche!

**PlaneteF** · 30/10/2014, 14h55

Envoyé par Médiat

La première formulation est purement syntaxique, c'est l'axiome de récurrence qui fait partie des axiomes de Peano (par exemple), la seconde formulation est purement sémantique et concerne le modèle $\text{[math]}$ , ces deux formulations ne peuvent être équivalentes pour un théorie incomplète.

Oui, ... dans l'autre fil tu parlais de "discutable" et je ne voyais alors pas ce que tu voulais dire par là, ... Donc maintenant OK, il s'agit plus d'une précision par rapport au sous-entendu classique ^(*) comme quoi l'on travaille dans $\text{[math]}$ . D'ailleurs j'ai failli mettre aussi la formulation du raisonnement par récurrence, auquel cas j'aurais précisé dedans $\text{[math]}$ et c'est dans ce cadre que je parlais d'équivalence. Maintenant cela n'enlève en rien l'intérêt de ta précision

^(*) sous-entendu que l'on ne fait effectivement pas lorsque l'on travaille par exemple sur les différents modèles de l'arithmétique auquel cas on fait le distinguo entre le modèle standard et les modèles non-standards.

Cordialement

**Médiat** · 30/10/2014, 15h04

Envoyé par PlaneteF

dans l'autre fil tu parlais de "discutable"

Oui, je voulais bien dire "dont on peut discuter", et non pour dire que c'était faux, bref comme quasi synonyme de ... pinaillage

j'aurais précisé dedans $\text{[math]}$

Et ce n'est pas un hasard si je ne l'ai pas fait

Le modèle (pour <) que j'ai proposé est typiquement un modèle non-standard (de <).

pseudoarallonge · 30/10/2014, 18h01

Oh punaise! Ce n'est pas évident.
Ce n'est pas évident de voir le rapport entre une proposition qui est faite sur un ensemble de n éléments, P(n) et l'ensemble lui-même...

Si je suppose la proposition P(n) suivante vrai: Un ensemble de cardinal n a n! permutations.
Si j'ai montré que la proposition implique que P(n+1) est vrai : Un ensemble de cardinal n+1 a (n+1)! permutations.

Qu'est ce qui dit que l'ensemble admet un plus petit élément ?!

**PlaneteF** · 30/10/2014, 19h15

Envoyé par pseudoarallonge

Qu'est ce qui dit que l'ensemble admet un plus petit élément ?!

Si l'ensemble dont tu parles est bien une partie de $\text{[math]}$ , si $\text{[math]}$ il n'admet aucun $\text{[math]}$ , sinon il en admet un (et un seul bien sûr).

Qu'est-ce qui permet de le dire ? ... Ben la proposition (admise ou démontrée, c'est selon) dont on parle depuis le début !

Cdt

pseudoarallonge · 30/10/2014, 19h19

Envoyé par Amanuensis

On peut "démontrer" le raisonnement par récurrence (attention aux " ") par l'absurde comme suit:

On suppose que le sous-ensemble $\text{[math]}$ est non vide. Il a un plus petit élément. Soit ce plus petit élément est 0, contradiction; soit il n'est pas nul, on le note k. k-1 existe, et est tel que P(k-1) est vrai par hypothèse, et on a donc $\text{[math]}$ , contradiction.

Je me permets de reprendre votre démonstration sur un cas concret:
P(n): Un ensemble E de cardinal n a n! permutations.
Soit n=3
$\text{[math]}$ : Un ensemble E de cardinal n n'a pas n! permutations.

Si E={0,1,2} le plus petit élément est 0. En quoi cela engendre une contradiction ?

Si E={2,3,4} k=2 donc k-1 existe.
Pourquoi P(k-1) est vrai ?

**gg0** · 30/10/2014, 21h36

Bonsoir.

Ce n'est pas sur E que porte l'explication de Amanuensis.
Soit G l'ensemble des entiers n pour lesquels P(n) est faux (donc pour lesquels il existe un ensemble à n éléments qui n'a pas n! permutations). G a un plus petit élément p (donc p est dans G)
Soit p=0, ce qui est impossible car un ensemble à 0 éléments (l'ensemble vide) a 0!=1 permutation (la permutation vide, qui est l'application vide)
Soit p>0; alors p a un prédécesseur p-1 qui n'est donc pas dans G. Mais l'hérédité (dans la preuve par récurrence) montre que puisque P(p-1) alors P(p-1+1). Contradiction, puisque P(p) est fausse et vraie.

Cordialement.

NB : Ce qui est au dessus est écrit sans rigueur pour permettre la compréhension.

**PlaneteF** · 30/10/2014, 21h38

Envoyé par pseudoarallonge

P(n): Un ensemble E de cardinal n a n! permutations.
Soit n=3
$\text{[math]}$ : Un ensemble E de cardinal n n'a pas n! permutations.

Si E={0,1,2} le plus petit élément est 0. En quoi cela engendre une contradiction ?

Si E={2,3,4} k=2 donc k-1 existe.
Pourquoi P(k-1) est vrai ?

Tu mélanges tout là. Dans la démonstration on applique la propriété sur le $\text{[math]}$ à l'ensemble $\text{[math]}$ , ... donc dans ton exemple cela n'a rien à voir avec l'ensemble $\text{[math]}$ dont tu parles.

Dans cette démonstration ce que l'on veut montrer c'est le résultat final du raisonnement par récurrence, à savoir $\text{[math]}$ . L'idée c'est alors de dire que cela est équivalent à démontrer que l'ensemble $\text{[math]}$ , ... démonstration faite par l'absurde.

Cordialement

pseudoarallonge · 30/10/2014, 22h02

Merci gg0 et PlaneteF,
Capito.
Je n'aurais jamais pu comprendre sans votre aide conjointe.

**PlaneteF** · 30/10/2014, 22h06

Envoyé par pseudoarallonge

Merci gg0 et PlaneteF,
Capito.
Je n'aurais jamais pu comprendre sans votre aide conjointe.

Hep, hep, hep, ... ce n'est pas fini, ce n'est que la moitié du chemin ! ...

Maintenant il faut démontrer la réciproque, à savoir : "Raisonnement par récurrence" => "Toute partie non vide de N admet un ppe."

A toi de jouer

Cordialement

**Médiat** · 31/10/2014, 04h52

A noter que si on ne parle que de $\text{[math]}$ , donc quand les deux formulations sont supposées équivalentes (et je n'en suis pas certain), la récurrence parle d'un nombre dénombrable de sous-ensembles de $\text{[math]}$ , alors que l'autre formulation parle d'un nombre non dénombrable de sous-ensembles de $\text{[math]}$ .

**Médiat** · 31/10/2014, 06h52

Bonjour,

Je ré-écris la démonstration dans le sens "tout sous ensemble non vide possède un plus petit élément entraîne le schéma de récurrence tel qu'énoncé dans le message #1" sans préciser "sous ensemble de $\text{[math]}$ " pour éviter le contrexemple du message #2 :

Soit $\text{[math]}$ une formule avec une variable libre qui vérifie :
$\text{[math]}$
$\text{[math]}$

Soit $\text{[math]}$ ( $\text{[math]}$ est l'ensemble des valeurs tels que $\text{[math]}$ est fausse)

Si $\text{[math]}$ , alors $\text{[math]}$ cqfd

Si $\text{[math]}$ , alors $\text{[math]}$ possède un plus petit élément, que nous noterons $\text{[math]}$ ,
$\text{[math]}$ , car on ne peut avoir conjointement $\text{[math]}$ (hypothèse 1) et $\text{[math]}$
donc $\text{[math]}$ tels que $\text{[math]}$ (puisque $\text{[math]}$ en effet $\text{[math]}$ ) et $\text{[math]}$ (puisque $\text{[math]}$ ce qui est contradictoire avec l'hypothèse 2. cqfd

Dans l'autre sens, je ne sais pas faire.

pseudoarallonge · 31/10/2014, 08h00

Bonjour,

Je me permets de reprendre votre démonstration (dans ce sens) en la commentant à ma sauce.

Soit $\text{[math]}$ une formule avec une variable libre qui vérifie :
$\text{[math]}$
$\text{[math]}$

On part de ces deux assertions, OK.

Soit $\text{[math]}$ ( $\text{[math]}$ est l'ensemble des valeurs tels que $\text{[math]}$ est fausse)

La définition de cet assemble m'a pas mal posé de problèmes. Si je le ré-éecris en reprenant mon exemple des permutations alors $\text{[math]}$

Si $\text{[math]}$ , alors $\text{[math]}$ cqfd

Si l'ensemble est vide, alors aucune proposition n'est fausse, donc elles sont toutes vraies. Ici, on a plus que ce qui est demandé, puisque $\text{[math]}$ et non pas $\text{[math]}$

Si $\text{[math]}$ , alors $\text{[math]}$ possède un plus petit élément, que nous noterons $\text{[math]}$ ,
Je comprends ici le choix judicieux de la notation.

$\text{[math]}$ , car on ne peut avoir conjointement $\text{[math]}$ (hypothèse 1) et $\text{[math]}$
D'accord

donc $\text{[math]}$ tels que $\text{[math]}$ (puisque $\text{[math]}$ en effet $\text{[math]}$ ) et $\text{[math]}$ (puisque $\text{[math]}$ ce qui est contradictoire avec l'hypothèse 2. cqfd

L'hypothèse 2 implique que $\text{[math]}$ soit $\text{[math]}$ . Cependant $\text{[math]}$ mais $\text{[math]}$ donc $\text{[math]}$ . D'où la contradiction.

La démonstration se fait entièrement dans le cadre de la logique finalement.

**Médiat** · 31/10/2014, 08h23

Bonjour,

Soit $\text{[math]}$ ( $\text{[math]}$ est l'ensemble des valeurs tels que $\text{[math]}$ est fausse)

La définition de cet assemble m'a pas mal posé de problèmes. Si je le ré-éecris en reprenant mon exemple des permutations alors $\text{[math]}$

Oui

Si $\text{[math]}$ , alors $\text{[math]}$ cqfd

Si l'ensemble est vide, alors aucune proposition n'est fausse, donc elles sont toutes vraies. Ici, on a plus que ce qui est demandé, puisque $\text{[math]}$ et non pas $\text{[math]}$

Faute de frappe de votre part, j'ai bien écrit $\text{[math]}$

donc $\text{[math]}$ tels que $\text{[math]}$ (puisque $\text{[math]}$ en effet $\text{[math]}$ ) et $\text{[math]}$ (puisque $\text{[math]}$ ce qui est contradictoire avec l'hypothèse 2. cqfd

L'hypothèse 2 implique que $\text{[math]}$ soit $\text{[math]}$ . Cependant $\text{[math]}$ mais $\text{[math]}$ donc $\text{[math]}$ . D'où la contradiction.

J'écrirais plutôt : L'hypothèse 2 implique que $\text{[math]}$ or $\text{[math]}$ et $\text{[math]}$ . D'où la contradiction

La démonstration se fait entièrement dans le cadre de la logique finalement.

Personnellement, je n'en connais pas d'autre.

**PlaneteF** · 31/10/2014, 09h44

Bonjour,

Pour démontrer par récurrence que "Toute partie non vide de $\text{[math]}$ admet un ppe." :

Soit $\text{[math]}$ une partie de $\text{[math]}$ n'admettant pas de ppe. On peut alors montrer que nécessairement $\text{[math]}$

Pour ce faire on peut démontrer par récurrence simple que : $\text{[math]}$

Cordialement

**Médiat** · 31/10/2014, 09h49

Bonjour,

Envoyé par PlaneteF

Pour ce faire on peut démontrer par récurrence simple que : $\text{[math]}$

Justement, je ne sais pas démontrer proprement (et de toute façon en dehors de $\text{[math]}$ , c'est impossible) $\text{[math]}$ dès que $\text{[math]}$ n'est pas un ensemble définissable (et comme je l'ai fait remarquer dans mon message #19, il y en a des tonnes).

Il me semble qu'à un moment ou à un autre il faut introduire du 2nd ordre.

**PlaneteF** · 31/10/2014, 10h03

Envoyé par Médiat

Justement, je ne sais pas démontrer proprement (et de toute façon en dehors de $\text{[math]}$ , c'est impossible) $\text{[math]}$ dès que $\text{[math]}$ n'est pas un ensemble définissable (et comme je l'ai fait remarquer dans mon message #19, il y en a des tonnes).

Je ne connais pas suffisamment ce concept d'ensemble définissable pour voir l'impact que cela a sur le raisonnement par récurrence classique qu'il s'agit de faire ici ?!

Cordialement

**Médiat** · 31/10/2014, 10h22

En fait, je ne vois même pas comment écrire "tout sous-ensemble de $\text{[math]}$ admet un plus petit élément" sans faire intervenir du 2nd ordre.

Là où je n'ai aucune restriction c'est concernant l'équivalence entre "tout sous-ensemble admet un plus petit élément" et la récurrence du second ordre.

C 'est à dire entre (j'utilise les conventions usuelles : les majuscules représentent des ensembles, les minuscules représentent des éléments):

$\text{[math]}$

et

$\text{[math]}$

**PlaneteF** · 31/10/2014, 10h36

Envoyé par Médiat

En fait, je ne vois même pas comment écrire "tout sous-ensemble de $\text{[math]}$ admet un plus petit élément" sans faire intervenir du 2nd ordre.

Là où je n'ai aucune restriction c'est concernant l'équivalence entre "tout sous-ensemble admet un plus petit élément" et la récurrence du second ordre.

C 'est à dire entre (j'utilise les conventions usuelles : les majuscules représentent des ensembles, les minuscules représentent des éléments):

$\text{[math]}$

et

$\text{[math]}$

Tu parlais dans ton message précédent d' "ensemble définissable" et de restriction par rapport à cela. Quel est le lien avec le message en citation ?

Cdt

**Médiat** · 31/10/2014, 10h42

En logique du premier ordre on ne peut parler (écrire des formules) que pour des éléments, ou des ensembles définissables, c'est à dire, définis par une formule (n'utilisant que des éléments) ; en logique du 2nd ordre on peut écrire des formules avec tous les sous-ensembles (la notion de "tous" ici est moins simple qu'il n'y paraît, mais comme j'utilise la même logique dans mes deux formulations, il ne peut pas y avoir de problème, les sous-ensembles considérés sont forcément les mêmes).

En logique du 1er ordre l'équivalence est démontrable si on précise "tous sous ensemble définissable admet un plus petit élément".

**PlaneteF** · 31/10/2014, 12h37

@Médiat : OK, merci pour ces précisions

Cdt

Formulations équivalentes du raisonnement par récurrence.

Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Re : Formulations équivalentes du raisonnement par récurrence.

Discussions similaires

Raisonnement par récurrence.

raisonnement par récurrence

Raisonnement par récurrence

Raisonnement par récurrence TS

Raisonnement par récurrence