"Il est facile de 2"

christophe c

Exercice 630: en bleu dans le fil en lien

Foys

Sauf erreur, 630 est faux.
En fait soit $e\in E$. Alors $card \big ( f^{-1} (\{e\})\big ) \leq n$. Sinon, il existe au moins $n$ éléments $x_1,...,x_n$ distincts dans $f^{-1} (\{e\}) \backslash \{e\}$ et $f(\{ x_1,...,x_n\}) = \{e\}$ est disjoint de $\{x_1,...,x_n\}$.

christophe c

Tu as raison sur le fait que l'exercice est faux, mais pas sur ton argument (que je ne comprends pas), je pense: en posant $E:=\N$ et $f(X)$ le maximum de $X$, tout le monde a un nombre fini d'antécédents. En fait, ce qu'on peut prouver c'est que pour tout $p\in \N$ il n'y a qu'un nombre fini d'éléments de $E$ qui ont au plus $p$ antécédents. (JE fais une modif dans le post)

Foys

Comme je ne sais plus lire, j'ai cru qu'on supposait "$f(X) \subset X$" (alors que c'est $f(X) \in X$). Ca change tout :-)

Foys

630. Si $F \subseteq E$ appelons $A_F$ l'ensemble des parties de $F$ de cardinal $n$. Soit $N \in \N$, $N \geq n$. Supposons qu'il existe $F\subseteq E$ de cardinal $N$, tel que $\forall x \in F$, $card \big ( f^{-1} (\{x \}) \big ) \leq p$. Alors: $A_F = \bigcup_{x \in F} f^{-1} (\{x\}) \cap A_F$. Autrement dit $A_F$ est réunion de $N=card (F)$ ensembles eux même de cardinal au plus $p$. Donc $$card( A_F) = \binom {N}{n} = \frac{N(N-1)...(N-n+1)}{n!}\leq pN$$ Comme $n\geq 2$, $N$ ne peut être arbitrairement grand. (on a même une majoration explicite: $N \leq \sqrt[n-1]{pn!}+n-1$)

christophe c

Ah ouiii, bravo foys!!! (tu)

christophe c

Question 631: on ne suppose pas l'axiome du choix complet, mais seulement l'axiome du choix dépendant. Soit $T$ une partie de $P(\R)$ telle que pour tout $A\subset \R$, il existe un ouvert $U$ de $\R$ tel que $\{x\in \R\mid A(x)\neq U(x)\}\in T$. Alors a-t-on forcément que tout ensemble maigre est inclus dans un élément de $T$?

christophe c

Question 632: soit $A\subset \R^\R$ tel que $\forall B\subset \R^2\exists f\in A: f\subset B$ ou $f\subset \{(x,y)\in \R^2\mid (y,x)\notin B\}$. On note $d:=card(A)$ et $d^+$ le premier ordinal tel qu'il n'y a pas de surjection de $d$ sur $d^+$. Il est évident que $d\leq card(2^\R)$

Exercice632.1: prouver que $d^+\geq card(2^\R)$

Exercice632.2: prouver que si $card(\R)=\omega_1$ alors $d=card(2^\R)$

Question 632.3: peut-on prouver que $d=card(2^\R)$?

christophe c

[large]Question 633: en bleue dans le fil en lien[/large]

marco

Question 633: Soit $E=\ell^2(\N)$, et pour tout $n,k \in \N$, $e_n(k)= \delta_{n,k}$. Soit $F=B(0,1)$ et $f$ définie par $\sum x_n e_n \mapsto \sum \frac{x_n}{n+1} e_n$. Alors $f(F)$ est compact donc fermé. Si $f(E)$ était fermé, alors comme $f(E)$ est dense, on aurait $f(E)=E$, donc $f$ est un isomorphisme, ce qui est faux.
Peut-être je me suis trompé.

christophe c

Bravo marco. Du coup je mets une remarque dans l'autre fil où j'ai donné un mauvais conseil.

christophe c

Question 634: inspirée par le fil http://www.les-mathematiques.net/phorum/read.php?16,1187665,1191945#msg-1191945

n'ayant pas vraiment le temps ni la possibilité technique de me connecter facilement, voici une petite question toute bête, qui ne me smble pas évidente à première vue. Peut-être l'est-elle...

On se place dans ZF pur canal historique, c'est à dire où le schéma de remplacement est précisément le suivant: pour toute relation binaire définie éventuellement avec paramètres, $R$ telle que $\forall x\exists ! y R(x,y)$, et tout ensemble $a$, il existe un ensemble $b$ tel que pour tout $x$, $x\in b$ ssi il existe $u\in a: R(u,x)$

On ne suppose en particulier aucun axiome de fondation ni axiome du choix aussi légers soient-ils.

L'énoncé suivant est-il consistant avec ZF (j'ai l'impression que non mais peu de dispo pour le vérifier): tout ensemble est réunion dénombrable de parties dénombrables?

Mattar

634 : cet article répond à une question plus faible : il est consistent que tout ensemble est réunion dénombrable d'ensembles de cardinalité plus petite, en supposant la consistance de l'existence d'une classe propre de cardinaux fortement compacts.

christophe c

Oh génial: merci! Je m'empresse de trouver un PC pour le lire

christophe c

Ah bin, je suis un peu bête. L'énoncé bleu 634 est bêtement faux, je viens de trouver une preuve presque triviale** qu'il est faux. A noter par ailleurs que l'article de mattar montre que l'énoncé suivant est consistant avec ZF: tout ordinal limite a une cofinalité égale à IN

** du coup je le laisse en exercice, il n'est vraiment pas difficile

Indication: pour tout ordinal $a$, tout ensemble $A$, il existe un ensemble $E$ qui n'est pas réunion d'une famille $U: a\to P(E)$ telle que pour tout $i\in a$ il existe une surjection de $A$ sur $U(i)$

Foys

634: Je dirais à vue de nez que si $E$ est union dénombrable de parties dénombrables alors il existe une application surjective $f: \N^2 \to E$. Pour $E=P(\N^2)$ on sait que c'est faux via $F=\{x \in E| x \notin f(x)\}$

EDIT sauf que la construction de $f$ n'est pas possible sans AC :-D

Foys

634: Soit $\alpha$ un ordinal et $E \subseteq \alpha$. Alors $E$ est bien ordonné, d'où un ordinal $\alpha_E$ et une bijection croissante (unique: ce qui suit ne nécessite donc pas AC mais je n'ai pas la motivation pour formaliser (:D)$f_E:\alpha_E \to E$. Par induction on montre que $\forall x \in \alpha_E, x \leq f_E(x)$. Donc que $\alpha_E \subseteq \alpha$.
Soit $\omega$ le premier ordinal non dénombrable. Soit $x$ un ordinal. Alors s'il existe $(E_n)_{n \in \N}$ une famille dénombrable de parties de $x$ telles que $x = \bigcup_{n \in \N} E_n$ , on pose $f: (p, \beta) \in \N \times \omega \mapsto f_{E_p}(\beta)$ si $\beta < \alpha_{E_p}$ et $\emptyset $ sinon. Alors $f$ est surjective de $\N \times \omega$ dans $E$. Sauf que $\N \times \omega$ est bien ordonné. Donc pour tout $y \in x$ posons $\varphi(y) = \min f^{-1} (\{y\})$. $\varphi$ est une bijection sur une partie de $\N \times \omega$. On voit donc que tout ordinal union dénombrable d'ensembles dénombrables est isomorphe à un élément de l'ensemble des $(A, R)$ où $A$ est une partie de $\N \times \omega$ et $R$ est un bon ordre sur $A$ (on a affaire à une partie de $P(\N \times \omega) \times P \big( (\N \times \omega) ^2\big )$ et on exploite le schéma de compréhension). On conclut avec le schéma de remplacement et le fait qu'il n'y a pas d'ensemble des ordinaux.

christophe c

@foys, tu as oublié de dire ce que tu prouves, faut le repérer dans l'argument.

Bon je ne laisse pas en exo le truc et donne sans détail une preuve que l'énoncé évoqué par mattar est le plus fort possible qu'on puisse espérer. Soit $A,B$ deux ensembles. Je prouve qu'il existe un ensemble $E$ tel qu'il n'existe pas de réunion $i\in A\mapsto B_i$ d'ensembles recouvrant $E$ tels qu'il y a une surjection de B sur chaque $B_i$.

Soit $\mu$ un ordinal tel qu'il n'y a pas de surjection de $B$ sur $\mu$. On s'intéresse à $E:= \mu ^A$. Soit $i\in A\mapsto B_i$ qui recouvre $E$. Il existe (exercice) un élément $a\in A$ tel que pour tout $j\in \mu$, il existe $f\in B_a$ tel que $f(a)=j$. Il n'est donc pas possible qu'il y ait une surjection de $B$ sur $B_a$.

Foys

christophe c a écrit:

@foys, tu as oublié de dire ce que tu prouves, faut le repérer dans l'argument.

Je montre qu'il existe un ensemble $A$ tel que $\forall x$, $x \in A$ si et seulement si $x$ est un ordinal réunion dénombrable d'ensembles dénombrables. Il existe des ordinaux qui ne vérifient pas ette propriété puisqu'il n'y a pas d'ensemble des ordinaux (ce qui est amusant est que cette preuve est non-constructive, malgé l'absence totale d'axiome du choix).

christophe c

Pour les lecteurs intéressés, je précise l'axiome de grand cardinal utilisé dans l'article mis par mattar. Un cardinal $c$ est fortement compact quand pour tout ensemble $E$, tout filtre $c$-additif sur $E$ se prolonge en un ultrafiltre $c$-additif sur $E$.

Un ensemble $X$ est $c$-additif signifie que pour tout partie $P$ de $E$ de cardinal $<c$, l'intersection des éléments de $P$ est un élément de $E$.

Un axiome de grand cardinal un peu plus célèbre, mais pas tellement plus fort est l'existence de cardinaux supercompacts. Un cardinal $c$ est supercompact quand pour tout ensemble $E$, il existe un ultrafiltre $W$ $c$-additif sur $P_{<c}(E)$ tel que pour toute fonction choix $f$, il existe $a\in E$ tel que $\{X\subset E\mid f(X)=a\}\in W$. Un cardinal supercompact est évidemment fortement compact.

Un axiome encore plus fort est celui de l'existence de cardinaux dits "extendible". Un cardinal $c$ est dit extendible quand toute théorie du second ordre $c$-consistante est consistante ($c$-consistante signifie que toutes ses parties de cardinal $<c$ sont consistantes). Attention ici consistante signifie "avoir un modèle plein du second ordre".

Un axiome encore plus fort, et peut-être le plus spectaculaire est la Vopenka Conjectur. Il dit que toute classe C de structures qui n'est pas un ensemble est telle qu'il existe $a,b$ distincts dans $C$ et un plongement élémentaire de $a$ dans $b$.

On peut monter plus haut, mais ces axiomes de grands cardinaux sont encore peu utilisés dans des résultats connus de consistance relative d'énoncés concernant les petits objets.

christophe c

@foys, ta preuve établit que $\omega_2$ n'est pas réunion dénombrable d'ensembles dénombrables. En effet, tu mets une surjection de $\omega_1$ sur $x$ dès lors que $x$ est un ordinal qui est réunion dénombrable d'ensembles dénombrables. Le même raisonnement établit que si un ordinal $a$ est réunion dénombrable d'ensembles sur lesquels il y a une surjection du cardinal infini $b$ dessus alors $card(a)\leq card(b^+)$

à noter aussi que le résultat de consistance relative que mattar nous apprend est spécial car ne correspond pas à "la philosophie ZF". Autrement dit les univers dans lesquels tous les ordinaux limites ont une cofinalité IN ne sont pas "hauts" car tout surunivers qui les contient et vérifie AC rend tous leurs ordinaux dénombrables.

christophe c

Question 635: on est dans ZF + AF + choix dépendant. On suppose que toute application $P$ de $P(\N)$ dans $\R$ telle que $\forall A,B\subset \N: $ si $A\cap B=\emptyset$ alors $P(A\cup = P(A)+P(B)$ est sigma-additive.

635.1) Est-ce que ça entraine que toute partie de IR est Lebesgue mesurable?

635.2) Est-ce que ça entraine l'axiome de détermination?

