Base de l'ensemble des suites

Judoboy

Salut, on a un super théorème qui nous dit que tout espace vectoriel admet une base ; sauf que ça utilise l'axiome du choix et donc en règle générale on n'est pas capable d'expliciter une base. Par exemple l'ensemble des suites à valeurs dans R admet une base, mais je sais pas à quoi elle ressemble.


La question c'est est-ce que c'est réellement impossible d'en sortir une base explicite ? Si oui, est-ce qu'on peut démontrer ce fait ?

Question subsidiaire : est-ce que ces questions ont un sens ?

nicolas.patrois

Pour cet espace vectoriel, la base canonique convient, elle est dénombrable.

GreginGre

@NP: absolument pas. La base canonique permet de décrire les suites à support fini.

Comment écrirais-tu la suite constante $1$ comme combinaison linéaire finie d'élements de la base canonique ?

Alannaria

Une suite récurrente linéaire d’ordre p est à valeurs dans un corps commutatif K ($\mathbb C$ ou $\R$) définie pour tout $n \geq n_0$ par : $a_0, a_1, …a_{p-1}$ étant ''p'' scalaires fixés de K ($a_0$ non nul): $\forall n \geq n_0$, on a:$u_{n+p} = a_0u_n + a_1u_{n+1} + \cdots + a_{p-1}u_{n+p-1}$ et le polynôme caract. fixe le terme général.

Une telle suite est entièrement déterminée par la donnée des ''p'' premiers termes de la suite et par la relation de récurrence. Fibonacci est d'ordre 2...

omega

@ Alannaria : je ne vois pas bien le rapport avec la question posée...

FdP-HLM

Alannaria:

Explique moi comment tu transformes la suite des nombres premiers en une suite récurrente d'ordre p.
p étant un entier.

Alannaria

Justement, on vient d'expliciter un ensemble de suites à valeurs dans R admettant une base simplement identifiable car on sait à quoi elle ressemble.

FdP-HLM

Toutes les suites ne sont pas des suites récurrentes d'ordre p, p entier.

Une suite est une collection dénombrable (ce n'est pas un ensemble) de nombres qui sont indexés par un entier.
Ces nombres n'ont pas de lien entre eux, à priori, hormis celui d'être utilisés par la même suite.

Alannaria

Un ensemble peut être aussi une collection dénombrable d'entiers ordonnés en relation récurrente et on a déjà une suite récurrente peu utilisable en pratique de Minác et Willans des nombres premiers d'ordre k, k étant un entier naturel :$\pi(k) = \sum_{j=2}^k \left[ {(j-1)! + 1 \over j} - \left[{(j-1)! \over j}\right] \right]$

Bruno

FdP-HLM : a écrit:

ce n'est pas un ensemble

Là tu me gênes, une suite est une application de $\N$ dans un ensemble (voire une collection) ; c'est une conséquence du schéma de substitution.

Bruno

Fin de partie

Bruno:

Soit $(u_n)_{\N}$ une suite réelle. Ce que je voulais dire est que ce machin: "$\{u_n\text{ pour tout }n\text{ entier naturel positif} \}$" ressemble à un ensemble mais ce n'est pas un ensemble, à priori, car il peut exister deux indices $p,q$ tels que $u_p=u_q$

De la même manière:

"$\{1,2,2,3,4,5,6,7,8 \}$" n'est pas un ensemble car $2$ figure deux fois.

GreginGre

Pour répondre à Judoboy. Je pense que tes questions ont un sens. Voilà ce que j'ai compris de ta question, arrête-moi si je me trompe:

tu te demandes si le fait d'utiliser l'axiome du choix pour démontrer l'existence d'un truc implique forcément que l'on ne pourra jamais expliciter.

Pas forcément, les matheux qui font des maths constructives (et qui réfute la version forte de l'axiome du choix), passent une bonne partie de leur temps à trouver des démonstrations "constructives" (i.e. qui débouchent sur un algorithme de calcul de l'objet, en très gros).

En fait, des fois , l'axiome du choix est juste utilisé par commodité pour aller plus vite , et on peut trouver un substitut. Parfois, on démontre que le résultat recherché est vrai si et seulement si on admet l'axiome du choix (il me semble que l'existence d'ensembles non mesurables pour la mesure de Lebesgue en fait partie, ou l'existence d'idéaux maximaux pour les anneaux quelconques ).

Quant à l'exemple précis de l'espace des suites, j'avoue que je ne sais pas. Mais je doute que l'on puisse vraiment expliciter une base. Par exemple, ton espace contient toutes les restrictions de fonctions réelles définies sur $\R$, ça fait beaucoup trop.

Si tu t'intéresses à ce genre de questions , le bouquin de H. Herlich , "Axiom of choice" fait à peu près le tour de toutes les questions que l'on peut se poser sur ce sujet.

Raymond Cordier

Bon, c'est le marronnier, la base de $\R$ sur $\Q$, l'axiome de DuChoix, et tout ça. Cette base, Judoboy "ne sait pas à quoi elle ressemble". Ben, elle ressemble à toute base : $(h_{i})_{i\in I}$, l'ensemble $I$ étant pour le coup équipotent à $\R$. Ainsi dénommée ici en l'honneur de son immortel inventeur, Georg Hamel.
Quand une fonction est continue et que quel que soit $\varepsilon >0$ il existe $\alpha >0$ tel que etc., on ne sait pas non plus "à quoi il ressemble", cet $\alpha$, ça n'a jamais empêché personne de travailler avec, de le couper en 4 si besoin est, etc.
Vous qui faites des math, regardez dans votre expérience les exemples où vous avez établi que quelque chose existe, et qu'après vous avez travaillé librement avec cette chose, sans vous casser la tête à ce sujet. Et faites-nous en part.
Il en est de même pour les bases de Hamel.
Il paraît qu'on peut faire des mathématiques avec des espaces vectoriels qui n'auraient pas de base. Moi je veux bien, à mon âge, on a vu bien des choses, et j'ai maintes fois demandé ici qu'on me montre de telles mathématiques, des textes, des énoncés, des théorèmes, des résultats, des math quoi. Mais rien ne vient. J'attends toujours, avec patience ... mais un scepticisme croissant.
Bonne soirée.
RC
08/11/2013

GreginGre

@RC: on sait très bien que cette question te laisse froid, tu nous l'a bien fait comprendre plusieurs fois.

Je remarque néanmoins que ta réponse n'apporte rien à la discussion, sinon une nouvelle occasion de déverser ta bile.

Pour ta gouverne, heureusement que des mathématiciens ont eu plus de curiosité intellectuelle que toi: cela a permis de créer les maths constructives, qui sont très intéressantes et permettent d'éclairer d'un jour nouveau des preuves dites "classiques", et même de produire des preuves algorithmiques.

nicolas.patrois

GreginGre a écrit:

@NP: absolument pas. La base canonique permet de décrire les suites à support fini.

Je rouille. :)o

