De toute façon je pense que c'est raté pour trouver une identité vérifiée par les matrices et pas les monoïdes, puisque les monoïdes libres (d'après ce que j'ai crompris) se plongent dans $M_{2,2}(\mathbb{N})$.
Oui, c'est ça. Considérons des endomorphismes $p,f,g$ d'un espace vectoriel $E$ de dimension finie. Vérifiant $p^2=p$, $pf=fp=f$, $gp=pg=g$ et $fg=p$.
Posons $F=\mathrm{Im}\,p$, comme $f=pf$ l'image de $f$ est incluse dans $F$, de même l'image de $g$ est incluse dans $F$. On peut donc regarder $p',f'$ et $g'$ les endomorphismes de $F$ restrictions de $p,f$ et $g$.
On voit que $p'=\mathrm{id}_F$ et $f'g'=p'=\mathrm{id}_F$. Comme $F$ est de dimension finie, on a $g'f'=p'$. Soit $x\in E$, on a $g(f(x))=g(f(p(x)))=g'(f'(p(x))=p(p(x))=p(x)$, donc on a bien $gf=p$.
Je viens de vider ma batterie en répondant à doc, mais bravooo, je vérifierai plus tard les détails. Tu as d'ailleurs trouvé peut-être le plus court des exemples.
Sur l'histoire des monoides libre et de $M_2(\N)$, j'avoue que je n'ai pas trop compris. Je peux prouver que prenant $\Z$ comme anneau, il existe une solution à ma question (même si je ne la connais pas)
En effet, les énoncés vrais dans tous les monoides forment un ensemble récursivement énumérable non récursif. les énoncés vrai (de ce genre) vrais dans $M_n(\Z)$ forment un ensemble co-recursivement énumérable... AAAAAAAAH NOOOOOOOOONNNNNNN PAS FORCEMENT!!!!!!!!!!!!!!!!!!!!!!!!!!![/size] (en fait, j'allais écrire par réflexe (lol batteries vides) un truc qui n'est essentiellement valable que pour certains corps... $\R$, $\C$, ($\Q$ probablement)
waouh, c'est joli ton annonce de théorème! C'est bien plus joli que le théorème de Matiasevic...[/size]
EDIT: voire post ci-dessous (le 3e je crois). En fait, je peux prouver qu'il y a des solutions à l'exercice (la plupart des versions: corps commutatifs habituels, anneaux finis, anneaux $\Z$) qui demande d'en trouver au moins une, par un argument de calculabilité.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Bonsoir à tous,
@ mpif: ton dernier post est la solution de quel exercice ?
Si c'est le 13), f n'est pas linéaire et g n'est pas donnée. :S
Bien cordialement.
Une identité est un couple de termes, noté $t_1=t_2$, par exemple $x(y((xy)z))=z((xy)z)$.
On dit qu'un demi-groupe vérifie l'identité si pour tout choix des variables (ici $x,y,z$) dans le demi-groupe, l'évaluation des termes donne le même élément. C'est facile de voire que ça passe au quotient.
J'ai fait quelques recherches et il semblerait que les monoïdes libres (finiment, ou dénombrablement engendrés je pense) se plonge dans $M_2(\mathbb{N})$. On voit alors qu'une identité satisfaite par les anneaux de matrices sera satisfaite par les monoïdes lires, et donc tous les monoïdes. Je pense aussi tous les demi-groupes...
Par contre j'ai trouvé une quasi-identité séparant les demi-groupes de matrices et les demi-groupes.
En gros la variété de demi-groupes engendrée par les $M_n(K)$ est la variété de tous les demi-groupes.
Par contre la quasi-variété de demi-groupes engendrée par les $M_n(K)$ n'est pas la quasi-variété des demi-groupes.
Il faut faire très attention à propos des décidabilités, j'expose un résultat de Julia Robinson.
Considérons $\phi(r,y,z)$ la formule $\exists a\exists b\exists c (2+yzr^2=a^2+yb^2-zc^2)$.
Considérons $\theta(r)$ la formule $(\phi(0,y,z)\wedge \forall w(\phi(w,y,z)\rightarrow\phi(w+1,y,z))\rightarrow\phi(r,y,z))$.
On voit une "récurrence" dans $\theta$.
Alors, dans $\mathbb{Q}$, on a $\theta(r)$ si et seulement si $r$ est entier.
Du coup les formules du premier ordre ne sont pas décidable dans $(\mathbb{Q},+,\times,0,1)$.
Il semblerait qu'il existe de meilleur formules (i.e. avec une autre répartition des quantificateurs), en utilisant des courbes elliptiques et les $\mathbb{Q}_p$... Comme quoi le travaille des géomètre modernes peut avoir un intérêt.
D'après ce qu'on ma dit (mais je n'ai jamais vu la formule), on peut même trouver une formule n'utilisant que des quantificateurs universels, mais il y en plus de 40...
Par contre on peut montrer que dans $(\mathbb{R},+,\times,0,1,\le,\mathrm{exp})$ les formules du premier ordre sont décidables.
Mais je ne sais pas trop pour les formules utilisant seulement le produit, elle semblent beaucoup plus "simples", du coup $(M_{2,2}(\mathbb{Q}),\times)$ est peut-être décidable.
@ mpif: ton dernier post est la solution de quel exercice ?
Si c'est le 13), f n'est pas linéaire et g n'est pas donnée.
Bien cordialement.
C'est la solution de 34), mais je ne comprend pas, je ne défini ni $f$ ni $g$, mais je les "prends" linéaires.
oui, je suis bien d'accord avec tout ça, et d'ailleurs le résultat de J.Robinson est très joli et merci de le rappeler, je ne savais plus par quelle formule $\Z$ (et du coup $\N$) est définissable dans $\Q$.
Mais ça n'enlève pas que l'ensemble A des formules (purement universelles) vraies dans tout monoide est un ensemble récursivement énumérable universel (donc non récursif) et que l'ensemble B des formules purement universelles vraies (du langage monoide) pour tout $n$ dans $M_n(K)$ est corécursivement énumérable, et contenant A. Il s'ensuit donc que B contient strictement A et qu'il existe une formule dans B-A.
40) je tire cette question que je trouve marrante du fil suivant http://www.les-mathematiques.net/phorum/read.php?4,550313,550436#msg-550436. Soit $E$ un espace métrique qui soit de Baire. Soit $D$ une partie dénombrable et dense de $E$. Soit $f$ une application de $D$ dans $\N^*$. Existe-t-il forcément un élément $x$ de $E-D$ tel que $\forall d\in d(x,d)/f(d)<1$?
Edit: j'ai encore mangé un mot sur 2:D, voir post suivant de foys...
Existe-t-il forcément un ensemble $F\subseteq D$ et un élément $x$ de $E-D$ tel que $\forall d\in F: d(x,d)/f(d)<1$ et $x\in \bar{F}$
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
christophe chalons écrivait:
> 40) je tire cette question que je trouve marrante du fil suivant http://www.les-mathematiques.net/phorum/read.php?4,550313,550436#msg-550436.
> Soit $E$ un espace métrique qui soit de Baire. Soit $D$ une partie dénombrable et dense de $E$.
> Soit $f$ une application de $D$ dans $\N^*$. Existe-t-il forcément un élément $x$ de $E\setminus D$ tel que $\forall d\in D,\ d(x,d)/f(d)<1$ ?
Non car on pourrait prendre $f$ bornée, voire constante (et $E=\mathbb R, D=\mathbb Q$)
Merci foys, je me suis encore gourré dans mes intentions (à remarquer aussi que je n'ai pas été très prudent avec la liberté de définir la distance, mais ça ce n'est pas une erreur de frappe). Je ne crée pas une nouvelle question, je fais un edit, tout en signalant ton post.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Oui donc, tu as résolu l'exercice. Effectivement, prenons un ensemble muni de la topologie discrête. Il est de Baire car les seuls fermés d'intérieur vide sont l'ensemble vide. Mais alors le seul $D$ possible est $E$ tout entier ce qui rend $E$ dénombrable d'ailleurs. En tout cas c'est sûr qu'on ne trouvera pas de $x\notin D$, quoiqu'on lui demanderait ensuite de vérifier.
Par contre je n'ai pas trop compris la suite. J'ai l'impression que tu traites le cas particulier $f:=constante 1$ par exemple. Je vais créer une question 41 formulée plus formellement.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
4) il existe une application $f$ de $D$ dans $\N ^*$ telle que pour tout $x\in E-D$, et toute partie $F$ de $D$ dont l'adhérence contient $x$, il existe $r\in F$ tel que $f(r)d(x,r)\geq 1$
EDIT: patch voir post foys
5) $E$ n'est pas dénombrable
(En rajoutant (3), ça semble rendre la question nettement plus difficile. Mais éventuellement déjà, trouver un exemple, avec seulement 1-2-4, ce serait pas mal je pense).
(Je n'avais pas rajouté (5) à la question40, et au fond, c'est de là qu'est venu ton exemple, foys: la condition 4 continue, après le "il existe" par "pour tout x hors de D blabla" )
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Concernant la question 34 (et ses entourantes 33 à ?) à laquelle a jolimnet répondu mpif, il y a une question plus pénible, dont la réponse est positive (on sait qu'il en existe, mais de là à en signaler un explicite...)
42) Trouver un énoncé $\forall x,y,..: terme_1=terme_2$ vrai dans tous les $M_n(K)$ et faux dans au moins un monoide. Remarque: l'énoncé de mpif contient un connecteur "implique"
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Je voulais dire que comme $f$ est à valeurs dans $\mathbb N^*$, l'inégalité est facile à satisfaire.
Pour 41) on va prendre $E=[0;1]$ muni de sa distance usuelle $d(x,y)=|y-x|$ et $D= \mathbb Q \cap E$, les points de 1 à 5 sont trivialement vérifiés.
42) non je l'ai expliqué plus tôt, on ne peut pas séparer les $M_n(K)$ des monoïdes avec une identité. Du moins si $K$ est de caractéristique $0$.
En fait le monoïde libre sur $n$ générateurs se plonge dans $M_2(\mathbb{N})$. Si une identité est vérifiée par les $M_n(K)$ alors elle est vérifiée par les monoïdes libres, et donc (en passant au quotient) par tous les monoïdes.
En claire si on a une formule $\forall x_1,\dots,x_n\ t(x_1,\dots,x_n)=t'(x_1,\dots,x_n)$ satisfaite par tous les $M_n(K)$ alors elle est satisfaite par tous les monoïdes.
En fait une identité passe au quotient mais pas une quasi-identité ! C'est ce qui rend possible mon exemple.
à foys, non je ne pense pas que le point4 soit satisfait, et même je pense que dans le cas précis de $\R$ justement, il ne l'est pas. Au post suivant, j'essairai de t'en donner une preuve.
à mpif, non, je pense que tu te trompes, j'ai déjà expliqué pourquoi, mais à propos de $M_n(\N)$.
Il existe au moins un énoncé de la forme $P:=\forall ...:t_1=t_2$*** vérifié dans $M_n(\N)$ pour tout $n$ et qui est faux dans au moins un monoide (je ne traite le cas avec des $K$ quelconques, ton argumentation ne tourne pas autour de ça)
Preuve: l'ensemble des $P$ de la forme *** vrais dans tous les monoides est un ensemble $A$ récursivement énumérable non récursif. L'ensemble $B$ des énoncés $P$ de la forme *** vrais dans tous les $M_n(\N)$ est le complémentaire d'un ensemble récursivement énumérable et on a $A\subseteq B$. Si on avait $A=B$ alors $A$ serait récursif (et $B$ aussi d'ailleurs).
Ah oui, non pardon, c'est vrai que tu as raison!!!!!!!!!, je disais n'importe quoi, on a bien sûr besoin de dire faire des hypothèses!!!!! Toute mes excuses, et les hypothèses se traduisent bien par $m_1=n_1; m_2=n_2; ...\to c=d$
Le $A$ sans autoriser des connecteurs en question (avec le truc dont je parle) est un ensemble assez débile lool
Donc effectivement la forme de ton énoncé est la meilleure possible
Ce qui m'a fait me tromper est que je me focalise sur ta citation
De toute façon je pense que c'est raté pour trouver une identité vérifiée par les matrices et pas les monoïdes, puisque les monoïdes libres (d'après ce que j'ai crompris) se plongent dans $M_{2,2}(\mathbb{N})$.
et je te faisais le "procès d'intention" (involontairment) de croire que tu continuais de le défendre et donc je te lisais en diagonale. loool Et j'avais tort (ou plutôt raison de penser que tu le défendais, mais tu avais raison de le défendre)
Ahhhh mais décidément je ne lis pas assez soigneusement, vu que tu parles d'une identité, TU AS RAISON, dès le départ, j'ai lu "identité" comme une simple reformulation de ce que je demande pfffff. Toutes mes excuses
Bon je vais un post de récapitulation
Donc je reprécise bien: tu as bien trouvé un exemple qui répond à 34 (avec les corps), mais il en existe AUSSI*** avec l'anneau $\Z$, et la question reste donc en suspens quand on autorise des connecteurs logiques.
*** pour l'argument que j'ai dit.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
à foys: soit $f$ à image dans $\N^*$. Soit une suite de rationnels $t_1<t_2,...$ (même strictement croissante) qui tend vers $x\notin \Q$ et telle que $\forall n\in \N^*: x-t_n<1/f(t_n)$, alors l'ensemble $F$ des $t_n$ contient bien $x$ dans son adhérence et infirme (4).
Certes, tu pourrais contester que les $t_i$ et $x$ existent.
EDIT: j'ai aussi patché ici
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
45) (inspiré par samok) Existe un couple $(A,P,a)$ tel que:
1) $A$ est un anneau
2) $P$ est tel que $\exists z\in P:y=x+z$ est un ordre totale sur $A$
3) $P$ est stable par $+$ et par $\times$
4) tout élement non nul $x$ de $P$ est tel qu'il existe un élément $z\in P: x=1+z$
5) $P\cap -P=\{0\}$
6) $a\in A$ et $\forall x\in A:2x\neq a$ et $2x\neq a+1$
?
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
41) Relis bien ton point 4)... à la base ton intention était d'avoir l'inégalité dans l'autre sens peut-être? En tout cas ton exemple avec la suite ne l'infirme pas, tel qu'il est écrit .
45)$\mathbb Z [X]$ avec $P$ l'ensemble des polynômes dont le coefficient dominant est positif, et comme $X$ et $X+1$ sont irréductibles, on prend $a=X$.
44) Ma quasi-identité est vraie dans $M_n(\mathbb{Z})$ car les quasi-identités passent aux sous-structure. De même "ma" quasi-identté est vraie dans $M_n(A)$ avec $A$ anneau intègre commutatif.
Par contre si $A$ est un anneau commutatif quelconque je ne sais pas trop.
Le résultat de la question 46 m'a l'air d'être un cas particulier d'un théorème de Khinchine :
Soit $\theta_{k}>0$ des réels tels que $\sum\theta_{k}<+\infty$. On considère l'ensemble
\begin{equation*}
A=\left\{x\in\left]0\,,1\right[:
\begin{aligned}
&\text{l'inéquation $\left\lvert x-\tfrac{p}{q}\right\rvert<\tfrac{\theta_{q}}{q}$ ($p\in\mathbb{Z}$, $q\in\mathbb{N}^{*}$)}\\
&\text{admet une infinité de solutions}
\end{aligned}\right\}.
\end{equation*}
Alors $\lambda(A)=0$ ($\lambda$ est la mesure de Lebesgue).
En fait c'est aussi relié à la question4 du présent topic. Si Erdos a vu ça seulement dans les années 60, un argument psycho-historique dit que L n'a pas un complémentaire maigre (ce qui me parait bizarre, mais après tout) ou qu'on avait pas encore prouvé ces années là qu'un ensemble A dont le complémentaire est maigre est tel que A-A est un voisinage de 0
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Pour 45) j'ai bien vu et lu. C'est un peu la blague de Coluche "quand il a fini de répondre à la question, tu comprends plus la question que t'as posé" (sourire).
longue vie à ce fil,
S
Edit : il n'y a pas de dérision, je n'ai pas cette capacité d'abstraction pour définir une question pertinente, je peux juste en apprécier la pertinence quand elle l'est et que j'ai pas trop de purée dans les yeux (je suis éducable quoi)
Il est "facile" de voir que pour tout convexe $C$ compact, et pour tout triangle $T$ il existe un convexe $C_2$ similaire à $C$ qui est inscrit dans $T$ (ie inclus dans $T$ et touchant ses 3 côtés)
Salut Christophe.
Pourrais-tu donner une démonstration possible, ou les grandes idées, si ça ne te dérange pas ?
J'ai très peu de temps encore grrrr, donc les grandes lignes:
Imagine ton convexe "dynamique" similaire au convexe modèle, et on démarre avec une copie toute petite à l'intérieur du triangle. Il gonfle (en restant TOUJOURS similaire), se bute dans un côté, continue de gonfler en restant à l'intérieur, se bute dans un deuxième côté, là il peut encore continuer de gonfler et finalement est bloqué par le troisième côté, ça s'arrête là tu as ta copie similaire au modèle et inscrite dans le triangle.
A priori, même, cette copie est plus que similaire, elle est comment dire, image par une composée de translation et d'homothétie du modèle.
C'est valable pour toute dimension finie, pour tout convexe, et ce qui fait office de triangle (je ne sais pas comment ça s'appelle en dimension n; tétraedre en dimension 3)
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Evidemment si tu es plus "géomètre", c'est sûr que tu risquais d'avoir du mal à trouver une preuve avec "des calculs géométriques" à la manière des fils de géométrie pure, genre où on trouve les points de contacts exacts et tout et tout...
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
En fait, j'avais en tête le lemme de Goursat, qui parle aussi de triangle convexe, et quand j'ai vu la question que tu posais, j'ai essayé de faire un rapprochement.
Mais je ne comprends pas grand chose à ton explication, c'est d'un niveau plus haut que le mien
Est-ce que l'idée dans le fond c'est d'utiliser des homéomorphismes et des difféomorphismes pour "modifier" le triangle ?
48) existe-t-il un polynome $P(X,Y)$ et des fonctions $f,g$ tels que $\forall a,b: cos(ab)=P(f(a);f(b))$
Mais je ne comprends pas grand chose à ton explication, c'est d'un niveau plus haut que le mien
Ah non non, c'est je pense "vox populi"... En fait, lis bien chaque détail et "imagine la scène"
Dès que j'ai du temps, je te la rédige "académiquement" en donnant des noms à tout ce qu'il faut. Maintenant, on peut contester le caractère formel, parce que c'est vrai que bof bof. Mais c'est bien plus facile que de jolis lemmes "exacts" de géométrie.
On ne modifie pas le triangle, on fait se balader dedans des homothétiques du convexe, en imaginant que les côtés du traingle sont "solides" et infranchissables.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
50) Soit $H$ un espace de Hilbert (sur $\R$ ) et $A\subseteq H$. On suppose que pour tout sev $K$ de $H$ qui est de dimension finie, $A\cap K$ est inclus dans une sphère. L'ensemble $A$ tout entier est-il forcément inclus dans une sphère?
51) Soit $A$ un anneau dont tous les éléments réguliers sont inversibles. Soit $B$ un sous-anneau de $A$ qui est noethérien. Existe-t-il forcément un sous-anneau $C$ de $A$ tel que $B \subseteq C$ et $C$ noethérien et tout élément régulier de $C$ est inversible?
L'exercice suivant échappe à la règle "être difficile", mais il est intéressant en ce qu'il offre une situation générale où des $\forall \exists$ deviennent "magiquement" des $\exists \forall$
52) Soit $\leq$ un odre total sur $E^n$. On suppose que $\forall (a_1,...,a_n)\in E^n\exists (b_1,...,b_n)\in E^n: (a_1,...,a_n)<(b_1,...,b_n)$. Prouver qu'alors $\forall a_1\in E\exists b_1\in E\forall a_2\in E\exists b_2\in E...: (a_1,...,a_n)<(b_1,...,b_n)$
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Comme il est annoncé facile, je me suis penché sur le 52)
Comme je suis paresseux, je fais pour n = 3.
Supposons à contrario Ea1 Qb1 Ea2 Qb2 Ea3 Qb3 (a1 a2 a3) >= (b1 b2 b3)
Je renote : (a1 a2(x) a3(x,y) ) >= (x y z)
(a1 a2(a1) a3(a1, a2(a1) ) >= (a1 a2(a1) z )
(a1 a2(a1) a3(a1,y) ) >= (a1 y z)
(a1 a2(x) a3(x,y) ) >= (x y z)
et par transitivité, (a1 a2(a1) a3(a1, a2(a1)) ) est maximum, contradiction.
Bon, bin le 53 va te faire tourner bourrique au niveau des notations si tu tiens à mettre des indices.
53) Soit $T:=E^\N$ muni de la topologie canonique (produit de la discrête)
Soit $n$ une application de $T$ dans $\N$
Soit $f$ une application de $T$ dans un ordre total $S$ telle que $\forall x\in T: f(x)$ ne dépend que de $(x_0;...;x_{n(x)})$
On suppose que pour tout $x\in T$ il existe $y\in T$ tel que $f(y)>f(x)$
Prouver qu'il existe une application continue $h$ de $T$ dans $T$ telle que $\forall x\in T: f (h(x)) >f(x)$
La différence avec le 52, c'est que au lieu de "s'arrêter" à n fixe, ça varie, tu ne peux donc plus dire, "je le fais pour n = 17 et on comprend le principe". En même tps, réussir celui-là te permet de mieux voir le principe.
54) Soit $E$ un $\R$-espace vectoriel de dimension finie et $f$ une application de $E\to E$.
Pour tout $P:=a_0+...+a^kX^k \in \R[X]$, on pose $T(P)=a_0.id + a_1.f+ ... + a^k f^k$ où $f^k$ signifie $f o f ...of$ k fois.
On suppose que:
$\forall P,Q: T(P+Q)=T(P)+T(Q)$ et $T(PQ) = T(P) o T(Q)$
Question: $f$ est-elle forcément une application linéaire?
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
justement, à ce propos et avant de me lancer (peut-être) dans le 53, j'aimerais te soumettre la question que je me suis posée à propos du 52 : pour tout entier n explicitement écrit, on voit clairement le texte de la démonstration qu'il faut écrire pour démontrer l'énoncé concernant n. Bien entendu, ce n'est pas une démontration de : quel que soit n, ... Cela ne m'a pas posé de problème de conscience puisque, au-delà de ma paresse, je me suis dit que ton théorème n'en était pas un, mais bien plutôt un schéma de théorèmes, pour lequel je t'ai proposé l'une parmi un schéma de démonstrations. Par contre, ça m'a fait penser à ceci : supposons que j'aie un théorème d'arithmétique à démonter de la forme
(Quel que soit n) P(n)
et que je n'en trouve pas de démonstration (par récurrence par exemple), mais que pour tout entier n explicitement écrit, j'indique au lecteur le procédé de construction d'une démonstration
Demn de l'énoncé P(n).
Deux cas peuvent alors se produire (un troisième, que ¬ (Qn) P(n) soit un théorème ne me semble pas possible puisqu'alors, il serait vrai pour tout modèle, dont le standard, et un des énoncés P(n) démontrés explicitement serait contredit) :
- soit (Qn) P(n) est un théorème. Dans ce cas, sa (ses) démonstrations sont-elle nécessairement apparentées aux démontrations Demk ?
- soit (Qn) P(n) est indémontrable, ce qui me semblerait tout de même paradoxal. Connaîtrais-tu un exemple de cette situation ?
1) de prouver que pour tout n il existe une preuve dans T (peano par exemple) de P(n)
2) de prouver que pour tout n, P(n)
Un exemple simple est que pour tout n, tu peux prouver que n est standard, même pour les entiers non standard, par exemple, si tu te places en analyse non standard. Pour autant tu ne peux pas prouver que pour tout n, n est standard.
Un autre exemple est le suivant: pour tout n, tu peux prouver qu'il n'existe pas de preuve de 0=1 de longueur au plus n, dans T (par exmple Peano). Le schéma de la preuve est d'ailleurs simple tu dis aux gens: "regardez, je les essaie toutes, et constatez avec moi qu'auune ne conclut 0=1". Pour autant, "donner ce plan à l'auditoire" n'est en aucun cas une preuve de la consistance de T
Donc, il y a PLUS que 2 cas, il y en a en fait au moins trois et tu n'as pas précisé.
1) Prouver $\forall n: R(n)$
2) donner un programme dont tu peux prouver que pour tout n, il renvoit une preuve de R(n)
3) donner un programme dont tu peux prouver que pour tout n, s'il s'arrête alors il renvoie une preuve de R(n)
...
il y a plein de théories consistantes dans lesquelles, on réussir (2) et pas (1), pour certaines R
D'ailleurs à commencer par les plus simples: tu prends une théorie très faible T (genre avec juste de la récurrence autorisée pour des broutilles), mais dans laquelle tout ce ci a un sens, et tu rajoutes le schéma d'axiome pour chaque R: si pour tout n, R(n) est prouvable dans T alors $\forall xR(x)$. Et bien tu obtiens une théorie très forte dont tous les axiomes de Peano sont des théorèmes, aussi faible que T soit au départ (en gros).
En effet, essentiellement, si tu peux prouver $\forall x: R(x)\to R(x+1)$, alors tu peux prouver que si $R(n)$ est prouvable alors $R(n+1)$ l'est, mais ce dernier énoncé est un énoncé très très simple (au sens bas en complexité) qui ne concerne que des choses très finies, etc.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Cela dit, pour le (53), justement, c'est pour ça que j'ai fai dépendre le n(x) de x, de sorte qu'on ne puisse plus même ne serait-ce qu'évoquer une idée du genre "vous voyez bien que pour n+1 c'est pareil"
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
55) On suppose que A,B sont des anneaux et que A est un sous-anneau de B tel que tout élément de A, qui, dans B est inversible, l'est aussi dans A.
Prouver sans utiliser ni les déterminants, ni les formes alternées que si une matrice carrée à coefficients dans A est inversible, en tant que matrice vue dans B alors elle est inversible vue dans A.
(anneaux commutatifs unitaires, of course)
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Réponses
si AC=A=CA et BC=CB=B et CC=C et AB=C alors BA=C
Posons $F=\mathrm{Im}\,p$, comme $f=pf$ l'image de $f$ est incluse dans $F$, de même l'image de $g$ est incluse dans $F$. On peut donc regarder $p',f'$ et $g'$ les endomorphismes de $F$ restrictions de $p,f$ et $g$.
On voit que $p'=\mathrm{id}_F$ et $f'g'=p'=\mathrm{id}_F$. Comme $F$ est de dimension finie, on a $g'f'=p'$. Soit $x\in E$, on a $g(f(x))=g(f(p(x)))=g'(f'(p(x))=p(p(x))=p(x)$, donc on a bien $gf=p$.
Sur l'histoire des monoides libre et de $M_2(\N)$, j'avoue que je n'ai pas trop compris. Je peux prouver que prenant $\Z$ comme anneau, il existe une solution à ma question (même si je ne la connais pas)
En effet, les énoncés vrais dans tous les monoides forment un ensemble récursivement énumérable non récursif. les énoncés vrai (de ce genre) vrais dans $M_n(\Z)$ forment un ensemble co-recursivement énumérable... AAAAAAAAH NOOOOOOOOONNNNNNN PAS FORCEMENT!!!!!!!!!!!!!!!!!!!!!!!!!!![/size] (en fait, j'allais écrire par réflexe (lol batteries vides) un truc qui n'est essentiellement valable que pour certains corps... $\R$, $\C$, ($\Q$ probablement)
waouh, c'est joli ton annonce de théorème! C'est bien plus joli que le théorème de Matiasevic...[/size]
EDIT: voire post ci-dessous (le 3e je crois). En fait, je peux prouver qu'il y a des solutions à l'exercice (la plupart des versions: corps commutatifs habituels, anneaux finis, anneaux $\Z$) qui demande d'en trouver au moins une, par un argument de calculabilité.
Si un énoncé $\forall ^* P$ est faux dans au moins un des $M_n(\Z)$ pour au moins un $n$, il est "récursivement énumérable de le trouver"
[size=large]Il y a donc bien un exemple de tel énoncé vrai pour tous les $M_n(\Z)$ mais pas pour tous les monoides.[/size]
Je vais barrer mon émotion de tout à l'heure, sniif.
@ mpif: ton dernier post est la solution de quel exercice ?
Si c'est le 13), f n'est pas linéaire et g n'est pas donnée. :S
Bien cordialement.
Une identité est un couple de termes, noté $t_1=t_2$, par exemple $x(y((xy)z))=z((xy)z)$.
On dit qu'un demi-groupe vérifie l'identité si pour tout choix des variables (ici $x,y,z$) dans le demi-groupe, l'évaluation des termes donne le même élément. C'est facile de voire que ça passe au quotient.
J'ai fait quelques recherches et il semblerait que les monoïdes libres (finiment, ou dénombrablement engendrés je pense) se plonge dans $M_2(\mathbb{N})$. On voit alors qu'une identité satisfaite par les anneaux de matrices sera satisfaite par les monoïdes lires, et donc tous les monoïdes. Je pense aussi tous les demi-groupes...
Par contre j'ai trouvé une quasi-identité séparant les demi-groupes de matrices et les demi-groupes.
En gros la variété de demi-groupes engendrée par les $M_n(K)$ est la variété de tous les demi-groupes.
Par contre la quasi-variété de demi-groupes engendrée par les $M_n(K)$ n'est pas la quasi-variété des demi-groupes.
Considérons $\phi(r,y,z)$ la formule $\exists a\exists b\exists c (2+yzr^2=a^2+yb^2-zc^2)$.
Considérons $\theta(r)$ la formule $(\phi(0,y,z)\wedge \forall w(\phi(w,y,z)\rightarrow\phi(w+1,y,z))\rightarrow\phi(r,y,z))$.
On voit une "récurrence" dans $\theta$.
Alors, dans $\mathbb{Q}$, on a $\theta(r)$ si et seulement si $r$ est entier.
Du coup les formules du premier ordre ne sont pas décidable dans $(\mathbb{Q},+,\times,0,1)$.
Il semblerait qu'il existe de meilleur formules (i.e. avec une autre répartition des quantificateurs), en utilisant des courbes elliptiques et les $\mathbb{Q}_p$... Comme quoi le travaille des géomètre modernes peut avoir un intérêt.
D'après ce qu'on ma dit (mais je n'ai jamais vu la formule), on peut même trouver une formule n'utilisant que des quantificateurs universels, mais il y en plus de 40...
Par contre on peut montrer que dans $(\mathbb{R},+,\times,0,1,\le,\mathrm{exp})$ les formules du premier ordre sont décidables.
Mais je ne sais pas trop pour les formules utilisant seulement le produit, elle semblent beaucoup plus "simples", du coup $(M_{2,2}(\mathbb{Q}),\times)$ est peut-être décidable.
C'est la solution de 34), mais je ne comprend pas, je ne défini ni $f$ ni $g$, mais je les "prends" linéaires.
Mais ça n'enlève pas que l'ensemble A des formules (purement universelles) vraies dans tout monoide est un ensemble récursivement énumérable universel (donc non récursif) et que l'ensemble B des formules purement universelles vraies (du langage monoide) pour tout $n$ dans $M_n(K)$ est corécursivement énumérable, et contenant A. Il s'ensuit donc que B contient strictement A et qu'il existe une formule dans B-A.
Je relirai ce soir cette histoire de $M_2(\N)$
Edit: j'ai encore mangé un mot sur 2:D, voir post suivant de foys...
Existe-t-il forcément un ensemble $F\subseteq D$ et un élément $x$ de $E-D$ tel que $\forall d\in F: d(x,d)/f(d)<1$ et $x\in \bar{F}$
> 40) je tire cette question que je trouve marrante du fil suivant http://www.les-mathematiques.net/phorum/read.php?4,550313,550436#msg-550436.
> Soit $E$ un espace métrique qui soit de Baire. Soit $D$ une partie dénombrable et dense de $E$.
> Soit $f$ une application de $D$ dans $\N^*$. Existe-t-il forcément un élément $x$ de $E\setminus D$ tel que $\forall d\in D,\ d(x,d)/f(d)<1$ ?
Non car on pourrait prendre $f$ bornée, voire constante (et $E=\mathbb R, D=\mathbb Q$)
En fait le résultat est vrai si on arrive à trouver dans $E$ une partie $F$ de $D$ de diamètre <1, dont l'adhérence n'est pas incluse dans $D$.
Par ex c'est vrai dans le cas où il existe dans $E-D$ des points non isolés de $E$: soit $x$ un tel point, $F=B(x,\frac{1}{3})\cap D$ convient.
Par contre je n'ai pas trop compris la suite. J'ai l'impression que tu traites le cas particulier $f:=constante 1$ par exemple. Je vais créer une question 41 formulée plus formellement.
1) $E$ est de Baire
2) $D$ est dénombrable et dense dans $E$
3) $E$ est connexe
4) il existe une application $f$ de $D$ dans $\N ^*$ telle que pour tout $x\in E-D$, et toute partie $F$ de $D$ dont l'adhérence contient $x$, il existe $r\in F$ tel que $f(r)d(x,r)\geq 1$
EDIT: patch voir post foys
5) $E$ n'est pas dénombrable
(En rajoutant (3), ça semble rendre la question nettement plus difficile. Mais éventuellement déjà, trouver un exemple, avec seulement 1-2-4, ce serait pas mal je pense).
(Je n'avais pas rajouté (5) à la question40, et au fond, c'est de là qu'est venu ton exemple, foys: la condition 4 continue, après le "il existe" par "pour tout x hors de D blabla" )
42) Trouver un énoncé $\forall x,y,..: terme_1=terme_2$ vrai dans tous les $M_n(K)$ et faux dans au moins un monoide. Remarque: l'énoncé de mpif contient un connecteur "implique"
Pour 41) on va prendre $E=[0;1]$ muni de sa distance usuelle $d(x,y)=|y-x|$ et $D= \mathbb Q \cap E$, les points de 1 à 5 sont trivialement vérifiés.
En fait le monoïde libre sur $n$ générateurs se plonge dans $M_2(\mathbb{N})$. Si une identité est vérifiée par les $M_n(K)$ alors elle est vérifiée par les monoïdes libres, et donc (en passant au quotient) par tous les monoïdes.
En claire si on a une formule $\forall x_1,\dots,x_n\ t(x_1,\dots,x_n)=t'(x_1,\dots,x_n)$ satisfaite par tous les $M_n(K)$ alors elle est satisfaite par tous les monoïdes.
En fait une identité passe au quotient mais pas une quasi-identité ! C'est ce qui rend possible mon exemple.
à mpif, non, je pense que tu te trompes, j'ai déjà expliqué pourquoi, mais à propos de $M_n(\N)$.
Il existe au moins un énoncé de la forme $P:=\forall ...:t_1=t_2$*** vérifié dans $M_n(\N)$ pour tout $n$ et qui est faux dans au moins un monoide (je ne traite le cas avec des $K$ quelconques, ton argumentation ne tourne pas autour de ça)
Preuve: l'ensemble des $P$ de la forme *** vrais dans tous les monoides est un ensemble $A$ récursivement énumérable non récursif. L'ensemble $B$ des énoncés $P$ de la forme *** vrais dans tous les $M_n(\N)$ est le complémentaire d'un ensemble récursivement énumérable et on a $A\subseteq B$. Si on avait $A=B$ alors $A$ serait récursif (et $B$ aussi d'ailleurs).
Ah oui, non pardon, c'est vrai que tu as raison!!!!!!!!!, je disais n'importe quoi, on a bien sûr besoin de dire faire des hypothèses!!!!! Toute mes excuses, et les hypothèses se traduisent bien par $m_1=n_1; m_2=n_2; ...\to c=d$
Le $A$ sans autoriser des connecteurs en question (avec le truc dont je parle) est un ensemble assez débile lool
Donc effectivement la forme de ton énoncé est la meilleure possible
Ce qui m'a fait me tromper est que je me focalise sur ta citation
et je te faisais le "procès d'intention" (involontairment) de croire que tu continuais de le défendre et donc je te lisais en diagonale. loool Et j'avais tort (ou plutôt raison de penser que tu le défendais, mais tu avais raison de le défendre)
Ahhhh mais décidément je ne lis pas assez soigneusement, vu que tu parles d'une identité, TU AS RAISON, dès le départ, j'ai lu "identité" comme une simple reformulation de ce que je demande pfffff. Toutes mes excuses
Bon je vais un post de récapitulation
Donc je reprécise bien: tu as bien trouvé un exemple qui répond à 34 (avec les corps), mais il en existe AUSSI*** avec l'anneau $\Z$, et la question reste donc en suspens
*** pour l'argument que j'ai dit.
Certes, tu pourrais contester que les $t_i$ et $x$ existent.
EDIT: j'ai aussi patché ici
44) Existe-t-il un énoncé purement universel vraie dans tous les $M_n[\Z]$ et fausse dans au moins un monoide??
(la 33 demande "vraie dans tous les $M_n(A)$, avec $A$ anneau commutatif et pas seulement dans tous les $M_n(\Z)$ )
1) $A$ est un anneau
2) $P$ est tel que $\exists z\in P:y=x+z$ est un ordre totale sur $A$
3) $P$ est stable par $+$ et par $\times$
4) tout élement non nul $x$ de $P$ est tel qu'il existe un élément $z\in P: x=1+z$
5) $P\cap -P=\{0\}$
6) $a\in A$ et $\forall x\in A:2x\neq a$ et $2x\neq a+1$
?
45)$\mathbb Z [X]$ avec $P$ l'ensemble des polynômes dont le coefficient dominant est positif, et comme $X$ et $X+1$ sont irréductibles, on prend $a=X$.
Par contre si $A$ est un anneau commutatif quelconque je ne sais pas trop.
En plus tu fournis un argument très simple (vrai dans $M_n(K)$ donc vrai dans $M_n(A)$ avec $A$ sous-anneau de $K$.
Ca me rappelle un fil de CLairon ! Je vais faire un fil séparé.
Ce qui génère une autre question métamathématique:
47) Peut-on caractériser élégamment les parties A de $\R$ telles que A-A est un voisnage de 0?
Soit $\theta_{k}>0$ des réels tels que $\sum\theta_{k}<+\infty$. On considère l'ensemble
\begin{equation*}
A=\left\{x\in\left]0\,,1\right[:
\begin{aligned}
&\text{l'inéquation $\left\lvert x-\tfrac{p}{q}\right\rvert<\tfrac{\theta_{q}}{q}$ ($p\in\mathbb{Z}$, $q\in\mathbb{N}^{*}$)}\\
&\text{admet une infinité de solutions}
\end{aligned}\right\}.
\end{equation*}
Alors $\lambda(A)=0$ ($\lambda$ est la mesure de Lebesgue).
longue vie à ce fil,
S
Edit : il n'y a pas de dérision, je n'ai pas cette capacité d'abstraction pour définir une question pertinente, je peux juste en apprécier la pertinence quand elle l'est et que j'ai pas trop de purée dans les yeux (je suis éducable quoi)
Salut Christophe.
Pourrais-tu donner une démonstration possible, ou les grandes idées, si ça ne te dérange pas ?
Merci
Imagine ton convexe "dynamique" similaire au convexe modèle, et on démarre avec une copie toute petite à l'intérieur du triangle. Il gonfle (en restant TOUJOURS similaire), se bute dans un côté, continue de gonfler en restant à l'intérieur, se bute dans un deuxième côté, là il peut encore continuer de gonfler et finalement est bloqué par le troisième côté, ça s'arrête là tu as ta copie similaire au modèle et inscrite dans le triangle.
A priori, même, cette copie est plus que similaire, elle est comment dire, image par une composée de translation et d'homothétie du modèle.
C'est valable pour toute dimension finie, pour tout convexe, et ce qui fait office de triangle (je ne sais pas comment ça s'appelle en dimension n; tétraedre en dimension 3)
En fait, j'avais en tête le lemme de Goursat, qui parle aussi de triangle convexe, et quand j'ai vu la question que tu posais, j'ai essayé de faire un rapprochement.
Mais je ne comprends pas grand chose à ton explication, c'est d'un niveau plus haut que le mien
Est-ce que l'idée dans le fond c'est d'utiliser des homéomorphismes et des difféomorphismes pour "modifier" le triangle ?
A+
Ah non non, c'est je pense "vox populi"... En fait, lis bien chaque détail et "imagine la scène"
Dès que j'ai du temps, je te la rédige "académiquement" en donnant des noms à tout ce qu'il faut. Maintenant, on peut contester le caractère formel, parce que c'est vrai que bof bof. Mais c'est bien plus facile que de jolis lemmes "exacts" de géométrie.
On ne modifie pas le triangle, on fait se balader dedans des homothétiques du convexe, en imaginant que les côtés du traingle sont "solides" et infranchissables.
Je me suis mal exprimé.
Tu as bien vulgarisé l'idée, mais je serai bien incapable de faire intervenir les bons objets mathémaatiques dessus.
51) Soit $A$ un anneau dont tous les éléments réguliers sont inversibles. Soit $B$ un sous-anneau de $A$ qui est noethérien. Existe-t-il forcément un sous-anneau $C$ de $A$ tel que $B \subseteq C$ et $C$ noethérien et tout élément régulier de $C$ est inversible?
L'exercice suivant échappe à la règle "être difficile", mais il est intéressant en ce qu'il offre une situation générale où des $\forall \exists$ deviennent "magiquement" des $\exists \forall$
52) Soit $\leq$ un odre total sur $E^n$. On suppose que $\forall (a_1,...,a_n)\in E^n\exists (b_1,...,b_n)\in E^n: (a_1,...,a_n)<(b_1,...,b_n)$. Prouver qu'alors $\forall a_1\in E\exists b_1\in E\forall a_2\in E\exists b_2\in E...: (a_1,...,a_n)<(b_1,...,b_n)$
Comme je suis paresseux, je fais pour n = 3.
Supposons à contrario Ea1 Qb1 Ea2 Qb2 Ea3 Qb3 (a1 a2 a3) >= (b1 b2 b3)
Je renote : (a1 a2(x) a3(x,y) ) >= (x y z)
(a1 a2(a1) a3(a1, a2(a1) ) >= (a1 a2(a1) z )
(a1 a2(a1) a3(a1,y) ) >= (a1 y z)
(a1 a2(x) a3(x,y) ) >= (x y z)
et par transitivité, (a1 a2(a1) a3(a1, a2(a1)) ) est maximum, contradiction.
Bon, bin le 53 va te faire tourner bourrique au niveau des notations si tu tiens à mettre des indices.
53) Soit $T:=E^\N$ muni de la topologie canonique (produit de la discrête)
Soit $n$ une application de $T$ dans $\N$
Soit $f$ une application de $T$ dans un ordre total $S$ telle que $\forall x\in T: f(x)$ ne dépend que de $(x_0;...;x_{n(x)})$
On suppose que pour tout $x\in T$ il existe $y\in T$ tel que $f(y)>f(x)$
Prouver qu'il existe une application continue $h$ de $T$ dans $T$ telle que $\forall x\in T: f (h(x)) >f(x)$
La différence avec le 52, c'est que au lieu de "s'arrêter" à n fixe, ça varie, tu ne peux donc plus dire, "je le fais pour n = 17 et on comprend le principe"
54) Soit $E$ un $\R$-espace vectoriel de dimension finie et $f$ une application de $E\to E$.
Pour tout $P:=a_0+...+a^kX^k \in \R[X]$, on pose $T(P)=a_0.id + a_1.f+ ... + a^k f^k$ où $f^k$ signifie $f o f ...of$ k fois.
On suppose que:
$\forall P,Q: T(P+Q)=T(P)+T(Q)$ et $T(PQ) = T(P) o T(Q)$
Question: $f$ est-elle forcément une application linéaire?
justement, à ce propos et avant de me lancer (peut-être) dans le 53, j'aimerais te soumettre la question que je me suis posée à propos du 52 : pour tout entier n explicitement écrit, on voit clairement le texte de la démonstration qu'il faut écrire pour démontrer l'énoncé concernant n. Bien entendu, ce n'est pas une démontration de : quel que soit n, ... Cela ne m'a pas posé de problème de conscience puisque, au-delà de ma paresse, je me suis dit que ton théorème n'en était pas un, mais bien plutôt un schéma de théorèmes, pour lequel je t'ai proposé l'une parmi un schéma de démonstrations. Par contre, ça m'a fait penser à ceci : supposons que j'aie un théorème d'arithmétique à démonter de la forme
(Quel que soit n) P(n)
et que je n'en trouve pas de démonstration (par récurrence par exemple), mais que pour tout entier n explicitement écrit, j'indique au lecteur le procédé de construction d'une démonstration
Demn de l'énoncé P(n).
Deux cas peuvent alors se produire (un troisième, que ¬ (Qn) P(n) soit un théorème ne me semble pas possible puisqu'alors, il serait vrai pour tout modèle, dont le standard, et un des énoncés P(n) démontrés explicitement serait contredit) :
- soit (Qn) P(n) est un théorème. Dans ce cas, sa (ses) démonstrations sont-elle nécessairement apparentées aux démontrations Demk ?
- soit (Qn) P(n) est indémontrable, ce qui me semblerait tout de même paradoxal. Connaîtrais-tu un exemple de cette situation ?
1) de prouver que pour tout n il existe une preuve dans T (peano par exemple) de P(n)
2) de prouver que pour tout n, P(n)
Un exemple simple est que pour tout n, tu peux prouver que n est standard, même pour les entiers non standard, par exemple, si tu te places en analyse non standard. Pour autant tu ne peux pas prouver que pour tout n, n est standard.
Un autre exemple est le suivant: pour tout n, tu peux prouver qu'il n'existe pas de preuve de 0=1 de longueur au plus n, dans T (par exmple Peano). Le schéma de la preuve est d'ailleurs simple tu dis aux gens: "regardez, je les essaie toutes, et constatez avec moi qu'auune ne conclut 0=1". Pour autant, "donner ce plan à l'auditoire" n'est en aucun cas une preuve de la consistance de T
Donc, il y a PLUS que 2 cas, il y en a en fait au moins trois et tu n'as pas précisé.
1) Prouver $\forall n: R(n)$
2) donner un programme dont tu peux prouver que pour tout n, il renvoit une preuve de R(n)
3) donner un programme dont tu peux prouver que pour tout n, s'il s'arrête alors il renvoie une preuve de R(n)
...
il y a plein de théories consistantes dans lesquelles, on réussir (2) et pas (1), pour certaines R
D'ailleurs à commencer par les plus simples: tu prends une théorie très faible T (genre avec juste de la récurrence autorisée pour des broutilles), mais dans laquelle tout ce ci a un sens, et tu rajoutes le schéma d'axiome pour chaque R: si pour tout n, R(n) est prouvable dans T alors $\forall xR(x)$. Et bien tu obtiens une théorie très forte dont tous les axiomes de Peano sont des théorèmes, aussi faible que T soit au départ (en gros).
En effet, essentiellement, si tu peux prouver $\forall x: R(x)\to R(x+1)$, alors tu peux prouver que si $R(n)$ est prouvable alors $R(n+1)$ l'est, mais ce dernier énoncé est un énoncé très très simple (au sens bas en complexité) qui ne concerne que des choses très finies, etc.
Prouver sans utiliser ni les déterminants, ni les formes alternées que si une matrice carrée à coefficients dans A est inversible, en tant que matrice vue dans B alors elle est inversible vue dans A.
(anneaux commutatifs unitaires, of course)