christophe c

Question 636: un espace compact $E$ est dit lisse quand son groupe d'homéomorphismes agit transitivement sur lui. Ces mots savants :-D pour dire $\forall x,y$ dans $ E\exists f\in H: f(x)=y$ où $H:=$ l'ensemble des homéomorphismes de $E\to E$.


636.1) (il me semble l'avoir déjà prouvé, mais me rappelle plus): existe-t-il un cardinal $c$ tel que tout compact lisse a un cardinal $\leq c$.

636.2) Est-ce que pour tout compact lisse $E$ et toute injection continue $f:E\to E: f$ est surjective?

question637) un espace compact est dit superlisse quand pour tous $x,y$ dans $E$, il existe une involution continue $f:E\to E$ telle que $f(x)=y$.

637.1) (il me semble l'avoir déjà prouvé, mais me rappelle plus): existe-t-il un cardinal $c$ tel que tout compact superlisse a un cardinal $\leq c$.

637.2) Est-ce que pour tout compact superlisse $E$ et toute injection continue $f:E\to E: f$ est surjective?

christophe c

Question 638:

Un graphe est une clique quand tous ses sommets sont deux à deux reliés.

J'appelle "graphe flasque" un graphe dont tous les sous-graphes qui sont des cliques sont dénombrables

Soit $(E,T)$ un espace topologique. J'appelle $Gra[E]$ le graphe dont les sommes sont les ouverts non vides (les éléments de $T$) et deux ouverts $U,V$ sont reliés quand $U\cap V=\emptyset$.