samok

ton erreur m'a fait comprendre la question.

S

Nîmes-man

La réponse de RC me semble sage. Je la reformule : non, Judoboy, tes questions n'ont pas de sens.

Pour donner un sens à tes questions, il suffirait de donner un sens au mot "explicite".

Greg l'a fait (et a donc donné un sens à tes questions) en proposant pour "explicite" le sens "dont la définition ne nécessite pas l'axiome du choix".

J'ai déjà eu l'occasion d'écrire que, d'après moi, ce recours ou pas à l'axiome du choix pour définir un objet est anecdotique. Un critère beaucoup plus discriminant est l'utilisation ou pas du tiers exclus.

Pour autant, je me garderais bien de qualifier de "non explicite" un objet dont la définition nécessite le tiers-exclus (ou l'axiome du choix) : je trouve ce mot "explicite" très mal choisi pour évoquer ces questions. Mais je ne vais pas répéter tout ce que j'ai écrit dans l'autre fil.

gerard0

On appelle ça "botter en touche".

La base canonique dont parlait Nicolas est explicite : Je sais quel est son cardinal et je suis capable de donner de façon compréhensible quel est son 1254852^ème élément.

Mais dans un autre fil, on a vu donner des sens différents au mot "explicite", des sens d'ailleurs peu explicites.

Les réponses qu'on a ici vont donc plutôt dans le sens d'une réponse "non" à la question qui est posée par Judoboy, celle qui a un sens ... en français courant.

Cordialement

Nîmes-man

J'imagine que ton message, gerard0, s'adresse à moi ?

J'ai bien compris à l'occasion de l'autre fil que tu ne partagais pas ma position, et tu y as détaillé la tienne de façon argumentée.

Je ne résiste pas tout de même à une question que m'inspire ton message : l'ensemble des nombres réels est-il explicite ? Si oui, quel est son 1254852^ème élément ?

gerard0

Non,

l'ensemble des réels n'est pas explicitable : On travaille de façon précise avec très peu de réels, il est même évident qu'on n'a travaillé qu'avec un nombre fini (et petit) de réels explicites.

Ce qui n'a rien à voir avec la question concrète posée par Judoboy.

Cordialement.

christophe c

de FdP Une suite est une collection dénombrable (ce n'est pas un ensemble) de nombres qui sont indexés par un entier.
Ces nombres n'ont pas de lien entre eux, à priori, hormis celui d'être utilisés par la même suite
...........
Ce que je voulais dire est que ce machin: "$\{u_n\text{ pour tout }n\text{ entier naturel positif} \}$" ressemble à un ensemble mais ce n'est pas un ensemble, à priori, car il peut exister deux indices $p,q$ tels que $u_p=u_q$. De la même manière:
"$\{1,2,2,3,4,5,6,7,8 \}$" n'est pas un ensemble car $2$ figure deux fois.

Deux erreurs (tu dois être fatigué, ça arrive, mais sois quand-même prudent, tu as été un peu péremptoire dans ta réponse):

1/ $\{1,2,2,3,4,5,6,7,8 \}$ est un ensemble et il est égal à $\{1,2,3,4,5,6,7,8 \}$ (et en principe, c'est mieux de séparer par des points-virgule, mais j'ai la flemme)

2/ La suite $u$ est un ensemble et c'est précisément $\{x \mid \exists n\in \N: x=\{\{n\}; \{n;u_n\}\}\}$

Pour info, $(a,b)=\{\{a\}; \{a;b\}\}$, mais ça, si tu veux tu peux l'oublier, c'est pas grave. Il y a des gens qui préfèrent considérer les couples comme des notions premières (mais c'est une autre affaire qui n'a rien à voir avec ce fil et concerne plus des recherches philo)

@judoboy: oui bien sûr que tes questions ont un sens, une fois un peu plus précisées:

tu te demandes si ZF démontre l'énoncé l'espace vectoriel des suites de nombres réels admet une base. Je continue de répondre aux autres, mais je réfléchirai pour te dire si la réponse est connue. Il y a peu de chance que ce soit oui, et beaucoup de chances que la réponse soit connue comme étant non (sous l'hypothèse de consistance de ZF). Dans le cas général, il est assez court de prouver que si tout espace vectoriel admet une base alors l'axiome du choix est vrai. Mais là, on a un espace particulier, et je dois prendre le temps de regarder si AD contredit qu'il a une base (je pense que oui, "au pied levé", mais ce n'est pas très sérieux, le pied levé)

de RCIl paraît qu'on peut faire des mathématiques avec des espaces vectoriels qui n'auraient pas de base. Moi je veux bien, à mon âge, on a vu bien des choses, et j'ai maintes fois demandé ici qu'on me montre de telles mathématiques, des textes, des énoncés, des théorèmes, des résultats, des math quoi. Mais rien ne vient. J'attends toujours, avec patience ... mais un scepticisme croissant.

Tu es de mauvaise foi, on t'a déjà dit où en trouver et je suis prêt à parier que tu n'es pas allé voir.

des textes, des énoncés, des théorèmes, des résultats, des math quoi dis-tu. Je vais être volontairement méchant, mais peux-tu:

1/ nous raconter quelles maths tu fais? On te voit régulièrement poster, (avec un soin parfaitement incontestable, j'en conviens!!) de sempiternels belles démonstrations classiques des parcours de taupin (parce que tu les as enseignées). Je crois que tu postes de temps en temps ici ou là un théorème de géométrie classique ou d'algèbre linéaire. Tu nous as aussi bcp gratifié de tes milles et unes formes de passions pour le fait que la moindre petite tendance à la continuité ou mesurabilité d'une fonction additive entrainait sa linéarité. Très bien. Peux-tu mettre des liens vers des maths que tu as faites (hors trucs d'annales) sur le forum qui nous ammèneraient vers des trucs un peu généraux et profonds (quels qu'ils soient)?

2/ Pourquoi, comme Greg te l'a dit, "cries-tu" (ou tonnes-tu?) toujours comme ça, pour balancer "un gout". Penses-tu que ton cri est convaincant?

3/ Qu'appelles-tu "faire des maths"?

4/ Pourquoi condamnes-tu les mathématiciens comme ça? (Si on te lit, on a l'impression que quelques calculs d'intégrales et un peu d'algèbre linéaire + 2 ou 3 raisonnements classiques d'analyse "infinie", typiquement de ceux enseignés dans les taupes sont les seules maths que "devraient" faire les chercheurs, je me trompe)

Pour info: j'allais te resignaler toute la richesse des résultats récents concernant ce domaine, puis je me suis ravisé à ne pas perdre 20mn d'exposé, vu ton engouement. Par ailleurs ton espèce de sous-entendu "l'axiome du choix est évident" (tu ne le dis pas, mais poste comme si tu le revendiquais) n'empèchera pas les gens de s'émouvoir de Banch-Tarski (dont je ne t'ai pas vu beaucoup parler).

Ouvre un fil si tu veux répondre en détails

Raymond Cordier

@ GreginGre
Non, aucun fiel de ma part, mais je me languis d'une réponse à ma question, que je re- re-repose : de grâce, donnez-moi des références à des mathématiques qui se feraient effectivement avec des espaces vectoriels qui n'auraient pas de base : des textes, des énoncés, des théorèmes, des résultats, des math quoi.
Je vais regarder l'ouvrage de H. Herrlich , "Axiom of choice", dès que Papa Noël me l'aura envoyé, ce qui ne saurait tarder.
Bonne nuit.
RC
08/11/2013

christophe c

@RC: il y a une spécialité entière qui gère*** l'analyse sans axiome du choix: la théorie descriptive des ensembles. Il y a un axiome alternatif, l'axiome de détermination*, qui fait gicler moult résultats plus vite que son ombre et qui, si tu étais patient, te passionnerait, comme il passionne tous les infinitistes. Cet axiome est parfaitement classique, parfaitement puissant et parfaitement opérant dans les questions d'analyse. Pour les références, google t'aidera un peu une BR, au bon rayon te comblera.

*** pour faire court, qui recense son inévitabilité, etc*****

** je t'en énonce une forme équivalente accessible à ta formation: pour toute partie $A$ de $\R^2$, il existe une application $f$ de $\R$ dans $\R$ telle que $f$ est continue sur $\R\setminus \Q$ et $f\subseteq A$ ou $f\cap A^*=\emptyset$, $A^*$ désignant l'ensemble des couples $(x,y)$ tels que $(y,x)\in A$

Rappel: $f = \{(x,y)\mid y=f(x) \}$

***** par exemple cette théorie est capable de prendre un "banal mais puissant théorème", comme celui de Hindman (+++) par exemple, puis d'éliminer de sa preuve l'utilisation de l'axiome du choix

(+++) Hindman dit que Pour tout couple d'ensembles $(A,B)$ tels que $A\cup B=\N$, il existe une partie $S$ de $\N$, qui est infinie et telle que: ((toutes les sommes d'éléments de S sont dans A) ou (toutes les sommes d'éléments de S sont dans A))

((toutes les sommes d'éléments de S sont dans A) ou (toutes les sommes d'éléments de S sont dans )

et se prouve en quelques lignes à grands renforts d'axiome du choix, mais se prouve de manière "horrible" sans l'axiome du choix.

enonce

Christophe C a écrit:

qui est infinie et telle que ((toutes les sommes d'éléments de S sont dans A) ou (toutes les sommes d'éléments de S sont dans A))

Il n'y aurait pas plutôt B, à la place de A dans la seconde assertion ?

christophe c

Oui bien sûr, pardon, les joies du copié-collé. Je corrige

christophe c

Pour en revenir à une remarque de Nimes man, il n'a pas tout à fait tort de signaler que l'axiome du raisonnement par l'absurde est tout autant, avec le recul du 20ième siècle, sulfureux que l'axiome du choix. Par contre, je serais très étonné que RC acceuille avec bienveillance des remises en cause du RPA

Remarque, je rappelle que AC=>RPA, je redonne la preuve: soit P un énoncé. Soit A l'ensemble des $x$ tels que $((x=0)$ ou $(x=1$ et $P))$. Soit B l'ensemble des $x$ tels que $((x=1)$ ou $(x=0$ et $P))$. Soit $f$ telle que $\forall U\in \{A;B\}: f(U)\in U$.

1) pour tout $U\in \{A;B\}: f(U)\in \{0;1\}$. Donc $f(A)=f(B)$ ou $f(A)\neq f(B)$

2) Si $f(A)=f(B)$ alors $0\in B$ ou $1\in A$, donc P

3) Si $f(A)\neq f(B)$ alors $(f(A)=f(B))$=>tout, donc P=>tout.

4) Conclusion: P ou (nonP)

Rappels: (dans la suite "théorème" signifie "théorème intuitionniste, ie énoncé ayant une preuve intuitionniste (n'utilisant pas d'axiomes du genre RPA, etc))

R1) le RPA, l'axiome non(non(X))=>X et le tiers exclus sont équivalents
R2) nonX est équivalent à X=>tout
R3) le fait que $\forall x,y$ dans $\{0;1\}: x=y$ ou $x\neq y$ n'utilise pas le tiers exclus évoqué en R1, car c'est un théorème particulier dont la preuve est rappelée ci-dessous en (**)
R3bis) $\{r;s\}$ est l'ensemble des $x$ tels que $x=r$ ou $x=s$
R4) Le fait que si (A=>C) et (B=>C) alors (A ou =>C (souvent appelé snobement raisonnemnt par cas) est un théorème et non un axiome (preuve rappelée en (***))


(**) $0=\emptyset$ et $1=\{0\}$. On a donc $0\neq 1$ car on a que (0=1)=>tout (en effet, on a que $(0\in 1$ et $0=1)$ entraine $0\in 0$ qui entraine tout par définition)

(***) A ou B est l'abréviation de ="pour tout Y: si A=>Y et B=>Y alors Y". Supposons que A=>C et B=>C et D. Alors, en particulier, si A=>C et B=>C alors C. Or comme A=>C et B=>C donc C.

Nîmes-man

RC a écrit:

donnez-moi des références à des mathématiques qui se feraient effectivement avec des espaces vectoriels qui n'auraient pas de base

Ça n'existe pas. Le but des constructivistes n'est pas de faire des maths différentes de celles que tu connais, mais de faire les mêmes maths que celles que tu connais tout en ayant des constructions algorithmiques effectives pour chaque objet.

Il ne s'agit pas de dire : "bon, l'espace des suites n'a pas de base, travaillons sur l'espace des suites sans base" ni même "bon, l'espace des suites n'a pas de base, ne travaillons pas sur l'espace des suites" mais plutôt "l'espace des suites que l'on considère doit avoir une base, peut-on reformuler nos définitions pour qu'on dispose bien d'un procédé algorithmique de construction de telles bases ?".

(Bien sûr, ma formulation ici est un peu naïve.)

Pour te donner un exemple simple : un anneau noethérien est un anneau dans lequel toute suite croissante d'idéaux stationne. Ceci se prête mal à un traitement constructif. Un constructiviste choisira plutôt la définition suivante : un anneau noethérien est un anneau dans lequel toute suite croissante d'idéaux de type fini pose (il existe n tel que $I_n=I_{n+1}$)". La seconde définition est, avec le formalisme classique, équivalente à la première, mais elle se prête mieux à un traitement algorithmique.

christophe c

Attention, ne pas confondre "mathématiques constructivistes" (que Nimes man décrit) et "mathématiques n'utilisant pas l'axiome du choix".

Les mathématiques sans l'axiome du choix sont la recherche de théorèmes démontrés dans ZF (ou dans ZF + certains axiomes intéressants en trant en violent conflit, par ailleurs, avec l'axiome du choix). L'axiome du RPA est accepté banalement.

