Images d'ensembles, relations d'équivalence et négation logique
Introduit| English | Sens |
|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | image réciproque |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | relation d'équivalence |
| negation/nɪˈɡeɪʃn/ | négation |
Deux enregistrements, une étiquette
- Une fonction de hachage envoie des fichiers distincts $a$ et $b$ à la même étiquette $L$. Avec $A=\{a\}$ et $B=\{b\}$, l'image de $A\cap B$ est vide, mais $f(A)\cap f(B)=\{L\}$.
- La même étiquette ne signifie pas nécessairement la même entrée. Cette distinction relie les images réciproques, les relations d'équivalence et la négation logique.
Énoncer les deux univers
- Fixer $f:X\to Y$. Pour $A\subseteq X$, son image est $f(A)=\{f(x):x\in A\}$. Pour $C\subseteq Y$, son image réciproque est $f^{-1}(C)=\{x\in X:f(x)\in C\}$.
- Le symbole $f^{-1}(C)$ décrit un ensemble d'entrées, même lorsque $f$ n'a pas de fonction réciproque. Les compléments doivent nommer leur univers : $X\setminus A$ et $Y\setminus C$ vivent dans des ensembles différents.
Pourquoi les images préservent les unions
- Si $y\in f(A\cup B)$, une entrée $x\in A\cup B$ se mappe vers $y$. Cette entrée appartient à $A$ ou $B$, donc $y\in f(A)\cup f(B)$.
- Réciproquement, l'appartenance à l'une ou l'autre image donne une entrée dans $A\cup B$. Les deux inclusions prouvent $f(A\cup B)=f(A)\cup f(B)$, sans aucune hypothèse d'injectivité.
Intersections : une entrée ou deux ?
- Si $y\in f(A\cap B)$, une entrée appartient aux deux ensembles et se mappe vers $y$. Ainsi $f(A\cap B)\subseteq f(A)\cap f(B)$. Dans le sens inverse, les deux entrées peuvent différer : élever au carré envoie aussi bien $-1$ que $1$ vers $1$.
- Si $f$ est injective, des sorties égales forcent ces entrées à coïncider, donnant l'égalité. L'égalité pour chaque paire $A,B$ force aussi l'injectivité : une collision donne des singletons disjoints avec des images qui se chevauchent. L'égalité pour une seule paire, comme $A=B$, ne prouve rien sur l'injectivité.
For every function $f$ and sets $A, B$ in its domain, which always holds?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Union equality holds for every map. The other equalities/inclusion become valid for every pair under injectivity, but can fail for a map with a collision. A particular pair can still give equality without injectivity.
Let $a,b$ be distinct and $f(a)=f(b)=L$. For $A=\{a\}$ et $B=\{b\}$, what are $f(A\cap B)$ et $f(A)\cap f(B)$?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The input intersection is empty, but both image sets contain L.
Différences et compléments peuvent échouer
- Toujours $f(A)\setminus f(B)\subseteq f(A\setminus B)$ : une sortie absente de $f(B)$ n'a pas d'antécédent dans $B$. L'inverse peut échouer. Si $f(a)=f(b)=L$, alors $A=\{a\}$ et $B=\{b\}$ donnent $\{L\}$ à droite mais l'ensemble vide à gauche.
- Soient $X=\{a,b,c\}$, $Y=\{L,M,N\}$, avec $a,b\mapsto L$ et $c\mapsto M$. Pour $A=\{a\}$, l'image de $X\setminus A$ est $\{L,M\}$, tandis que $Y\setminus f(A)=\{M,N\}$. Préserver les compléments relatifs à tout $Y$, pour chaque $A$, exige une bijection.
Prove that images preserve unions and give intersection inclusion. Then use a collision to disprove image-difference equality.
Comparez les quantificateurs, les univers d'ensembles et les témoins explicites dans votre raisonnement.
Images réciproques préservent les opérations ensemblistes
- Pour $C,D\subseteq Y$, une entrée se mappe dans $C\cup D$ exactement lorsqu'elle se mappe dans au moins un ensemble. Elle se mappe dans $C\cap D$ exactement lorsqu'elle se mappe dans les deux. Ainsi, les images réciproques préservent les unions et les intersections.
- De plus $f^{-1}(Y\setminus C)=X\setminus f^{-1}(C)$ : les deux côtés contiennent exactement les entrées dont les sorties sont hors de $C$. Aucune de ces identités n'exige d'injectivité ni de surjectivité.
$f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ for every function $f$.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
An input maps into C ∩ D exactly when it maps into both C and D; injectivity is unnecessary.
Sortie et retour
- L'identité $f(f^{-1}(C))=C\cap f(X)$ ne conserve que les sorties atteignables. Dans la carte finie ci-dessus, $C=\{L,N\}$ a pour image réciproque $\{a,b\}$ et pour image de l'image réciproque $\{L\}$ : la sortie manquante $N$ ne peut apparaître.
- Toujours $A\subseteq f^{-1}(f(A))$. Ce trajet aller-retour ajoute chaque entrée partageant une sortie avec $A$. Pour $A=\{a\}$, cela donne $\{a,b\}$. L'égalité pour tout $A$ vaut exactement lorsque $f$ est injective.
Valable pour toute application ?
Distinguer les identités universelles des affirmations nécessitant des hypothèses supplémentaires.
Pour $f(x)=x^2$ on $\mathbb R$ et $A=\{-2\}$, how many elements belong to $f^{-1}(f(A))$?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
f(A)={4}, whose preimage is {-2,2}. The round trip can add inputs.
Let $X=\{a,b,c\}$, $Y=\{L,M,N\}$, $f(a)=f(b)=L$, $f(c)=M$, and $C=\{L,N\}$. Find $f(f^{-1}(C))$.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Only L is in both C and the image {L,M}. No input maps to N.
Use $a,b\mapsto L$, $c\mapsto M$ from $X=\{a,b,c\}$ à $Y=\{L,M,N\}$. For $A=\{a\}$ et $C=\{L,N\}$, find $f^{-1}(f(A))$, $f(f^{-1}(C))$, and $f^{-1}(Y\setminus C)$. Explain each change.
Comparez les quantificateurs, les univers d'ensembles et les témoins explicites dans votre raisonnement.
Trois propriétés des relations
- Une relation sur un ensemble $S$ est réflexive si $x\sim x$ pour tout $x\in S$, et symétrique si $x\sim y$ implique $y\sim x$ pour toute paire. Un unique élément ou une paire défaillante infirme la propriété correspondante.
- La transitivité exige que $x\sim y$ et $y\sim z$ impliquent $x\sim z$ pour tout triplet. Une relation d'équivalence possède les trois propriétés. Il faut toujours préciser $S$ : changer les éléments autorisés peut changer la réponse.
Pourquoi les classes d'équivalence partitionnent un ensemble
- Définir $[x]=\{y\in S:y\sim x\}$. La réflexivité place $x$ dans $[x]$, de sorte que les classes couvrent $S$. Chaque classe est non vide.
- Si $z\in[x]\cap[y]$, la symétrie et la transitivité donnent $x\sim y$. Tout $w\sim x$ satisfait aussi $w\sim y$, donc $[x]\subseteq[y]$ ; inverser les rôles donne l'égalité. Les classes distinctes sont donc disjointes : elles forment une partition.
Les restes donnent des classes complètes
- Sur $\mathbb Z$, posons $x\sim y$ signifiant que $4$ divise $x-y$. La réflexivité découle de $x-x=0$ ; la symétrie du changement de signe ; la transitivité en additionnant deux différences divisibles par $4$.
- Les quatre classes sont $[0],[1],[2],[3]$, avec $[r]=\{r+4k:k\in\mathbb Z\}$. Les entiers négatifs y appartiennent aussi : $-1\in[3]$. Remplacer $4$ par $6$ donne exactement six classes, car tout entier a un reste allant de $0$ à $5$.
How many equivalence classes does “same remainder mod 6” have on $\mathbb Z$?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Two integers are related when they leave the same remainder on division by 6. The possible remainders 0, 1, …, 5 give exactly 6 classes.
Carrés égaux, même classe
- Sur $\mathbb R$, $x\sim y$ lorsque $x=\pm y$, équivalent à $x^2=y^2$. L'égalité de ces valeurs est réflexive, symétrique et transitive, c'est donc une relation d'équivalence.
- Pour $x\ne0$, la classe est $\{x,-x\}$ ; la classe de zéro est simplement $\{0\}$. Plus généralement, toute fonction regroupe les entrées en classes d'équivalence par valeur de sortie égale, qu'elle soit injective ou non.
Trouver la propriété qui échoue
- Sur $\mathbb R$, $|x-y|\le1$ échoue à la transitivité avec $0,1,2$. Sur $\mathbb Z$, la différence impaire échoue à la réflexivité car $x-x=0$ ; elle échoue aussi à la transitivité avec $1,2,3$. Les deux relations sont symétriques.
- La relation $x\le y$ sur $\mathbb R$ échoue à la symétrie avec $0,1$. La relation $xy>0$ sur $\mathbb R\setminus\{0\}$ est une équivalence par signe, mais sur l'ensemble de $\mathbb R$, elle échoue à la réflexivité en zéro. L'univers fait partie de la question.
Relation d'équivalence ?
Vérifier la réflexivité, la symétrie et la transitivité simultanément.
On $\mathbb Z$, the relation “$x - y$ is odd” is
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
It fails reflexivity because x − x = 0 is even. It is symmetric (x − y odd ⇒ y − x odd) but not transitive: 1 − 2 and 2 − 3 are odd, yet 1 − 3 is even.
The relation $xy>0$ is an equivalence relation on all of $\mathbb R$.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
At x=0, x² is not positive, so reflexivity fails. Removing zero gives an equivalence relation with two sign classes.
Prove that $6\mid(x-y)$ defines an equivalence relation on $\mathbb Z$ and describe its classes. Explain why replacing “divisible by 6” by “odd” fails.
Comparez les quantificateurs, les univers d'ensembles et les témoins explicites dans votre raisonnement.
Implication et contraposée
- $P\Rightarrow Q$ est faux exactement quand $P$ est vrai et $Q$ est faux. Si $P$ est faux, l'implication est vraie. Par exemple, « si $3$ est divisible par $4$, alors $3$ est pair » a un antécédent faux et est une implication vraie.
- La contraposée $\neg Q\Rightarrow\neg P$ a la même valeur de vérité que $P\Rightarrow Q$. La réciproque $Q\Rightarrow P$ ne doit pas nécessairement : la divisibilité par $4$ implique la parité pour les entiers, mais le nombre pair $2$ n'est pas divisible par $4$.
$P \Rightarrow Q$ is false only when $P$ is true and $Q$ is ____.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Truth table of implication.
Nier l'énoncé entier
- Nier une implication donne $\neg(P\Rightarrow Q)\equiv P\wedge\neg Q$. Les lois de De Morgan échangent « et » contre « ou » : par exemple, $\neg(Q\wedge R)\equiv\neg Q\vee\neg R$.
- En combinant les règles, la négation de $P\Rightarrow(Q\wedge R)$ est $P\wedge(\neg Q\vee\neg R)$. L'antécédent doit être vérifié, et au moins une conclusion promise doit être fausse. Le « ou » inclut la possibilité que les deux conclusions soient fausses.
L'ordre des quantificateurs contrôle l'affirmation
- Sur $\mathbb R$, « pour tout $x$ il existe $y>x$ » est vrai : choisir $y=x+1$. « Il existe $y$ supérieur à tout $x$ » est faux : poser $x=y$. Déplacer un quantificateur existentiel plus tôt empêche son choix de dépendre des variables ultérieures.
- Nier un quantificateur à la fois, en conservant l'ordre et les domaines : $\neg(\forall x\,\exists y\,S)\equiv\exists x\,\forall y\,\neg S$. Ainsi, « chaque fichier stocké a un hash » est faux exactement quand certains fichiers stockés n'ont pas de hash ; cela ne signifie pas que tous les fichiers en manquent.
On $\mathbb R$, “for every $x$ there is $y>x$” is equivalent to “there is $y$ such that $y>x$ for every $x$.”
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The first holds using y=x+1. The second fails by taking x=y for any proposed y.
Nier la convergence vers zéro
- Pour une suite réelle, la convergence vers zéro signifie : pour tout $\varepsilon>0$, il existe un entier non négatif $N$ tel que tout entier positif $n>N$ satisfait $|a_n|<\varepsilon$. Le seuil $N$ peut dépendre de $\varepsilon$.
- Sa négation est : il existe $\varepsilon>0$ tel que pour tout seuil $N$, certains entiers $n>N$ satisfont $|a_n|\ge\varepsilon$. Conserver la condition stricte $n>N$ ; nier uniquement la conclusion $|a_n|<\varepsilon$, y compris l'égalité dans son échec.
The negation of “for every $\varepsilon > 0$ there is $N$ with $|a_n| < \varepsilon$ for all $n > N$” is
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Flip ∀ε, ∃N, ∀n>N to ∃ε, ∀N, ∃n>N, in that order. Failure of a strict inequality includes equality. Alternating zeros and ones fails at ε=1/2 but has late zeros, and ε=2 never fails.
Tardivement arbitraire n'est pas finalement toujours
- Poser $a_n=1$ pour $n$ impair et $a_n=0$ pour $n$ pair. Choisir $\varepsilon=1/2$. Au-delà de toute borne, il y a un indice impair avec $|a_n|\ge\varepsilon$, donc la suite ne converge pas vers zéro.
- Pourtant, elle n'est pas bornée inférieurement par zéro à partir d'un certain rang : les indices pairs donnent des zéros à tout moment tardif. Ni toute tolérance positive n'échoue : $\varepsilon=2$ contient toute la suite. Une seule tolérance défaillante suffit ; ses mauvais indices n'ont pas besoin d'inclure tous les indices ultérieurs.
If a real sequence does not converge to zero, there must be a positive tolerance which every sufficiently late term exceeds or equals in absolute value.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Alternating 1 and 0 has arbitrarily late terms outside ε=1/2, but also arbitrarily late zeros. Some late term for every cutoff is weaker than all terms beyond one cutoff.
Let $a_n=1$ when $n$ is a power of $2$ et $a_n=0$ otherwise. Negate convergence to zero and verify the negation. Does the sequence eventually stay away from zero?
Comparez les quantificateurs, les univers d'ensembles et les témoins explicites dans votre raisonnement.
Résumé
- Une image réciproque est l'ensemble des entrées dont les sorties appartiennent à un ensemble spécifié. Les images réciproques préservent les unions, intersections et compléments dans leurs univers respectifs ; les images préservent toujours les unions, mais l'égalité des intersections pour chaque paire nécessite l'injectivité.
- Une relation d'équivalence est une relation réflexive, symétrique et transitive ; ses classes partitionnent l'ensemble sous-jacent. Une négation est l'énoncé vrai exactement lorsque l'original est faux. Nier les quantificateurs dans l'ordre, en conservant leurs domaines et toute dépendance entre les choix.