Je note $G\leq H$ (entre deux graphes) quand $\exists f: sommets(G)\to sommets(H)$ tel que pour toute arête $(x,y)$ de $G$, $(f(x),f(y))$ est une arête de $H$.

Est-ce que pour tout graphe flasque $G$ il existe un espace topologique $E$ avec $G\leq Gra[E]$ et $Gra[E]$ flasque?

Pea

Il me semble qu'on peut aisément répondre aux questions 636.1), 636.2), 637.1) et 637.2) en remarquant que si $K$ est un espace compact lisse (resp. superlisse) alors pour tout ensemble $I$ il en va de même de $K^I$.

christophe c

Merci et bravo Pea

christophe c

Question 639:

Peut-on prouver dans $T$ que l'existence d'un ordre total sur P(IR) entraine celle d'un bon ordre sur IR?

Ca fait une question $639_T$ par théorie $T\in \{ZF; ZF+AF; ZF+AF+ChoixDep\}$

Remarque: je pense que non, mais j'ai la flemme de faire un forcing pour ajouter un ordre total sur P(IR) dans un modèle de AD(IR), puis vérifier que ça ne suffit pas à créer un bon ordre sur IR

La question est inspirée de http://www.les-mathematiques.net/phorum/read.php?16,1187665,1198735#msg-1198735