Les "mathématiques constructivistes" (MC) sont décrites ci-dessus par Nimes man dans leur intention quotidienne. Il y a aussi les mathématiques intuitionnistes (MI) (qui sont encore différentes, mais pas trop en pratique des MC) , qui elles sont rigoureuses et fondées. Elles cherchent les théorèmes démontrés dans ZFI, c'est à dire ZF moins l'axiome du RPA

Les "constructivistes" (3) (ne doivent pas être confondus avec les "mathématiques intuitionnistes")

maths habituelles ---> formelles, bien définies
(MI) --> branche des maths, formelles, bien définies
(MC) ---> je ne sais pas, il y a un doute, mais il s'agit de l'objet d'étude pas de ceux qui l'étudient
(3) ---> il s'agit de ceux qui s'intéressent et pratiquent les MC. Il ne faut pas les confondre avec leur objet d'étude. Ils ont des préoccupations philosophiques, réunies sous le labl "constructivisme" (contrairement à l'intuitionnisme qui est purement mathématique et formel (:= logique classique moins axiome du RPA)

L'implication du RPA par l'AC fait qu'il est normal que l'AC soit rejeté par quiconque rejette le RPA. Cependant, il y a des choses prouvées avec l'AC qui sont tout à fait "constructives" au sens où le nommeraient des "constructivistes". L'utilisation d'un axiome dans une preuve n'implique pas sa nécessité dans d'autres preuves du même énoncé. Ca peut juste être un "accélérateur

