T.7 · Set images, equivalence relations and logical negation

Préparation GRE niveau universitaire. Objectifs locaux dans le périmètre ETS examiné ; il s'agit d'un enseignement original, pas d'un test officiel ni d'un prédicteur de score.

Prérequis : Opérations sur les ensembles, quantificateurs, fonctions et preuve élémentaire.

• Démontrer des identités d'images et distinguer l'inclusion de l'égalité
• Vérifier la réflexivité, la symétrie et la transitivité avec des cas explicites
• Négater des implications et des énoncés quantifiés sans en modifier la portée

préimage : L'ensemble des entrées dont les sorties se trouvent dans un ensemble cible spécifié.

relation d'équivalence : Une relation qui est réflexive, symétrique et transitive.

Pour f:X→Y et A⊆X, l'image f(A) consiste en toutes les sorties f(a) avec a dans A. Un point est dans f(A∪B) exactement s'il provient de A ou B, donc f(A∪B)=f(A)∪f(B). Si A⊆B, alors f(A)⊆f(B). Pour une intersection seule, f(A∩B)⊆f(A)∩f(B) est automatique : la même sortie peut provenir de différentes entrées. Utilisez f(x)=x², A={−1}, B={1} ; l'image de gauche est vide tandis que l'intersection de droite est {1}.

Les préimages se comportent différemment. Pour C⊆Y, f⁻¹(C) désigne ici l'ensemble de toutes les entrées envoyées dans C, même si f n'a pas de fonction inverse. L'appartenance à deux préimages signifie que la même entrée mappe vers les deux ensembles cibles. Par conséquent, les préimages préservent les unions, les intersections et les compléments par rapport au domaine/codomaine indiqué. Ne transférez pas un théorème sur les préimages aux images. Si f est injective, les intersections d'images deviennent alors égales, car des sorties égales imposent alors une entrée commune.

Une relation R sur X est réflexive quand xRx pour tout x, symétrique quand xRy implique yRx, et transitive quand xRy et yRz impliquent xRz. Les trois constituent une relation d'équivalence ; ses classes partitionnent X. Sur les entiers, xRy quand x et y ont le même reste modulo quatre donne quatre classes. La relation |x−y|≤1 est réflexive et symétrique mais pas transitive : 0R1 et 1R2 tandis que 0 n'est pas relié à 2. Vérifier uniquement un diagramme ou deux propriétés est insuffisant.

Une implication P⇒Q est fausse exactement quand P est vraie et Q fausse. Ainsi la négation de P⇒(Q∧R) est P∧(¬Q∨¬R), et non ¬P⇒(¬Q∧¬R). Négater « tout x possède la propriété A » donne « il existe x sans A » ; négater « il existe x » donne « tout x ne ». Un contre-exemple peut réfuter une affirmation universelle, tandis que des exemples ne peuvent pas la prouver. Les quantificateurs conservent leur ordre lors de la négation individuelle : ¬(∀x∃y S(x,y)) est ∃x∀y ¬S(x,y).

Laissez f mapper a et b vers le libellé L. Avec A={a}, B={b}, f(A∩B)=∅ mais f(A)∩f(B)={L}. Pour xRy défini par x=y ou x=−y sur ℝ, la réflexivité et la symétrie suivent directement, et deux changements de signe donnent encore z=±x, prouvant la transitivité. Les classes sont {x,−x}, avec {0} un singleton. Une fausse affirmation « chaque fichier stocké a un hash » signifie qu'au moins un fichier stocké n'a pas de hash ; cela ne signifie pas que tous les fichiers manquent de hashes.

f⁻¹(C) peut signifier un ensemble image réciproque sans fonction inverse. Une relation réflexive et symétrique peut encore échouer à être transitive. Néguez l'énoncé entier avant de simplifier ses parties.

Démontrez $f(A\cap B)\subseteq f(A)\cap f(B)$. Donnez un exemple d'inclusion stricte. Sous quelle hypothèse supplémentaire sur f l'égalité suit-elle pour tout A et B ?

Solution détaillée

Si $y=f(x)$ pour $x\in A\cap B$, alors x appartient à chaque ensemble, donc y appartient à chaque image. Pour la stricteté, mappez des a,b distincts vers le même c et prenez $A=\{a\}$, $B=\{b\}$. L'image de gauche est vide et l'intersection de droite est $\{c\}$. Si f est injective et $y=f(a)=f(b)$ avec $a\in A,b\in B$, l'injectivité donne a=b dans l'intersection, prouvant l'inclusion réciproque. Inversement, l'exemple du singleton montre que l'égalité pour toute paire impose l'injectivité.

Sur les entiers, définissez $aRb$ lorsque $a-b$ est divisible par 4. Montrez que c'est une relation d'équivalence et décrivez chaque classe. Négation : « Pour tout entier n, il existe un entier m supérieur à n ayant la propriété P. »

Vérification après tentative

La réflexivité utilise $a-a=0$ ; la symétrie utilise l'opposé d'un multiple de quatre ; la transitivité utilise la somme de deux tels multiples. Les classes sont les quatre résidus modulo quatre ; la classe de a est $a+4\mathbb Z$. La négation est : il existe un entier n tel que tout entier m supérieur à n ne satisfait pas P. Équivalentement $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$. Cela n'affirme pas que P échoue pour tout entier, ni que m est au plus n pour tout m.