Demande de rappels
Dans ce fil, je poste des questions dont je sais qu'elles sont résolues mais me rappelle plus la réponse. Un grand merci d'avance à celles et ceux qui répondront. (Pardon, c'est de la pure logique). J'ai croisé un jour les réponses dans diverses BR ou conversations les ai retenues un temps, puis oubliées avec la vieillesse.
1/ Définition de $\N$ dans $(\Q, +,\times)$. Je crois me rappeler qu'elle existe, mais n'ai plus aucune idée de ce qu'elle est (je l'avais croisée dans une BR)
2/ Indécidabilité (non récursivité) de l'ensemble des équations polynomiales à coefficients entiers qui ont au moins une solution qui soit un uplet de nombres rationnels.
3/ Définition de $+$ dans $(\Z, \times , x\mapsto x+1)$
4/ (Vague) approximation canonique d'une fonction continue quelconque par une fonction $C^\infty$ (je ne sais même pas, même peut-être analytique) à l'aide d'une convolution astucieuse
5/ Preuve de l'indécidabilité de la logique propositionnelle intuitionniste du deuxième ordre pure (les phrases sont par exemple de la forme $\forall X\exists Y: (X\to Y)\to Y$ ). Je pourrais certes essayer de le faire en exercice, mais autant demander.
A suivre...
1/ Définition de $\N$ dans $(\Q, +,\times)$. Je crois me rappeler qu'elle existe, mais n'ai plus aucune idée de ce qu'elle est (je l'avais croisée dans une BR)
2/ Indécidabilité (non récursivité) de l'ensemble des équations polynomiales à coefficients entiers qui ont au moins une solution qui soit un uplet de nombres rationnels.
3/ Définition de $+$ dans $(\Z, \times , x\mapsto x+1)$
4/ (Vague) approximation canonique d'une fonction continue quelconque par une fonction $C^\infty$ (je ne sais même pas, même peut-être analytique) à l'aide d'une convolution astucieuse
5/ Preuve de l'indécidabilité de la logique propositionnelle intuitionniste du deuxième ordre pure (les phrases sont par exemple de la forme $\forall X\exists Y: (X\to Y)\to Y$ ). Je pourrais certes essayer de le faire en exercice, mais autant demander.
A suivre...
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pour 1/ : on voit qu'il suffit de définir les entiers (car un entier est positif si et seulement s'il peut s'écrire $a^2+b^2+c^2+d^2$, $a,b,c,d$ des entiers). Ensuite la formule qu'elle donne pour définir les entiers est remarquablement compliquée, mais je ne suis pas persuadé qu'il y ait plus simple. Il s'agit de $\small\forall A,B, (((\exists x,y,z, 2+bz^2 = x^2+Ay^2)\land \forall M, (( \exists x,y,z, 2+ABM^2+Bz^2=x^2+Ay^2)\implies (\exists x,y,z (2+AB(M+1)^2+Bz^2=x^2+Ay^2)))\\\implies \exists x,y,z, 2+ABn^2+Bz^2=x^2+Ay^2))$ (pour dire que $n$ est entier). Notons que $2$ est définissable sans trop de souci car $1$ l'est (via $\times$)
Pour 3/ : on peut définir $0$ dans cette structure ($\forall x, x\times 0 = 0$), donc $-1$ ($-1+1 = 0$). Ensuite on dit que $a+b=c$ si et seulement si : ($c=0$ et $a= -1 \times b$) ou ($c\neq 0$ et $(ac+1)(bc+1)= (ab+1)c^2 +1$)
ça marche : le cas $c=0$ est clair, le cas $c\neq 0$ vient du fait que cette égalité est vraie si et seulement si $abc^2+bc+ac +1 = abc^2 + c^2+1$ si et seulement si $(b+a)c = c^2$ si et seulement si $b+a=c$ (elle traite dans son article le cas $c>0$ mais en fait on n'a besoin que de $c\neq 0$, et le cas $c=0$ se traite à part)
2/ Ce n'est pas le 10è problème de Hilbert ? Résolu par Matiassevitch
4/ Il s'agit de prendre une fonction $f:U\to \mathbb{R}$ continue, $U\subset \mathbb{R}^d$ un ouvert; on peut clairement supposer $U=\mathbb{R}^d$ si on veut simplement une approximation locale; et alors on prend $\zeta$ une fonction $C^\infty$ de support inclus dans la boule euclidienne de rayon $1$ autour de $0$, d'intégrale $1$; et on peut alors poser $\zeta_\epsilon (x) := \frac{1}{\epsilon^d}\zeta(\frac{x}{\epsilon})$ qui reste de masse totale $1$ (elle la "concentre" autour de $0$). Alors $\zeta_\epsilon * f (x) := \int_{\mathbb{R}^d} f(y)\zeta_\epsilon(x-y) \mathrm{d}y$ va tendre vers $f$ uniformément sur tout compact lorsque $\epsilon$ tend vers $0$, et sera $C^\infty$.
5/, 6/ ,7/ Aucune idée
On a un très bel exemple ici de la valeur des travaux féminins soit dit en passant!!
Pour (2) non c'est pour les entiers Matiyasevic. Mais je vais voir si grâce à 1 ça se retrouve.
(Et non, malheureusement j'ai dû retrouver l'article :-D surtout pour la définition de $\Z$ dans $\Q$ dont j'avais le souvenir d'avoir été persuadé qu'elle n'existait pas)
Ah effectivement mais je pensais justement que les problèmes étaient équivalents (pas de manière immédiate mais je pensais tout de même)
Non mais par contre $8(4x^2-1)=0$ doit marcher... je post l edit avant de justifier
@lmpc :-D :-D :-D j'ai admiré ton combat pour justifier l'existence de solutions quand $(0,...)$ en est une. Ca m'arrive souvent aussi, c'est assez épuisant. Il y a pire, c'est quand on prouve $(u=v)\to (A\vee 3u=3v)$ en 5 pages en ayant tellement été concentré sur le $A$.
$\forall A,B: $
$ (($ $(\exists x,y,z, 2+bz^2 = x^2+Ay^2)$ et si pour tout $M: $
$(( \exists x,y,z: 2+ABM^2+Bz^2=x^2+Ay^2) \to (\exists x,y,z (2+AB(M+1)^2+Bz^2=x^2+Ay^2)))$
Alors
$\exists x,y,z, 2+ABn^2+Bz^2=x^2+Ay^2))$
J'essaierai d'améliorer la disposition ultérieurement.
$a^2+b^2+c^2+d^2=-1$ (on applique le théorème des 4 carrés^^)
Une preuve : les anneaux sont supposés commutatifs unitaires, finis, donc on peut parler de leur caractéristoque, nécessairement finie. Donc $-1= n-1$ pour un entier $n\geq 2$ (sauf si l'anneau est nul, auquel cas toute équation est satisfaite), donc en appliquant les 4 carrés on a une solution. Elle n'a évidemment pas de solution dans $\Z$
D'ailleurs unitaire suffit (un anneau, même non commutatif, a une caractéristique)
pour le 7) on peut faire avec une equation á 1 variable. Je tire ça d'un vieux post du membre Doraki sur maths forum: c'est
$(x^2+23)(x^3-x-1)=0$
Et c est un exercice intéressant d'algebre de vérifier que ça marche
Concernant le (3), je viens de le donner en défi à ma classe de 1S (qui est en train de réfléchir sous mes yeux) avec récompense de 20 de moyenne au T3.
Merci héhéhé, en fait, je m'en servais toujours** sans le savoir, mais je remercie grandement ce qui m'ont répondu quand-même bien sûr.
** quand je floute des images (j'aime bien faire ça), je fabrique une $g : x \mapsto $ moyenne des $f(t)$ quand $t$ est voisin de $x$, avec pondération qui tend vite vers $0$ quand il s'éloigne de $x$. Le fait que nous soyons plusieurs au monde est super, on peut remplacer le fait de re-réfléchir à un truc pendant 5H à froid par une demande à un camarade.
Au fond de moi, je pense que ma vraie question réellement désirée est "est-ce que ça donne une analytique, ou juste une $C^\infty$ de faire ça, et si non, est-ce qu'il y a des moyens similaires d'obtenir une analytique (peu importe la sévérité de l'exigence de convergence)?"
Je crains que les visiteurs du présent fil soit plus des passionnés de logique que la moyenne (ce n'est pas un reproche, mais il y a des tas d'algébristes sur le forum qui ne mettent pas les pieds en logique).
Et merci ModuloP!
> Au fond de moi, je pense que ma vraie question réellement désirée est "est-ce que ça donne
> une analytique, ou juste une $C^\infty$ de faire ça, et si non, est-ce qu'il y a des moyens
> similaires d'obtenir une analytique (peu importe la sévérité de l'exigence de convergence)?"
Un théorème de Whitney dit que pour toute fonction continue $f:\mathbb R^n\to \mathbb R$ et pour toute fonction continue $\epsilon : \mathbb R^n\to {]0,+\infty[}$, il existe une fonction analytique $\tilde f:\mathbb R^n\to \mathbb R$ telle que $|\tilde f -f|<\epsilon$ sur $\mathbb R^n$.
Ici, je m'intéressais peut-être plus au genre de preuve pour obtenir ce genre de résultat plus qu'au résultat lui-même. Obtient-on Whitney en faisant quelque chose qui ressemble à de la convolution.
(Je m'intéresse depuis quelques temps au supplément de force que donnent les stratégies consistant à jouer ses coups en les tirant (en partie) au sort, car on a semble-t-il pas mal de choses qu'on ne sait pas prouver autrement).
$(x^2-3)(x^2-5)(x^2-15)=0$
(ou encore, pour rester proche de ModuloP: $(x^2+1)(x^2+5)(x^2-5)=0$)
EDIT: En fait, aucun des deux ne marchent modulo 8! Les puissances de 2 sont un peu récalcitrantes. Donc je rectifie:
$(x^2+1)(x^2-7)(x^2+7)=0$. Sauf erreur, celui la marche. Fin de l'EDIT)
Si quelqu'un veut faire un post lá dessus dans la section algebre (ou arithmétique, c est borderline), qu'il n'hésite pas. Sinon je le ferai peut être.
Il serait notamment intéressant de savoir jusqu'á quel degré on peut descendre.
Si tu arrives a trouver un polynôme de degré inférieur à $5$, je serai vraiment surpris !
En admettant l'hypothèse du continu, il existe une involution $f$ de $\mathbb{R}$ telle que [pour tout $E$] $f(E)$ est Lebesgue-négligeable si et seulement si $E$ est maigre.
- est-ce que ça t'embête qu'il faille admettre l'hypothèse du continu ?
- est-ce que tu as accès au livre ?
[EDIT] - et puis, comme j'ai toujours peur de dire des bêtises, je ne suis pas sûr que ça réponde à ton 6), ta confirmation me rassurerait :-D
1) Pardon pour mon manque de disponibilité
2) Grand merci à héhéhé dont je ne vois que maintenant le post
3) @GA: euuu oui, le fait d'utiliser l'hypothèse du continu tue tout lien avec la question 6 car elle concerne les "cardinal invariant", c'est à dire la classification des cardinaux compris entre celui de IN et celui de IR. En fait, on a "constaté" que quand une inégalité avait toujours lieu, on parvenait toujours à construire une réduction de Tukey plus générale l'impliquant.
(et ici aussi mais je n'ai pas lu en entier)
$\mathbb{Z/13Z}$ ?
Amicalement
Paul
* si j'ai bien compris.
A est l'anneau fini choisi par le démon. J'abrege par n l'élément n.1.
si 2n+1=0 alors c'est bon (n+1 est solution). Sinon si 2(3n+1)=0 idem et si 2(3n+2)=0 idem aussi. CQFD.
10/ J'aurais besoin de savoir si les matrices symétriques qui sont semblables à une matrice de la forme $N+^tN$ où $N$ est $k$-nilpotente sont étudiées sous le contexte que $k$ tel que est imposé et assez fixe pendant le problème et les ordres des matrices eux sont gros par rapport à $k$ et varient.
Je ne ferai pas de mystère sur le fondement de ma question, elle provient du fait qu'une matrice d'adjacence de graphe non orienté $G$ est telle que $G$ est coloriable avec $k+1$ couleurs ssi elle a la propriété ci-dessus à la contrainte près que la matrice de passage est une matrice de permutation. Il suit que les matrices ayant la propriété ci-dessus sont des sortes de matrices "quantiquement" $k+1$ coloriables si on peut dire (à moins qu'il n'y ait un théorème de Brauer pour le cas général).