Par ailleurs, des faits mal connus, hélas***, de ceux-là même qui se sont engagés sur le tard vers les MC (ou qui parlent même parfois des MI) sont que ces distinctions ne sont pas pertinentes (il est prouvable que ni le RPA ni l'AC ne sont "non constructifs sur le fond" + il est prouvable que moult raisonnements intuitionnistes (ou constructifs) conduisent à des conclusions tout autant non consrtuctives que celles qu'on reprochait au RPA ou à l'AC *****)

C'est donc une joyeuse boom où, bien souvent, selon le type de chercheur qu'on rencontre, on va avoir (et tant mieux) droit à un exposé pas seulement technique mais teinté de "prises de position" philosophiques (mais pour le coup, il ne s'agit pas de la philo invalide des philosophes, mais de choses quand-même assez sérieuses, toute proportion gardée)

Sinon, pour la vraie recherche concernant ce thème, elle est plus ou moins regroupée sous un label qui n'évoque pas de position subjective: correspondance de Curry Howard, qui elle-même contient plusieurs branches qui se sont développées, en France regroupées dans des labos dits de "théorie de la démonstration" ou des labos labellisés "informatique théorique".

En particulier, c'est la CorCuHo qui a démontré la stérilité de la distinction de fond entre maths intuitionnistes et maths classiques (et qui d'ailleurs l'a définie formellement), et a mis en lumière une distinction plus profonde et elle vraiment pertinente qui est l'utilisation ou non de l'axiome (A=>(A=>B))=>(A=>B), qui lui change tout

*** ceci étant dû au fait que ce sont souvent des mathématiciens qui ont eu leur vaillante vie propre en maths (hors logique), puis pour des raisons personnelles, de passion ou d'intérêt techniques se sont tournés, sur le tard, vers d'erronés textes anciens, n'ont pas pu caser (le temps nous est compté) de lecture de recherche récente logiques sur ces thèmes et ont développé des points de vue "autodidactes" (parfois très intéressants, mais handicapés par la séduction qu'avait eu sur eux la rhétorique des textes anciens)

***** C'est ce point (non connu, puis mal connu, puis volontairement mal connu parce que heurtant peut-être une espérance philosophique) qui explique la scission entre les "maths intuitionnistes" et "les maths constructivistes". Les MC espéraient dans un premier temps (probablement, je n'étais pas dans leur coeur) que les preuves des MI ne pouvaient que conduire à des conlusions constructives. Comme ce n'est pas le cas, il est probable qu'il ait fallu un "mot ex nihilo" pour labelliser "les gens qui cherchent à travailler dans des systèmes où ils se sentent sûrs que quoi que sera leur preuve dans ce système, elle ne pourra que conduire à une conclusion "constructive" (mot qui n'a jamais été défini et est laissé à l'appréciation populaire)