christophe c

Question 640 (en l'honneur de Cantor), inspirée par un fil récent.

Définition: on dira qu'une partie $A$ de $\R$ est grosse quand pour toute suite $a\in \C^\N$, si $\forall x\in A$, la série $\sum_{n\in \N} a_n exp(in\pi)$ converge vers $0$ alors $a$ est la constante nulle.

On se place maintenant dans $T:=ZF +choixdep$. L'axiome suivant est-il consistant avec $T$?

axiome: pour tout partie $A$ de $\C$, il existe un ouvert $U$ de $\C$ et une partie $X$ de $\C$ qui est grosse et telle que $\forall x\in X: A(x)=U(x)$

Pea

Concernant la question 638: j'imagine que par graphe tu entends un graphe simple (i.e. deux sommets sont reliés par au plus une arête et un sommet n'est jamais relié à lui-même) et non-orienté. Il me semble alors que ta question est équivalente à la suivante (je suspecte d'ailleurs fortement que la réponse à cette dernière est non mais je n'ai pas de contre-exemple à proposer):

Est-ce que tout graphe flasque a un nombre chromatique dénombrable?

L’équivalence découle je crois des lemmes faciles suivants:

Lemme 1: Soit $E$ un espace topologique. Alors $Gra[E]$ est flasque ssi $E$ est séparable.

