parties et applications caractéristiques

fcb_54
fcb_54
dans Fondements et Logique
Bonjour,

Après la définition de la fonction caractéristique d'une partie E, l'auteur a énoncé le théorème suivant:

Théorème: L'applixation A----> Xa de P(E) dans F(E;{0;1}) (ensemble des applications) est bijective.

Mon problème commence à partir de la partie qui suit:

Ce théorème permet de donner une interprétation intéressante du théorème de Cantor (il n'existe aucune application surjective d'un ensemble E sur P(E) ). Puisque l'on a une bijection de F(E;{0;1}) sur P(E), le théorème de Cantor équivaut à la non existence d'une surjection de E sur F(E;{0;1}). On peut démontrer la non existence à l'aide du procédé diagonal de Cantor.
Soit phi une application quelconque de E dans F(E;{0;1}). Ainsi, pour tout a appartenant à E, phi(a) est une application de E dans {0;1}. On peut alors définir une application f de E dans {0;1} comme suit :

Quel que soit a appartenant à E, f(a):= 1 si phi(a)(a)=0
0 si phi(a)(a)=1

Par construction, f(a) est différent de phi(a)(a). A fortiori f est différent de phi(a). Cela étant vrai quel que soit a appartenant à E, f n'est pas dans l'image de phi qui n'est donc pas surjective.