Rappels historiques de quelques théorèmes ou principes-clé et formels qui ont généré l'histoire précédente:

1) Théorème de Statman: la logique PROPOSITIONNELLE minimale est PSPACE-complète (c'est presque évident, mais l'énoncé est parlant), donc la logique intuitionniste aussi (la logique propositoinnelle classique "n'est que" CO-NP complète)
2) Si pour tout x: a.x = g(x.x) alors a.a = g(a.a)
3) Théorèmes de complétude en tout genre ---> adéquation syntaxe / sémantique qui se prouve toujours de la même façon

4) CorCuHO: une preuve est un programme qui s'exécute (théorèmes de réalisation)
4.1) Tous les axiomes s'exécutent** (y compris le RPA et l'axiome du choix ---> mort de la pertinence de la distinction attendue en espérant "accuser" le RPA et l'AC)
4.2) Réciproquement, il n'est pas trop dur d'avoir "tout programme prouve quelque chose", ie, "tout programme est une preuve" (c'est moins souvent évoqué, pour des raisons "politiques")


**Rappel de comment se réalise le RPA, c'est le "wanted" des western (dont le caractère non constructif devient alors tout à fait artificiel, sur le plan math, un "wanted" est tout aussi constructif que n'importe quel autre idée calculatoire): On veut garantir A sachant qu'on a une garantie G1 de (A=>B)=>A. On donne à G1 un "chèque sans provision" du montant "A=>B" (elle s'engage donc à nous rapporter A). Ou bien elle ne se sert pas du chèque et rapporte A, ou bien elle souhaite l'encaisser et va au guichet en fournissant A (et attendre du banquier une remise en nature de . On demande alors au guichetier de placer G1 sur off, et de nous ramener la valeur A. (En termes concrets, c'est une manière de capturer les criminels en leur proposant une récompense s'ils se rendent.

La traduction de ça en informatique existe depuis autant de temps que l'informatique elle-même et est autant "programmables" que n'importe quoi de "constructif": il s'agit de la commodité "try ... finally" ou encore "CallCC", qui e=permet à un programme d'essayer un truc, mais de rendre la main s'ils tentent d'accéder à tel label. Pour être plus précis, c'est une instruction qui fournit une "fausse fonction" bluff et qui, si elle est exécutée (donc un "bluf(toto)" est appelé) renvoie la valeur de la variable de la fonction bluf à l'appelant du programme (ie "bluf(toto)" déclenche un "enregistrer toto à tel endroit puis exit")

mister_jones

Je ne sais pas exactement ce que cherche Raymond Cordier quand il demande des exemples de mathématiques utilisant des espaces vectoriels qui n'auraient pas de base.

Dans mes recherches de tous les jours, je manie des espaces vectoriels (y compris de dimension finie), sans jamais parler de base. D'une part, parce qu'il n'y en a pas nécessairement de canonique, d'autre part parce que ça ne servirait à rien.
A ma connaissance, on ne considère jamais de base algébrique des espaces vectoriels de l'analyse, type L^p, Sobolev, fonctions continues... En géométrie, la notion de fibré vectoriel non-trivial vient du fait qu'on ne peut pas toujours trouver une base "canonique". De plus, les quotients et sous-espaces vectoriels d'un espace vectoriel n'ont pas de base évidente.

Pour toutes ces raisons, je ne vois pas pourquoi on devrait trouver naturel de pouvoir considérer une base de n'importe quel espace vectoriel. Je vais même poser la question à l'envers : peux-tu me donner un exemple d'espace vectoriel de dimension infinie, pour lequel on ne peut pas expliciter une base (en un sens naïf), mais où la considération d'une base via l'axiome du choix permet de résoudre un exercice, qui ne fait pas référence à la notion de base dans son énoncé.

Je pense connaître un énoncé de ce genre mais j'avoue n'avoir jamais réfléchi à une façon de le démontrer sans utiliser la notion de base.

christophe c

Je ne sais pas exactement ce que cherche Raymond Cordier quand il demande des exemples ...

à ronchonner -D

Siméon

Pour répondre à mister_jones, voici un problème susceptible de plaire à Raymond Cordier.

Existe-t-il une fonction $f\colon \R \to \R$ additive telle que pour tout $x \in \R$ on a $f(f(x)) = -x$ ?

Fin de partie

Christophe:

Je sais bien qu'une suite est un ensemble mais ce n'est pas $\{u_n\}$ que je persiste, par ailleurs, à ne pas considérer être un ensemble pour la raison déjà indiquée. Si tu préfères, la notation étant incorrecte elle invalide ce qu'elle est censée définir.

Raymond Cordier

@ Siméon
Merci de me poser un problème "susceptible de [me] plaire". En effet celui-ci n'est pas sans intérêt, quoiqu'un peu facile - du moins dans le cadre des mathématiques réelles, dans lesquelles tout espace vectoriel a une base.

Les autres, on me dit qu'elles existent, mais jusqu'ici nul n'a su me les montrer, ni aujourd'hui ni jamais. À ce sujet, la prose de christophe c est très belle littérairement parlant, mais pour ce qui est de son contenu mathématique effectif, je ne vois rien venir.