Lemme 2: Si $E$ est un espace topologique séparable alors $Gra[E]$ a un nombre chromatique dénombrable.

Lemme 3: Si $H\leqslant G$ alors $\chi(H)\leqslant \chi(G)$ où $\chi(G)$ désigne le nombre (cardinal) chromatique d'un graphe $G$.

Lemme 4: Si le nombre chromatique d'un graphe $G$ est $\kappa$ alors $G\leqslant K_{\kappa}$ où $K_{\kappa}$ désigne le graphe complet à $\kappa$ sommets.

Lemme 5: Pour tout cardinal $\kappa$ il existe un espace topologique $E$ de cardinal $\kappa$ (par exemple un espace discret) tel que $K_\kappa\leqslant Gra[E]$.

christophe c

Hélas ton lemme1 est faux: un produit quelconque d'espaces flasque est flasque. Par contre la réponse à 638 est non pour une raison beaucoup plus terre a terre (de mon téléphone).

Maintenant que je suis sur un pc, je peux donner une indication pour prouver la réponse non à 638. Trouver un graphe tel qu'il n'y a pas dedans 3 sommets deux à deux reliés et qui est un contre-exemple "évident" à [638.oui]

Remarque: on peut même choisir ce graphe coloriable avec deux couleurs

Pea

A christophe: effectivement mon lemme 1 est faux, j'ai raconté n'importe quoi! Par contre,je ne sais pas si je délire encore mais si $G$ est $2$-coloriable on a $G\leqslant K_2$, non? Comment peut-on dans ces conditions trouver un contre-exemple $2$-coloriable?

christophe c

Bin justement, ce n'est parce qu'un graphe est 2-coloriable qu'il est $\leq$ à un $ Gra[E]$ , avec $gra[E]$ flasque.

Bon, je te donne une solution très simple, car je vais peut-être me déconnecter.

Tu prends n'importe quel ensemble $X$. Tu prends $2\times X$. Tu relis $(i,x)$ avec $(j,y)$ quand $i\neq j$ et $x\neq y$. Tu as la 2 coloration $(x,i)\mapsto i$. Il n'y a donc pas de grosses antichaines.

Soit $(E,T)$ un espace topologique et $f: 2\times X\to T$. La famille d'ouverts $x\mapsto f(0,x)\cap f(1,x)$ est une famille d'ouverts deux à deux disjoints, quand elle est constituée d'ouverts non vides. Il reste ensuite à travailler un peu pour se ramener à cette situation (me semble-t-il). Remarque, je n'ai pas vérifié, je n'en suis pas sûr. Disons que c'est une idée en passant.

Pea

Christophe:pourtant avec ta définition si $G$ est $2$-coloriable il me semble bien que $G\leqslant Gra[E]$ où $E$ est par exemple l'espace topologique discret à $2$ éléments (car alors $Gra[E]$ contient une $2$-clique), non?

christophe c

oula oui, tu as parfaitement raison . Du coup, l'exercice reste intéressant à l'instant de maintenant

