Transformer un couple en un couple d'ensembles disjoints

Congru
Modifié (29 Mar) dans Fondements et Logique
Bonjour
Je propose cet exercice.
1. (Sans l'axiome de fondation) Soit $(A,B)$ une paire un couple d'ensembles ; trouver un ensemble $C$ tel que $C$ soit en bijection avec $B$ et $\bigcap \{C;A\}=\emptyset$
2. (Axiome de fondation autorisé) Donner un prédicat fonctionnel binaire $f$ tel que, pour tous $A$ et $B$, $fAB$ soit en bijection avec $B$ et $\bigcap \{fAB;A\}=\emptyset$.
N.B.
Cet exercice à l'apparence innocent vient de la solution que j'ai trouvée pour la construction de Henkin.
@Martial et @Médiat_Suprème désolé pour mon dernier message dans mon dernier fil, j'ai parlé avant de réfléchir.
Family, mathematics, friends

Réponses

  • Pour la 2), j'imagine qu'un truc comme $B\times \{A\}$ doit marcher ?

    Pour la 1), si $A$ est assez grand, cela devrait être vrai que $B$ s'injecte dans $B\times (\mathcal{P}(A) \setminus A)$ ?
  • Bonjour @Georges Abitbol, merci pour ta réponse.
    Ta solution pour le "1." ne fonctionnera pas. Pour le "2.", peux-tu prouver que cela fonctionne ?
    Family, mathematics, friends
  • Edit. Dans la question initiale, j'ai dit "paire" au lieu de "couple". Comme je n'ai pas le droit de changer la question initiale après une réponse de quelqu'un, j'espère qu'un modérateur bien-veillant voudra bien faire le changement.
    Family, mathematics, friends
  • raoul.S
    Modifié (29 Mar)
    Pour la 1. $\bigcap \{C;A\}=\emptyset$ désigne l'intersection de $C$ avec $A$ ? Si oui voici une preuve que je ne formalise pas.
    On considère l'énoncé $E(x):=(\forall b, b\in B\Rightarrow (b,x)\not\in A)$. Il suffit de montrer qu'il existe un ensemble $x$ tel que $E(x)$. En effet si tel est le cas alors l'ensemble $C:=B\times \{x\}$ fait l'affaire.
    Supposons alors que pour tout ensemble $x$, on ait $\neg E(x)$. Il existe alors une "injection" de la classe de tous les ensembles dans $\mathcal{P}(A)\setminus \{\emptyset\}$ "définie" par $x\mapsto \{(b,x)\mid\; b\in B\wedge (b,x)\in A\}$ ce qui est absurde.
  • Congru
    Modifié (29 Mar)
    @raoul.S Merci, c'est évidemment une solution que tu as produite. Je connaissais trois façons de résoudre le problème, et ta solution est l'une d'elle.
    Family, mathematics, friends
  • Congru
    Modifié (29 Mar)
    Ce problème est en lien avec mon autre fil sur les témoins de Henkin et la preuve classique du théorème de complétude
    https://les-mathematiques.net/vanilla/discussion/2337240/probleme-dans-la-demonstrations-du-theoreme-de-completude#latest
    Family, mathematics, friends
  • Je connaissais trois façons de résoudre le problème,

    Quelles sont les deux autres ? Sans tomber dans le langage machine svp... :mrgreen:

  • Congru
    Modifié (29 Mar)
    @raoul.S désolé, il y a un tout petit peu de langage.
    Les deux autres solutions sont très proche de ce que tu proposes:
    a. On prend $v$ tel que  $v\notin \bigcup \bigcup A$ on considère $C:=B\times \{v\}$
    b. On prend $v$ tel que  $v\notin \bigcup \bigcup A$ on considère $C:= \{v\} \times B$
    Est-ce que tu vois comment faire pour le "2." ?
    Family, mathematics, friends
  • Pour la 2. je ne comprends pas la notation $fAB$.
  • Congru
    Modifié (29 Mar)
    $f$ est une "fonction" binaire au même titre que la "fonction" produit Cartésien $\times$. On utilise la notation préfix pour $f$:
    en notation préfixe, le produit le produit Cartésien de $U$ et $W$ (dans cet ordre) sera noté $\times UW$.
    N.B: la notation préfixe est plus naturelle que la notation infixe et évite la nécessité de paranthéses: voir $\times \times UWV$ et $\times U\times WV$.
    Edit. merci au modérateur qui a amélioré la rédaction de la question initiale.
    Family, mathematics, friends
  • Congru
    Modifié (29 Mar)
    Définition: $\forall x\forall y(\pi _2 (x;y)=y)$
    @raoul.S voilà comment j'avais rédigé ma troisième solution pour le "1." (la solution qui est exactement la même que la tienne):
    On a $(\forall x (\bigcap \{ B\times \{x\};A\} \not =\emptyset )) \implies \forall yy\in\{\pi_2 z\mid z\in A\}$.
    Family, mathematics, friends
  • Georges Abitbol
    Modifié (30 Mar)
    Euh, plutôt $\{A\}\times B$. En effet, si $\{\{A\}, \{A,b\}\} \in A$, alors $A\in \{A\} \in \{\{A\},\{A,b\}\} \in A$, ce qui est proscrit par l’axiome de fondation, non ?

    EDIT : et pour la 1), ok, le truc que j’ai proposé n’a aucune raison de marcher…
  • @Congru : peux-tu mettre un lien vers le dernier message auquel tu fais allusion ? Je ne vois pas du tout de quoi tu veux parler.
  • Congru
    Modifié (30 Mar)
    Dans mon fil d'il y a quelques semaines (la place du langage dans la démonstration) tu m'expliquais quelque chose sur la théorie de la démonstration, @Médiat_Suprème avait rajouté une nuance à ton explication, j'ai fait une interprétation erronée de cette nuance et j'avais tellement honte que je tenais  à m'excuser pour mon erreur mathématique :D. Au fait je n'avais pas compris la nuance qu'apportait @Médiat_Suprème et j'aurais juste dû demander des précisions.
    Family, mathematics, friends
  • Congru
    Modifié (30 Mar)
    En effet, si $\{\{A\}, \{A,b\}\} \in A$, alors $A\in \{A\} \in \{\{A\},\{A,b\}\} \in A$, ce qui est proscrit par l’axiome de fondation, non ?
    @Georges Abitbol super ta démonstration, en effet ta démonstration pour le "2." marche très bien, je ne la connaissais pas. Je te dis un grand merci.
    Family, mathematics, friends
  • @Congru : OK, ça me revient maintenant.
  • Foys
    Modifié (31 Mar)
    A mon tour;
    (i)Soit $T$ un ensemble; alors $\omega_T:= \{x\in T \mid x \notin x\}$ (obtenu à l'aide du schéma de compréhension) n'appartient pas à $T$ (sinon $\omega_T \notin T$ si et seulement si $\omega_T \in \omega_T$ ce qui entraîne une contradiction).
     (ii) pour tous $x,y,z$, si $\{x,y\} = \{x,z\}$ alors $y = z$ (exo!)
     (iii) Soient $A,B$ deux ensembles, $P:= \{p\in B \mid \exists q, \exists r, p = \{q,r\}\}$ et $\omega$ n'appartenant pas à $P$. Alors pour tout $x \in A$, $\{\omega, x\} \notin B$ et $x\mapsto \{\omega, x\}$ est injective (cf ii), donc son image est l'ensemble cherché.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Congru
    Modifié (1 Apr)
    Wow, @Foys super ton (i). je n'ai jamais vu le "raisonnement de la diagonales" utilisé comme cela. D'où te viens cette idée ?
    Tu viens de faire mon "1." et "2" sans utiliser l'axiome de fondation. Et je vais compte me servir de cet ensemble "diagonale".
    Foys a dit :
    A mon tour;
    (i) $\omega_T:= \{x\in T \mid x \notin x\}$
    C'est à cause de choses comme ça que j'adore la logique.

    Family, mathematics, friends
  • Congru
    Modifié (1 Apr)
    @Foys pour le (iii) ne faudrait-il pas prendre $\omega \notin \bigcup P$ ?
    Family, mathematics, friends
  • Congru
    Modifié (1 Apr)
    En attendant, voilà ce que je souhaite prendre, (inspiré de la solution diagonale proposée par Foys):
    Soit $f$ le prédicat fonctionnel binaire défini par la formule $(z=y\times \{ \{t\in \bigcup \bigcup x\vert t\not \in t\} \};(x;y;z))$.
    Pour tout $A$, pour tout $B$, $fAB$ est en bijection avec $B$ et $\bigcap \{fAB;A\} =\emptyset $
    Family, mathematics, friends
Connectez-vous ou Inscrivez-vous pour répondre.