Le problème posé par Siméon revient à celui-ci : étant donné un espace vectoriel $E$ de dimension infinie sur un corps commutatif $K$, existe-t-il une application ($K$-)linéaire $f$ de $E$ dans $E$ telle que pour tout $x \in E$ on ait : $f(f(x)) = -x$ ? Nous savons de science sûre que tout espace vectoriel a une base, ce que s'accordent à affirmer toutes sortes de bons auteurs dont l'autorité ne me semble pas devoir être mise en doute, et alors la réponse est oui, à l'évidence.

Ici, $E$ est $\R$ et $K$ est $\Q$, et s'agissant d'une telle fonction additive $f\colon \R \to \R$, telle que pour tout $x \in \R$ on ait : $f(f(x)) = -x$, il est clair que cette fonction $f$ est discontinue, et qu'elle donc les qualités surprenantes des fonctions additives discontinues, bien connues des mathématiciens depuis un siècle environ.

Que Siméon nous donne donc d'autres énoncés analogues, relevant des mathématiques réelles, mais moins faciles.

Bonne soirée à Siméon, à christophe c et à tous.
RC

christophe c

@RC: au lieu de toujours chercher à critiquer, tu devrais modifier ton post, il y a une confusion*** car tu n'as pas nommé l'espace vectoriel et réutilisé le nom du corps, affirmant, par étourderie un truc potentiellement faux à la fin.

@FdP: généralement, la notation, $\{ f(x) \mid ... \}$ abrège $\{t\mid \exists x: f(x)=t\ et\ ....\}$. Et c'est un ensemble. Le fait de répéter les noms ou des noms différents d'un même objets n'a rien à voir avec la choucroute. $\{1;1;1;1;1;1;1;1;1;5-4;3-2\}$ est un ensemble, c'est $\{1\}$

Heureusement, qu'avant d'écrire, on n'a pas l'obligation de savoir de manière omnisciente si deux noms désignent ou non le même objet, ça paralyserait toutes les maths. $\{a;b\}$ est un ensemble que $a$ soit ou non égal à $b$ (c'est précisément l'ensemble des $t$ tels que $t=a\ ou\ t=b$)

*** je te cite le passage: étant donné un espace vectoriel de dimension infinie sur un corps commutatif $K$, existe-t-il une application $f$ de $K$ dans $K$ telle que pour tout $x \in K$ on ait : $f(f(x)) = -x$ ? Â l'évidence, la réponse est oui

Et pis, c'est rigolo de te voir rouler des mécaniques en affirmant 2-3 fois que c'est un exo fastoche mais pas au point de ne pas prendre la précaution de supposer la dimension infinie. En dimension2, (avec comme base "constructive" $(e_1,e_2)$), si on envoie $e_1$ sur $e_2$ et $e_2$ sur $(-e_1)$, et qu'on prolonge linéairement en $f$, on obtient que $f(f(xe_1+ye_2)) = f(xe_2-ye_1)=-xe_1-ye_2 = -(xe_1+ye_2)$ (sauf erreur)

christophe c

Ah bin RC a remodifié son post donc le mien est obsolète, mais pas grave, je m'adressais aussi à FdP et précisais un point sur le dimension

NoName

> Merci de me poser un problème "susceptible de
> plaire". En effet celui-ci n'est pas sans intérêt,
> quoiqu'un peu facile - du moins dans le cadre des
> mathématiques réelles, dans lesquelles tout espace
> vectoriel a une base.

Y a des maths réelles et des maths pas réelles maintenant?

christophe c

Je suis toujours déconcerté de voir le nombre de forumeurs qui semblent ne pas être persuadés à 99,4% que RC est un gros trolleur -D Je pense que c'est dû aux posts qu'il soigne perfectionnistement par ailleurs, il paie le péage de l'autoroute du troll En tout cas, moi ça ne me gêne pas, c'est toujours distrayant de répondre à des trolls, mais je ne suis pas sûr que le modés apprécient, en particulier quand ses trolls dérivent graveleusement vers des thèmes politiques, par exemple les maths du sol et les maths du sang

Raymond Cordier

Mille excuses à christophe c, j'ai posté trop vite et je me suis aperçu que j'avais mélangé $E$ et $K$. Je n'ai bien sûr pas eu besoin de son dernier message pour corriger cette étourderie, et je ne l'ai pas lu pendant que je corrigeais le mien. Qu'il me fasse la grâce de penser que je n'ignore pas qu'en dimension finie sur certains corps, et notamment sur $\Q$, il n'existe pas toujours d'endomorphisme $f$ tel que $f\circ f=-Id$. Mais comme en dimension 2 il en existe toujours, cela règle ipso facto le cas de la dimension infinie.
Christophe c peut toujours modifier lui aussi son message à l'intention des générations futures.
Bien cordialement,
RC

christophe c

Je n'ai bien sûr pas eu besoin de son dernier message pour corriger cette étoiurderie et je ne l'ai pas lu pendant que je corrigeais le mien

Siméon

@Raymond : en fait j'ai simplifié le problème que j'avais en tête qui était le suivant.

Peut on munir le groupe additif $(\R,+)$ d'une structure de $\C$-espace vectoriel.

Professeur Rectangle

Preuve et constructivité.