christophe c

Question 642 : http://www.les-mathematiques.net/phorum/read.php?16,1199715,1199715#msg-1199715

Question 643: http://www.les-mathematiques.net/phorum/read.php?4,1199023,1199023#msg-1199023

christophe c

Question 644 : http://www.les-mathematiques.net/phorum/read.php?16,1199715,1200047#msg-1200047

christophe c

Question 645 (axiome du choix accepté): existe-t-il un ensemble $T$ inclus dans l'ensemble des applications associatives de $\R^2\to \R$ telles que deux éléments différents quelconques de $T$ soient non isomorphes et avec $card(T)>card(\R)$

christophe c

Question 646 (que j'ai surement déjà posée).

L'étude de processus probabilistes (je ne précise pas ce que c'est donc la question va être un peu vague), mène à des systèmes d'équations polynomiaux dont on cherche des solutions dans $[0;1]^n$.

Soit $n\in \N$. Soit $f$ polynomiale de $[0;1]^n\to [0;1]^n$ (autrement dit une fonction polynomiale de $\R^n$ dans lui même telle que l'image directe par $f$ de $[0,1]^n$ soit incluse dans $[0,1]^n$).

Existe-t-il un processus probabiliste (à l'image du lien mis) conduisant à s'interroger sur un uplet $p\in [0;1]^n$ de probabilités inconnues tel que l'hypothèse faite sur le processus implique que $p$ est solution de $[f(p) =p; inconnue\ p]$?

Remarque: si oui, Brouwer est une conséquence** naturelle du fait que "beaucoup" de parties de $\R$ sont Lebesgue-mesurable.

Remarque2: j'ai dans l'idée que la réponse est "oui", je crois que dans le passé, j'avais trouvé pour chaque $f$ un processus, mais me rappelle plus vraiment au moment où je poste.

** par Weirstrass

christophe c

Remarque (à propos de 646): en admettant Brouwer, pour toute $f: [0,1]^n\to [0;1]^n$ (pas forcément continue!!!), on peut obtenir un processus probabiliste (si je me rappelle bien) ayant la propriété suivante:

L'évènement indice i "je gagne" est "égal" à l'évènement "je joue 1000000 de fois + 1 fois (de manière indépendante), et je gagne au dernier coup quand un réel tiré au sort de manière uniforme dans $[0,1]$ est $\leq$ à $f(frequence)(i)$, où $frequence(k):=$ nombre de gains indice k (dans le million) divisé par $1000000$

Tout ça pour dire qu'il n'est pas réglo d'utiliser Brouwer pour répondre à la 646

christophe c

Exercice 647 : soit $T$ un ensemble et $E$ l'ensemble des couples $(F,A)$ de parties de $[0;1]$ telles que $F$ est fermé. On note $\sigma(T)$ l'ensemble des fermés $G$ de $[0;1]$ tel que $\forall (F,A)\in T\cap E: G\subset A$ et $G\cap F\neq \emptyset$.

Construire, sans utiliser l'axiome du choix (choix dépendant autorisé), un $T$ tel que $\sigma(T)=\emptyset$ et pour toute partie dénombrable $D$ de $T$, $\sigma(D)\neq \emptyset$


Question 648: l'axiome suivant est-il consistant avec ZF (aucun axiome du choix, même faible n'est supposé)?

énoncé: pour tout ensemble $E$ et tut filtre $F$ sur $E$, si $F$ est stable par intersections dénombrables alors il existe un ultrafiltre $U$ stable par intersections dénombrables tel que $F\subset U$

christophe c

Exercice 649: je le trouve sympathique et l'idée c'est d'en donner une solution rapide (celle à laquelle je pense est un peu longue).

Soit $A$ un anneau commutatif unitaire et $E$ un ensemble. On suppose que $\sigma$ est une application de $E^2$ dans l'ensemble $B$ des idéaux de $A$.

Pour deux idéaux $U,V$ de $A$, tout $J$ et toute famille d'idéaux $W$ indicée par $J$, on note $U\to V := \{x\in A\mid \forall y\in U: xy\in V\}$ et $[\forall x\in J: W_x]$ l'intersection des idéaux $W_x$ quand $x$ parcourt $J$.

modifié après remarque de Zephir, merci Zephir

On suppose que $[\forall x\in E: \sigma(x,a)\to \sigma(x,b)]\times [\forall x\ni E: \sigma(x,b)\to \sigma(x,a)] \subset [\forall x\in E: \sigma(a,x)\to \sigma(b,x) ]$ pour tous éléments $a,b$ de $E$

On note $<a=b>$ l'idéal $[\forall x\in E: \sigma(a,x)\to \sigma(b,x)]$.

Soit $f$ une application de $E$ dans $B$. On dira qu'elle est interne quand $\forall a,b$ dans $E: <a=b> \subset (f(a)\to f(b)) \cap (f(b)\to f(a))$

On suppose la chose suivante: pour toute application $f$ interne de $E$ dans $B$, il existe $a\in E$ tel que pour tout $x\in E: \sigma(x,a) = f(x)$.

Exercice: prouver que l'anneau est trival (ie que $0_A=1_A$)

zephir

Bonsoir Christophe,
La notation $U_x$ n'étant pas définie, ton énoncé n'a plus de sens à partir de la 3eme ligne.

christophe c

Question 650: connaissez-vous un ensemble de matrices à coefficients dans $F_2$ (ie $\{0;1\}$) qui soit NP-complet et invariant par semblabilité** dans $F_2$?

** deux matrices sont semblables $M,N$ quand il existe une matrice bijective $P$ telle que $PN=MP$ (et l'invariance signifie si si deux matrices sont semblables, alors elles sont toutes deux dans l'ensemble ou hors de l'ensemble)

Foys

christophe c a écrit:

semblabilité**

On dit "similitude". Que veut dire "ensemble NP-complet?"

christophe c

Je n'osais pas utliiser le terme "similitude" à cause du fait que parfois en géométrie ça désigne autre chose (une composée d'une isométrie avec une homothétie).
Concernant le terme NP-complet:

Soit $A$ un ensemble fini que l'on va considérer comme un alphabet. Notons $A^*$ l'ensemble des mots (c'est à dire des suites finies) dont les lettres sont dans $A$. Je note $|m|$ la longueur du mot (son nombre de lettres)

Une partie $E$ de $A^*$ est dite P (pour polynomiale) quand il existe un entier $k$, un nombre $C$ et un programme d'ordinateur qui a la propriété suivante:

pour tout $m\in A^*$, quand on lui donne $m$ en entrée, il tourne, il tourne, mais au bout de moins de $C.|m|^k$ opérations, il s'arrête et donne la bonne réponse à la question $<<m$ est-il dans $E>>$

Soit (pour simplifier), $B$ un autre ensemble de lettres, disjoints de $A$ de même taille que $A$. On peut appliquer la définition ci-dessus à $(A\cup ^*$. Une partie $E$ de $A^*$ est dite NP quand il existe une partie $F$ de $(A\cup ^*$ qui est P avec la propriété que pour tout $m\in A^*$:
$$ m\in E \iff \exists n\in B^* : mn\in F\ et\ |n|\leq |m|$$

où $mn$ est la concaténé de $m$ et $n$.

$E,F$ deux parties de $A^*$. On dit que $E\leq F$ quand il existe une application de $A^*\to A^*$, qui se calcule en temps polynomial (définition, tu me la demandes si tu veux) et telle que $E=f^{-1}(F)$

Un théorème très célèbre (bien que facile, c'est un des rares théorèmes à la fois faciles et célèbres) dit qu'il existe $E\in NP$ tel que pour tout $F\in NP: F\leq E$. Un tel $E$ est dit NP-complet.
Quand pour tout $F\in NP: F\leq E$, seulement on dit que $E$ est NP-dur.

L'archétype de l'exemple d'ensemble NP-complet est le complémentaire de l'ensemble des tautologies. On l'appelle SAT. Il se ramène facilement à l'ensemble suivant qui est appelé $3SAT$ (bon je le modifie un peu pour faciliter les choses, ce n'est pas le 3SAT officiel mais bref): soit $U,V$ deux parties finies de $X^*$. Le couple $(U,V)$ est dit convenable quand il existe deux ensembles disjoints $S,T$ inclus dans l'alphabet $X$ tels que tout mot de $U$ a une lettre au moins dans $S$ et tout mot de $V$ a une lettre au moins dans $T$.
L'ensemble des couples convenables est NP-complet (on les code en ajoutant une petite syntaxe pour les représenter comme un mot sur un bon alphabet)

Comme autre ensemble célèbre de problèmes NP-complet (enfin d'ensemble NP-complet), c'est celui de la coloration des graphes avec 3 couleurs. L'ensemble des graphes 3-coloriables est NP-complet (c'est facile à voir en y réduisant SAT par des calculs dans $F_3$).

Autre exemple: l'ensemble des systèmes d'équations écrits avec des carrés et des $+$ qui ont une solution dans $F_3$ est NP-complet. On ne peut pas retirer l'usage des carrés sinon ça devient évidemment P (résolution par substitution)

Autre exemple: le complémentaire de l'ensemble des produits de sommes de produits de lettres qui sont égaux à $0$ avec les règles de calculs de l'anneau $F_2$.

Autre exemple: l'ensemble des matrices à coefficients dans $2$ telles qu'il est possible de barrer certaines lignes de manière à obtenir qu'il ne reste qu'un seul $1$ non barré par colonne

Je t'ai donné des exemples de mon cru que j'aime bien. Si tu vas sur wikipedia, tu en trouveras plein d'autres.

Foys

Ah merci (la littérature de vulgarisation abonde de présentations vagues mais pas de définitions formelles de plus le mot "problème NP complet" -et non "ensemble NP-complet"- est employé, je pensais donc avoir affaire à autre chose. )

christophe c

Je confirme effectivement que la littérature vulgarisée est complètement pourrie sur ce thème. Et la littérature non vulgarisée est particulièrement ubuesque et engoncée: on n'est pas gâté.

christophe c

Question 651: l'ensemble des théorèmes linéaires*** ne comportant qu'une variable propositionnelle et écrits seulement avec $\to$ est-il un ensemble polynomial?

*** informellement, un théorème linéaire est une expression écrite avec des flèches et des lettres, telle que si on l'interprète comme un espace vectoriel, on peut construire dedans un vecteur canonique non nul.

Exemple: $((a\to a)\to b)\to b$. Il y a un vecteur non nul canonique dans $L( L( L(A,A),B) , $ qui est $x\mapsto x(Id_A)$.

Il est connu que l'ensemble des théorèmes linéaires (écrits seulement avec $\to$) est NP-complet. Par contre l'ensemble des théorèmes linéaires maximaux est P. Maximal veut dire qu'on ne peut pas colorier les occurrences de ses variables (ie colorier les lettres, mais une même lettre à différentes places peut être coloriée de couleurs différentes) et continuer d'avoir un théorème (sachant qu'un $a$ bleu, un $a$ jaune, etc deviennent différents), sauf si une même lettre a été coloriée d'une seule couleur (autrement dit, on n'a rien changé).

christophe c

Question 652: on note $T$ l'ensemble des suites presque constantes à termes entiers (constantes à partir d'un certain rang). Existe-t-il une partie récursivement énumérable $A$ de $T$ dont le complémentaire ne l'est pas avec, pour toutes valeurs des variables $u,f$:

si $f$ est une application de $\N\to \N$ et $u\in A$ alors $f\circ u\in A$

christophe c

[size=x-large]Question 653[/size]