Pourriez-vous m'expliquer cette partie d'une manière assez simple? (Sachant que j'ai vu le théorème de Cantor concernant la surjection et compris sa démonstration)

D'ailleurs, je n'ai jamais vu cette écriture phi(a)(a) et je n'ai pas la moindre idée de ce qu'elle peut signifier

Merci d'avance.

Réponses

  • 1528
    1528
    Si tu ne comprends pas les notations il n'est pas surprenant que tu ne comprennes pas la preuve ! Il s'agit du procédé diagonal de Cantor, tu devrais pouvoir en trouver facilement sur le net des descriptions à ton goût.

    Ici $\phi$ est une application de $E$ dans ${\cal F}(E,\{0,1\})$. Ainsi, pour tout $a \in E$, $\phi(a)$ est une application de $E$ dans $\{0,1\}$ et $\phi(a)(a)$ est la valeur de cette application en $a$. C'est donc une notation tout à fait classique.
  • fcb_54
    fcb_54
    Je te remercie tout d'abord d'avoir pris le temps de me répondre

    J'ai cherché sur plusieurs site (dont wiki) et j'ai trouvé des démos concernant le procédé diagonal de Cantor. Le problème c'est qu'ils parlaient tous de comment on peut prouver la non dénombrabilité de l'ensemble R, donc je n'arrivais pas à faire le lien avec la surjection. Mais je vais quand même continuer mes recherches.
    Ensuite, je ne comprends pas le dernier paragraphe, je t'explique comment je vois les choses. Selon ce que je comprends, phi est bien une application, mais sa valeur pour tout a appartenant à E, doit être égale à phi(a) et non à phi(a)(a).
  • fcb_54
    fcb_54
    Enfin c'est bon j'ai relu ce que vous m'aviez écrit plusieurs fois je pense avoir bien compris la notation phi(a)(a)
  • 1528
    1528
    $\phi(a)$ est bien la valeur de l'application $\phi$ en $a$. Cela n'empêche pas $\phi(a)$ d'être une application de $E$ dans $\{0,1\}$ et donc, en particulier, d'avoir une valeur en $a$. Valeur que l'on note (comme d'habitude) "nom de la fonction"$(a)$ c'est-à-dire ici $\phi(a)(a)$.
  • fcb_54
    fcb_54
    Merci beaucoup pour l'explication c'est plus clair maintenant.

    Et concernant le procédé diagonal de Cantor, personne n'a une explication de comment on peut l'appliquer à des ensemble afin de prouver la non surjectivité?
  • 1528
    1528
    La non surjectivité de quoi ? Ici il est utilisé pour montrer la non surjectivité de toute application (appelée ici $\phi$) de $E$ dans ${\cal P}(E)$.
  • fcb_54
    fcb_54
    "Par construction, f(a) est différent de phi(a)(a). A fortiori f est différent de phi(a). Cela étant vrai quel que soit a appartenant à E, f n'est pas dans l'image de phi qui n'est donc pas surjective. "

    Voilà j'ai du mal à comprendre cette partie, le raisonnement à suivre pour comprendre que phi n'est pas surjective.
    J'ai également du mal à comprendre "f n'est pas dans l'image de phi"
  • GaBuZoMeu
    GaBuZoMeu
    Il suffit de lire calmement et attentivement. Allons-y par étapes.

    1) On a posé $f(a)=0$ si $\phi(a)(a)=1$ et $f(a)=1$ si $\phi(a)(a)=0$. Donc "par construction, $f(a)$ est différent de $\phi(a)(a)$". D'accord ?

    2) $f$ et $\phi(a)$ sont deux applications de $E$ dans $\{0;1\}$. Elles seraient égales seulement si on avait $f(b)=\phi(a)(b)$ pour tout $b\in E$. Or on a $f(a)\neq \phi(a)(a)$. Donc "$f$ est différent de $\phi(a)$". D'accord ?

    3) Le raisonnement qu'on a fait vaut pour tout $a\in E$. On a donc montré que pour tout $a\in E$, $f$ est différent de $\phi(a)$. Or, par définition de l'image, $f$ appartient à l'image de $\phi$ seulement s'il existe $a\in E$ tel que $f=\phi(a)$. Donc "$f$ n'est pas dans l'image de $\phi$". D'accord ?

    4) $\phi$ est surjective seulement si toute application de $E$ dans $\{0;1\}$ est dans l'image de $\phi$. Or on a construit une application $f :E\to \{0,1\}$ qui n'est pas dans l"image de $\phi$ ; $\phi$ "n'est donc pas surjective". D'accord ?
  • fcb_54
    fcb_54
    Merci énornmément GaBuZoMeu, je comprends beaucoup mieux maintenant
    Merci également à tous les membres qui ont essayé de m'aider
  • christophe c
    christophe c
    @fcb. Je te donne une version qui a moins l'air "anguleuse" qu'un "raisonnement guidé" et qui dit un truc plus général.

    Soient $E,F$ des ensembles, $G$ l'ensemble des applications de $E$ dans $F$ et $L$ une surjection de $E$ sur $G$. Alors $card(F)\leq 1$.

    Afin d'être doux et velouté à tes oreilles, je ne vais pas prouver $card(F) \leq 1$, mais seulement que toute application de $F$ dans $F$ a un point fixe et je te laisserai en déduire toi-même que $card(F) \leq 1$

    Soit donc $f$ une application de $F$ dans $F$. Soit $g:x\mapsto f(L(x)(x))$, application de $E$ dans $F$. Soit $e$ tel que $L(e) = g$. Alors :
    $$L(e)(e) = g(L(e)(e))$$
    et donc, en abrégeant $p:=L(e)(e)$, on obtient $p=g(p)$.

    Le fil ci-dessus a mis en scène ça avec $x\mapsto 1-x$, et Cantor le met en scène avec $x\mapsto non(x)$.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • fcb_54
    fcb_54
    Merci pour ton post :)
    Par contre j'ai du mal à comprendre comment tu as fais pour arriver à : L(e)(e)=g(L(e)(e))
    et la première partie de la dernière phrase: Le fil ci-dessus a mis en scène ça avec x ---->1-x
  • christophe c
    christophe c
    Par contre j'ai du mal à comprendre comment tu as fais pour arriver à : L(e)(e)=g(L(e)(e))

    Je ne comprends pas ta question. qu'appelles-tu "mettre en place" et "arriver à "?

    Par "le fil ci-dessus", je parle parle du topic, ie des posts précédents et je te dis qu'ils ont fait ce que je te décris en prenant f:= (x|
    > 1-x), etc

    Édit: j'avais tapé g à la place de f pardon et merci pour le signalement.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • mpif
    mpif
    Je suppose qu'il demande comment démontrer que $L(e)(e)=g(L(e)(e))$.

    Vu que $L(e)=g$ et pour tout $x$ on a $g(x)=f(L(x)(x))$, on peut facilement démontrer $L(e)(e)=g(e)=f(L(e)(e))$ ce qui donne un point fixe de $f$.

    L'égalité avec $g$ est à priori impossible à démontrer en général (surtout que $L(e)(e)$ n'appartient même pas à $E$ mais à $F$). De toute façon on voulait un point fixe de $f$, pas de $g$.
  • fcb_54
    fcb_54
    Oui c'est ce que je voulais savoir mpif merci beaucoup

    Merci également christophe c
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 6

AmadouFoys +4 Invités