Savoir s'il y a besoin de l'axiome du choix (ou d'une version faible de cet axiome) pour démontrer l'existence d'une base de $\R^{\N}$ et savoir si on peut expliciter une telle base sont deux problématiques très différentes.
On peut en effet imaginer qu'on puisse expliciter une telle base (appelons la $B$), mais qu'on ait besoin de l'axiome du choix pour démontrer que $B$ est bien une base de $\R^{\N}$.

Je ne sais si c'est effectivement le cas, je vais donc illustrer le problème par un autre exemple.
Je considère la proposition suivante : "Il existe un ensemble dont le cardinal est strictement plus grand que celui de $\N$ mais strictement plus petit que celui de $\R$" qui se démontre à l'aide de la négation de l'hypothèse du continu.
Peut-on, expliciter un tel ensemble ?

On serait tenté de répondre "non", en croyant que l'expliciter prouverait que l'hypothèse du continu est fausse.

Mais la vraie réponse est "oui". On peut expliciter un tel ensemble, mais on ne pourra démontrer qu'il vérifie cette proposition qu'en niant l'hypothèse du continu.
On peut prendre comme ensemble, l'ensemble des bons ordres sur $\N$, à isomorphisme près (autrement dit, l'ensemble des classes d'équivalences de bons ordres sur $\N$ pour la relation "est un ordre isomorphe à").

Professeur Rectangle

Axiome du choix


Concernant l'axiome du choix, le voir comme un axiome "d'existence" est purement subjectif. En effet, tout modèle de la théorie des ensembles ZF contient un sous-modèle satisfait l'axiome du choix. La preuve se trouve dans le "Théorie des ensembles" de Jean-Louis Krivine. Cet ouvrage donne même un théorème plus fort : tout modèle de la théorie des ensembles contient un sous-modèle qui vérifie le principe du choix. Le principe du choix disant qu'il existe une relation de bon ordre sur la collection de tous les ensembles.

Dire que l'axiome du choix est vrai, c'est donc nier l'existence d'ensembles "étranges". C'est nier qu'il existe des ensembles inductifs sans maximum, c'est nier qu'il existe des ensembles non-vides dont le produit est non-vide.
A contrario, dire que l'axiome du choix est faux, c'est postuler l'existence d'ensembles aux propriétés étranges. C'est postuler l'existence de familles d'ensembles non-vides dont le produit est vide, etc.
En "supprimant" ces ensembles pathologiques, l'axiome du choix devient vrai.

Raisonnement par l'absurde

Pour ce qui est du raisonnement par l'absurde, ce n'est pas un axiome, mais plutôt une règle logique. Ce n'est pas, mathématiquement, un objet de même nature que les axiomes.
Le raisonnement par l'absurde ne se limite d'ailleurs pas aux seules mathématiques, il peut être utilisé dans n'importe quelle autre discipline nécessitant de la logique (autre science, droit, philosophie, etc.).

Il y a eu, par le passé, des tentatives de mathématiciens de se dispenser du raisonnement par l'absurde. La plus célèbre est, à mon avis, la logique intuitionniste.
ces tentatives furent abandonnées lorsque Gödel démontra qu'on peut coder la logique classique (avec le raisonnement par l'absurde) à l'intérieure de la logique intuitionniste (en utilisant des doubles négations).
La logique intuitionniste a, depuis, trouvé d'autres applications.


PS : Merci pour la référence à Axiom of Choice de Horst Herrlich, je ne connaissais pas

christophe c

@Prof R:

je plussois ton premier des deux posts. Je précise que tu parlais,enfin évoquais l'ordinal de $\omega_1$ dans ton exemple avec l'hypothèse du continu.

Pour le deuxième post, tu es très catégorique sur des choses pour le moins douteuses, historiquement. Je te cite: Il y a eu, par le passé, des tentatives de mathématiciens de se dispenser du raisonnement par l'absurde. La plus célèbre est, à mon avis, la logique intuitionniste.
ces tentatives furent abandonnées lorsque Gödel démontra qu'on peut coder la logique classique

Que signifie "se dispenser" et que signifie "abandonner" ici?

Si tu entends par "se dispenser" la tentative T de déduire le RPA de la logique intuitionniste, le théorème que tu cites de Godel n'a strictement rien à voir avec une mise à port de l'espoir d'y arriver, et ne peut donc conduire à l'abandon par d'éventuels chercheurs passés de la poursuite de T.

Le fait que le RPA n'est pas déductible de la logique intuitionniste est un théorème élémentaire de logique (je ne connais pas la date de sa découverte, mais, elle doit être d +30 heures au plus, d étant la date de formalisation de la logique intuitionniste)

