Ensemble Flashcards
(Définition) Ensemble
On appelle ensemble toute collection non ambiguë d’objets distincts deux à deux, appelés éléments de l’ensemble. L’ensemble vide, noté ∅ , est l’ensemble ne contenant aucun élément.
(Définition) Appartenance
Le fait qu’un élément x appartienne à un ensemble E se note x ∈ E , et son contraire x ∉ E
définir un ensemble par extension, c’est …
définir un ensemble en listant tous ces éléments
définir un ensemble par intension, c’est …
définir les éléments de l’ensemble sont ceux satisfaisant un prédicat, typiquement de la forme { x I P ( x ) } qui est l’ensemble des x tels que P ( x ) est vrai.
(traduction) S:= { f(x) I R(x) }
S est l’ensemble des f(x) TELS QUE R(x).
(Définition) Inclusion d’un ensemble dans un autre
Si tout les éléments d’un ensemble appartiennent a un autre ensemble alors il est un sous-ensemble.
noté E ⊆ F :
∀x . ( x ∈ E ⇒ x ∈ F ) ou ∀x ∈ E . x ∈ F
(traduction) T ⊆ S
( ∀e I e ∈ T => e ∈ S )
(traduction) T ⊂ S
T ⊆ S ∧ (∃e ∈ S ∧ e ∉ T)
(traduction) T ⊈ S
¬(T ⊆ S)
(Définition) Égalité
E et F sont égaux , noté E = F , si E ⊆ F et F ⊆ E .
(Définition) Non-égalité
E et F ne sont pas égaux , noté E = F , si ¬ ( E = F ) . On dit
(Définition) Ensemble des parties d’un ensemble
L’ ensemble des parties de E , noté 𝒫( E ) ou 2ᴱ, est l’ensemble contenant tous les sous-ensembles de E , c’est-à-dire l’ensemble { X I X ⊆ E } .
(Définition) Complémentaire d’un ensemble
Le complémentaire de E par rapport à A, noté ∁ₐE ou E \ A est : {x I x ∈ E et x ∉ A}
ou encore lorsqu’il n’y a pas d’ambiguïté sur E, noté ᶜA, Aᶜ ou ¬A est E = { x I x ∉ E } .
(proprieté) 1ere Loi de De Morgan ( S ∩ T )ᶜ
Sᶜ ∪ Tᶜ
(proprieté) 2e Loi de De Morgan ( S ∪ T )ᶜ
Sᶜ ∩ Tᶜ
(Sᶜ)ᶜ =
S
S ∪ Sᶜ =
U
S ∩ Sᶜ =
Ø
S \ Ø =
S
S \ T =
S ∩ Tᶜ
Réécriture de l’inclusion S ⊆ T
S ⊂ T ∨ S = T
Réécriture de l’inclusion stricte S ⊂ T
S ⊆ T ∨ T ≠ S
(Définition) Union
L’ union de E et F , notée E ∪ F , est l’ensemble défini comme suit :
E ∪ F = { x I x ∈ E ∨ x ∈ F } .
(Définition) Intersection
L’ intersection de E et F , notée E ∩ F , est l’en- semble défini comme suit :
E ∩ F = { x I x ∈ E ∧ x ∈ F } .
(Propriété) opérateurs ensemblistes
Les opérateurs d’union et d’intersection sont associatifs , commutatifs et distributifs l’un par rapport à l’autre.
L’ensemble vide ∅ est élément neutre pour l’union et l’ élément absorbant pour l’intersection.
(Définition) Couple et produit cartésien
Étant donnés deux éléments x ∈ E et y ∈ F, le couple formé par x et y , noté ( x, y ) , est l’ensemble {{ x } , { x, y }} à deux éléments.
Le produit cartésien de E et F , noté E × F , est l’ensemble { ( x, y ) I x ∈ E ∧ y ∈ F } .
Produit cartésien
S x T = {(a;b) I a ∈ S ∧ b ∈ T}
C’est à dire toutes les paires possibles entre les éléments de S et de T.
Sⁿ
Produit cartésien de S, n fois
(Définition) Relation
Une relation R entre E et F est un sous-ensemble du produit carté- sien E × F : R ⊆ E × F . Pour une relation R entre E et F et deux éléments e ∈ E et f ∈ F , lorsque e et f sont en relation selon R, on note ( e, f ) ∈ R ou eRf .
Lorsque E = F , R ⊆ E × E est une relation sur E .
Relation
- Associe des éléments de 2 ensembles.
- Sous ensemble d’un produit cartésien de ces 2 ensembles.
a𝓡b signifie
(a,b) ∈ 𝓡
(Définition) une relation 𝓡 sur un ensemble E est réflexive si
si tout élément est relié à lui-même
∀x . x ∈ E ⇒ ( x, x ) ∈ 𝓡. ou
∀x . x ∈ E, x𝓡x;
Tous les x ont une boucle vers eux mêmes.
(Définition) une relation 𝓡 sur un ensemble E est antiréflexive si
si ∀x . x ∈ E ⇒ ( x, x ) ∉ 𝓡. ou encore
𝐈s ∩ 𝓡 = Ø
Aucun a admet une boucle vers lui même.
(Définition) une relation 𝓡 sur un ensemble E est symétrique si
si symétrique si x relié à y entraîne que y est relié à x
∀x,y . ( x, y ) ∈ 𝓡 ⇒ ( y, x ) ∈ 𝓡. ou
∀x,y ∈ E ,\; (x𝓡y) ⇒ (y𝓡x)
Pour chaque relations “aller” x vers y, il y a aussi un “retour” y vers x.
(Définition) une relation 𝓡 sur un ensemble E est anti-symétrique si
si x relié à y et y relié à x entraînent x=y
∀x,y . (( x, y ) ∈ R ∧ ( y, x ) ∈ R ⇒ x = y )
∀x . x ∈ E, ((x𝓡y)∧ (y𝓡x)) ⇒ (y𝓡x)
(Définition) une relation 𝓡 sur un ensemble E est transitive si
si quand x est relié à y et y à z alors x est relié à z
∀x, y, z . (( x, y ) ∈ R ∧ ( y, z ) ∈ R ⇒ ( x, z ) ∈ R )
∀x, y, z ∈ E, ((x𝓡y)∧ (y𝓡z)) ⇒ (x𝓡z) ou encore
𝓡² ⊆ 𝓡
(Définition) une relation 𝓡 sur un ensemble E est une relation d’équivalence si
si elle est réflexive, symétrique et transitive.
(Définition) une relation 𝓡 sur un ensemble E est une relation d’ordre si
si elle est réflexive, antisymétrique et transitive.
(Définition) Composition de relations
Soient 𝓡 ⊆ E × F et S ⊆ F × G deux relations, la composition de 𝓡 et S , notée 𝓡 ◦ S , est définie comme suit :
𝓡 ◦ S = { ( x, z ) I∃ y ∈ F . (( x, y ) ∈ 𝓡 ∧ ( y, z ) ∈ S ) } .
𝓡 ◦ S = { ( x, z) ∈ LxU I (∃b ∈ T I (a,b) ∈ 𝓡 ∧ (b,c) ∈ S)}
JPM : Une Jointure en fait.
(Définition) Fermeture transitive
Soit R ⊆ E × E une relation sur E et n un entier positif. On note R 1 = R et et R = R n − 1 ◦ R . La fermeture transitive est la relation
