Identité remarquable indécidable
Bonjour, je me suis posé une question. Existe-t-il une identité remarquable vraie et indécidable ?
Je suis donc je pense
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Sauf à changer la signification de "identité remarquable", non. Car ça veut dire égalité prouvée utilisable. Si elle est indémontrable, on ne peut pas savoir si elle est utilisable.
Cordialement.
PS: encore écrit un message en même temps que quelqu'un d'autre...(enfin deux personnes) (tu)
Pour moi, une identité remarquable est une égalité entre deux polynômes à plusieurs variables dont les coefficients sont dans $\Bbb Z$ : "$P(X_1,\dots,X_n) = Q(X_1,\dots,X_n)$". Par exemple : "$(X_1+X_2)^2 = X_1^2+2X_1X_2+X_2^2$". Pour savoir si une telle égalité est vraie, il faut écrire $P$ et $Q$ sous forme développée et voir si leurs coefficients sont égaux. C'est 100% décidable comme procédure. Donc à la question de Quentin, je répondrais "non".
Edit : Suite à la remarque de Maxtimax, je rajoute l'hypothèse que $P$ et $Q$ ont des expressions explicites avec les entiers intuitifs 0, 1, -1, etc.
Il faut faire très attention dans ce genre de choses.
Si les polynômes $P,Q$ sont décrits avec des "vrais" entiers, alors comme tu le dis la procédure de décision est très simple. Mais il faut savoir comment on nous fournit cette identité (remarquable ou pas)
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Ça n'est pas à ce genre de polynômes que je pensais. :-D
Cordialement.
"démontrable" n'a aucun sens absolu. c'est relatif à une théorie donnée. Pour toute propriété bien écrite, il y a une théorie qui la démontre. Ne serait-ce, pour la propriété P, que la théorie dont le seul axiome est P (et comme P=>P, tu as la démonstration pour le même prix). Par suite, c'est la même chose pour "indécidable".
Cordialement.
Poirot: je vais essayer d'apprendre un peu de logique mathématiques
"indécidable" ne veut rien dire tout seul. Je rappelle les définitions précises:
1/ $T\vdash P$ signifie qu'il existe une preuve irréfutable (en maths on dit preuve tout court) de $P$ dont TOUS les admis sont dans $T$.
Oralement, ça se lit $T$ prouve $P$. ou encore $T$ démontre $P$.
2/ $P$ est indécidable par $T$ signifie que $T$ ne démontre pas $P$ et $T$ ne démontre pas non plus $(nonP)$.
3/ Pour toutes les théories mathématiques $T$ "utilisables humainement", c'est à dire dont la liste des axiomes est "facile" à définir, et qui n'est pas "trop" pauvre expressivement, il existe des phrases $P$ indécidables par $T$
4/ Pour toute phrase $P$, il existe, la plupart du temps, un énoncé sous la forme $Truc=Machin$ (post maxtimax, Salut à toi!!) dont $T$ prouve que c'est équivalent à $P$. Il était donc bon que tu précises que Truc et machin sont des polynômes
5/ Tu as oublié les $\forall$ devant les lettres qui figurent dans les polynômes, mais "on avait compris" et on les a rajoutés en te répondant ci-dessus
6/ Pour les théories simples en vigueur où les lettre désignent des choses proches de ce qu'on appelle "un nombre" (complexe compris), la réponse à ta question est "non". Tous les phrases de la forme
$$\forall ... \forall ..: Machin = Truc$$
sont décidables dans les théories "honnêtes" qui rendent l'énoncé "précis" aux yeux du lecteur. Par exemple, la théorie des groupes ne décide pas l'énoncé $\forall a,b: ab=ba$, mais c'est "fait exprès" en quelque sorte. Quand les gens parlent d'un groupe connu, "ils savent décider" humainement et "savent" humainement s'il rajoute ou pas l'axiome au cadre familier qu'ils vont traiter, ce qui revient à dire qu'un exemple "de groupe familier où on ne sait pas qu'il est commutatif sera un truc probablement très élaboré (ou qu'on manquera d'informations élémentaires à propos du groupe visé, même s'il est désigné par un nom)
7/ Mattar (Salut à toi Mattar!!) t'a répondu si on enrichit avec l'opération puissance, mais je n'ai pas vérifié dans le lien si la théorie est "honnête" (ref 6 ci-dessus). J'ignore que Peano décide toutes les égalités en expression polynomialo-puissancées précédées de $\forall$, mais je pense que oui, juste ç partir de mon expérience logicienne qui est que si ce n'était pas le cas, ce serait un tel sccop que beaucoup de médias spécialisés en aurait parlé (y comris si la réponse n'est pas connue).
8/ Bon bin, j'espère ne rien oublier :-D :-D
9/ Ah si le post de Mattar répond à ta question à propos de preuves particulières (enfin j'imagine) où la théorie ne serait constituée que "de règles de calcul". J'imagine que pour que le truc de Tarski ne soit pas une anecdote peu intéressante sa théorie est honnête à l'exception du fait qu'elle joue au jeu de ne contenir que des règles de calcul (bon j'irai lire la page wikipedia, car je te réponds en l'ayant entre aperçu 0.78 seconde, c'est pas très sérieux de ma part.
10/ Ne te demande pas longtemps si le fait qu'on ne connaisse pas de "théories usuelles" échappant à ce discours signifie qu'il n'en existe pas. On sait parfaitement en fabriquer, mais elles ne sont pas a priori passionnante, puisque fabriquer juste pour marcher.
Bref grosso modo l'identité remarquable $$\forall (n,x_1,...,x_d)\in \N \times \Z^d, 1=\min\left \{1,|P(m,x_1,...,x_d)| \right \} \tag 1$$ est "vraie" (pour les gens qui considèrent que ZFC est consistante du moins) mais "indécidable" (si on prouve $(1)$ dans ZFC, on peut transformer algorithmiquement cette preuve en une preuve de la non consistance de ZFC ce qui est le vrai contenu du 2ième théorème de Gödel: il s'agit d'une démonstration à trous de $\bot$ dans ZFC ou autre système idoine, attendant une preuve de la consistance du système pour être complétée).
$$
\forall X, \ P(X)\neq 0
\qquad\text{en}\qquad
\forall X,\ \min\big(1, P^2(X)\big) = 1.
$$ Ce qui "trahit" (gentiment) l'INTENTION PROBABLE du demandeur telle que précisée ensuite quand il a restreint aux polynômes son désir.
A noter que cette "impossibilité" ou "grande difficulté" à demander les vertus du polynomial à l'opération min (ou de manière équivalente à l'opération $x\mapsto |x|$) intervient dans de nombreux champs des mathématiques. Par exemple dans le poids alourdit, bien que ce soit accessoire la preuve de Stone Weirstrass, ou encore dans le degré minimum pour rendre les équations diophantiennes difficiles, et bien d'autres situations.
(Précision, j'ai transformé ton $|x|\geq 1$ en $x^2\geq 1$, mais sans trahir ton propos)
concernant l'identité algébrique de Tarski on peut la démontrer par factorisation du premier membre et factorisation du second membre
Elle se présente avec x et y réels positifs sous forme de fonctions exponentielles :
$[(1 + x)^y + (1 + x + x^2)^y]^x[(1 + x^3)^x + (1 + x^2 + x^4)^x]^y = [(1 + x)^x + (1 + x + x^2)^x]^y[(1 + x^3)^y + ( 1 + x^2 + x^4)^y]^x$
Les identités remarquables du 3ème degré permettent de factoriser :
$(1+x^3)^x = (1+x)^x(1-x+x^2)^x$ et $(1+x^3)^y=(1+x)^y(1-x+x^2)^y$
En prenant le début du carré de l’expression du 4ème degré il vient : $(1+x^2)^2 - 2x^2 + x^2 = (1 - x + x^2)(1 + x + x^2)$
d’où : $(1 + x^2 + x^4)^y = (1 - x + x^2)^y(1 + x + x^2)^y $ soit :
$[(1+x)^y + (1 + x + x^2)^y]^x[(1+x)^x(1 - x + x^2)^x + (1 - x + x^2)^x(1 + x + x^2)^x]^y$ =
$[(1+x)^x + (1 + x + x^2)^x]^y[(1+ x))^y(1 - x + x^2)^y + (1 - x + x^2)^y(1 + x + x^2)^y]^x$
en factorisant au premier et second membre par $( 1 - x + x^2)^{xy}$ on vérifie l’égalité :
$(1 - x + x^2)^{xy}[(1 + x)^y + (1 + x + x^2)^y]^x = (1 - x + x^2)^{xy}[(1 + x)^y + (1 + x + x^2)^y]^x$
cette identité algébrique de Tarski reste valable dès la formule originelle lorsque x est variable complexe
en particulier si x = 1 + i et y = 1 - i d'autre part pour x = - j et x = - j² l'identité est nulle au premier et second membre
L’intérêt scientifique de cette identité homogène de degré 2xy n’est pas évident.
x apparaît comme variable principale prise dans C (et y simple paramètre)
d’une fonction puissance associée à une fonction exponentielle.
Cordialement