Concernant l'axiome du choix, le fait que L le satisfasse (et comme tu dis, satisfasse un principe du choix) est intéressant, mais ne nourrit pas les tenants du débat "pour ou contre" ; "constructivisme", etc. En effet, il s'agit de débats ultraplatoniciens (ou d'attaque du platonisme). Le fait que $L\models AC$ est écarté (d'ailleurs à tort, mais c'est une autre affaire ) d'un revers de la main par les combattants de cette guéguerre car ils considèrent de toute façon que L n'est pas "le vrai univers". La seule conséquence incontestable tirée à l'époque de la découverte de L est que si ZF est consistant alors ZFC l'est aussi.

Tu écris un peu vite: En "supprimant" ces ensembles pathologiques, l'axiome du choix devient vrai. Euu, non, c'est un peu plus subtil que ça -D (ou alors faut en supprimer vraiment beaucoup, ie descendre éventuellement jusqu'à L)

Tu écris, à propos du RPA: ce n'est pas un axiome, mais plutôt une règle logique. Ce n'est pas, mathématiquement, un objet de même nature que les axiomes.. Bon, on n'est pas à l'armée, je veux pas te paraitre despote, mais si si c'est un axiome**. après, t'as le droit d'en faire une règle logique, bien évidemment, vive la liberté. De toute façon, pour tous les axiomes logiques il y a une correspondance règle-axiomes qui marche très bien. C'est celle, d'ailleurs popularisée qui fait correspondre les systèmes dits "à la Hilbert" et ceux de calculs des séquents ou de déduction naturelle (logique combinatoire--->lambda calcul (tape sur google))

C'est l'axiome $\forall A,B: $ ((A=>B)=>A)=>A

(dont les gens utilisent généralement dans le cas particulier ((nonA)=>A)=>A, en se rappelant que (nonA) abrège (A=>tout))

christophe c

Autocitation: Le fait que le RPA n'est pas déductible de la logique intuitionniste

je te donne un argument informel: un théorème de la logique intuitionniste** est vrai dans tous les espaces topologiques dans le sens suivant: si pour tous $A,B$, tu définis "A=>B" comme la réunion des ouverts X tels que $A\cap X\subseteq B$, alors toute théorème de la logique intuitionniste est l'espace entier si tu remplace les lettres par des ouverts quelconques.

Or le RPA entraine (exercice) A ou (nonA). Exercice trouve un espace topologique et un ouvert A où il n'est pas vrai que $A\cup (int(complementaire(A))) = espaceentier$

**La logique intuitionniste (réduite à "=>") est le plus petit ensemble stable qui contient tous les:

A=>((A=>B)=>B)
A=>(B=>A)
(A=>B)=>((B=>C)=>(A=>C))
(A=>(A=>B))=>(A=>B)

exo: vérifie que dans tout espace top, ces formes sont des noms de l'espace entier, quelles que soient les valeurs des lettres, pourvu que ce sont des ouverts

Professeur Rectangle

Je précise ma référence à Gödel.
Gödel a démontré que tout théorème de logique classique peut se coder en logique intuitionniste.
Son codage est très simple : il ajoute une double négation devant chaque proposition atomique.

Ainsi, si la logique classique avec le raisonnement par l'absurde contient une contradiction, alors la logique intuitionniste contient la même contradiction.

Professeur Rectangle

christophe c a écrit:

Tu écris un peu vite: En "supprimant" ces ensembles pathologiques, l'axiome du choix devient vrai. Euu, non, c'est un peu plus subtil que ça -D (ou alors faut en supprimer vraiment beaucoup, ie descendre éventuellement jusqu'à L)

J'envisageais effectivement de descendre jusqu'à L.

Remarque : L dépend de l'univers de départ. Deux univers peuvent donner deux L différents. En effet, L dépend de la collection des ordinaux (qui n'est pas forcément la même d'un univers de la théorie des ensembles à l'autres).
Sauf erreur de ma part, l'existence d'un cardinal inaccessible est indécidable dans L.

christophe c

, l'existence d'un cardinal inaccessible est indécidable dans L.

Attention: $L$ est un objet, pas un énoncé ou une thoérie. Tu voulais doute dire "indécidable dans ZF+V=L"

Ainsi, si la logique classique avec le raisonnement par l'absurde contient une contradiction, alors la logique intuitionniste contient la même

Ca aussi c'est un exercice élémentaire (je vais d'ailleurs ajouter des précisions en (**)), dont je ne pense pas qu'on puisse dire que ceux dont tu disais qu'ils tentaient de "se dispenser" du RPA ne le connaissaient pas avant Godel et auraient "renoncer" après. Mais merci car ça précise ce que tu as voulu dire quand tu as écrit: Il y a eu, par le passé, des tentatives de mathématiciens de se dispenser du raisonnement par l'absurde. La plus célèbre est, à mon avis, la logique intuitionniste. ces tentatives furent abandonnées lorsque Gödel....

Tu voulais donc dire semble-t-il: un certain nombre de chercheurs, dans le passé, espéraient s'affranchir des contradictions habituellement rencontrées en logique classique (paradoxes des fondements, etc) par le biais d'un retrait du RPA des maths. Ils y ont renoncé quand blabla

C'est possible, au tout début, pourquoi pas après tout, c'est une question d'histoire (et s'il y a bien un domaine que je ne connais pas c'est l'histoire). Mais ça parait quand-même, bien que possible, peu probable car les "paradoxes des fondements", ie le théorème (A=>(A=>B))=>(((A=>B)=>A)=>B), ont émergé très officiellement dès avant 1900 je crois. Or ces paradoxes sont des théorèmes intuitionistes dès le départ sans qu'il y ait besoin même d'une reformulation. Autrement dit, quand Godel était encore entrain de têter sa maman, il était déjà publié formellement et courtement que le problème ne vient pas du RPA. Il ne semble donc pas qu'un projet de retrait du RPA en vue de lever des paradoxes antifondateurs ait pu exister, puis se soit écroulé parce qu'une non-non traduction aurait été mise au jour.

De l'histoire je ne connais que quelques vagues rumeurs, mais j'ai plutôt entendu dire que la logique intuitionniste était appelée des voeux de Brouwer qui voulait, face à l'infini, chercher une alternative aux maths qui prouvent l'existence de quelque chose sans l'exhiber (S'appuyant sur SON théorème de point fixe par exemple). Autrement dit, même si ça s'est crashé ensuite (j'ai dit pourquoi quelques posts au dessus), l'acte de naissance de la log intu serait des motivations "constructivistes" (ie des motivations de même nature que le premier post de l'auteur du fil)

(**) Propositionnellement, il n'y a pas besoin de "non-non" traduction (sur le langage de =>, seul pertinent de toute façon): si P=>tout est un théorème propositionnelle de la logique classique alors P=>tout est un théorème de la logique intuitionniste.

Sketch-preuve: supposons que ((A ou (nonA)) et P)=>tout. Alors P=>(A=>tout), mais aussi P=>((A=>tout)=>tout), donc P=>tout

(Rappel: A=>tout est abrégé par "nonA")

Il s'ensuit par récurrence que si tu peux utiliser un nombre fini d'axiomes de la forme (X ou (nonX)) pour prouver que P=>tout alors tu peux t'en passer.

christophe c

Ah et au fait, oui bien sûr que "il existe inaccessible" est improuvable dans ZF+V=L (sauf si ZF contradictoire). il n'y a rien à changer d'ailleurs, c'est la même preuve que "il existe inaccessible" est improuvable dans ZFC

Professeur Rectangle

A propos du constructivisme : il suffit de considérer un modèle de Herbrand de la ZF (ou de ZFC) pour pouvoir représenter (par exemple sur ordinateur) tous les ensembles du modèle.
Comme quoi, on peut n'avoir que des ensembles intuitivement constructibles tout en gardant l'axiome du choix.

christophe c

Attention, ce sont souvent des modèles artificiels cependant et ils contiennent tous des entiers infinis. Par ailleurs, qu'atteint-on réellement par ordinateur? Le début de l'arbre, et non pas la branche la plus à gauche entière, dont on ne peut pas savoir comment elle continue.

Cependant, sur le plan général, tu as raison souligner que philosophiquement la distinction constructif/ non constructif n'a pas de sens (ce qui peut se démontrer autrement sans même avoir recours à ZF tout entier) et c'est ça qui conduit à avoir deux mots, un mot informel : "consrtuctif" et un mot mathémtiquement défini: "intuitionniste".

Judoboy

Bon je crois que j'ai la réponse à ma question et même bien plus, merci à tous !