[FES] Formalismes, Ensembles et Structure (1)

Vocabulaire ❤️ relatif aux ensembles structures et aux relations

I. Ensembles

1.1 Ensembles et elements

Collection d’objets


Quand on definit un ensemble il faut faire attention aux contradictions

cf Paradoxe de Russel

Pour echapper a ces contradictions > il faut respecter des regles precises pour definir des ensembles Certains ensembles definis de maniere axiomatique (par exemple ) D’autres peuvent etre construits a partir de ceux la avec des operations convenables (par exemple )

1.2 Sous-ensembles

Definition (Sous-ensemble)

Soient E et F deux ensembles. On dit que F est inclus dans E si tout element de F est element de E. On note . On dit aussi que F est un sous-ensemble ou une partie de E.

Exemple :

Deux ensembles sont egaux ssi ils ont exactement les memes elements (si chacun est inclus dans l’autre) :

Un sous ensemble de E peut etre defini comme ensemble des elements de E verifiant une certaine proposition

Exemple : Exercice :

En particulier, si cette proposition est impossible on obtient l’ensemble vide qui doit etre considere comme un sous-ensemble de nimporte quel ensemble. On le note .

Un ensemble qui possede un unique element est appele singleton. Il ne faut pas confondre l’element x et le singleton . On peut ecrire : mais pas l’inverse.

1.3 Produit cartesien

Soit E et F deux ensembles. On peut construire un nouvel ensemble appele produit cartesien de E et F, note , dont les elements sont les couples formes d’un element de E et d’un element de F :

Si on note etc

Exemple : L’ensemble peut etre identifie a un plan muni d’un repere cartesien

1.4 Quantificateurs

1.5 Negation d’une proposition

Definition (Negation d’une proposition)

Soit P une proposition qui est vraie (1) ou fausse (0). On note la negation de la proposition P, c-a-d la proposition qui est vraie si P est fausse, et faussi si P est vraie. Notons que

“et” se note aussi “ou” se note aussi

D’autre part, comme l’implication possede la table de verite

P Q
V V V
V F F
F V V
F F V

La proposition est logiquement equivalente a ou dans le cadre de la logique classique

1.6 Negation d’une proposition avec des quantificateurs

ex :

2 Ensemble des parties d’un ensemble

2.1 Ensemble

Ex si alors

Remarque : L’ensemble n’est pas vide puisqu’il contient l’element . C’est un singleton

2.2 Operations dans

Soit E un ensemble et A et B deux parties de E. On peut definir de nouvelles parties de E par les operations suivantes :

ie ex

ie ex

ie ex

ie ex

ie ex

2.3 Proprietes

Proprietes


2.4 Exercices d’application

Enonce : Soit A B et C trois parties d’un meme ensemble E. Demontrer que

: Ce qui appartient a A et a B ce qui n’appartient pas a A mais appartient a C : Ce qui appartient a A mais pas a C ce qui n’appartient ni a A ni a B ce qui appartient a A et a B

Solution : Soit un element de , x appartient au moins a l’un des deux ensembles ou

Si

Si

Dans tous les cas :


3. Application d’un ensemble dans un autre

3.1 Definition

Definition (Applications)

Soient E et F 2 ensembles. On appelle application de E dans F la donnee des ensembles E, F et d’une partie de E x F telle que pour tout element de E il existe un element de F tel que

3.2 Composition des applications

Soit E, F et G trois ensembles, f une application de E dans F et g une application de F dans G on appelle application composee de f et g l’application de E dans G qui a un element de E fait correspondre l’image par g de l’image par f de . On note cette application

Exemples :

Theoreme 1

Si E, F, G, H sont quatre ensembles et f, g, h trois applications appartenant respectivement a

Demonstration Les deux applications et ont le meme ensemble de depart : E et le meme ensemble d’arrivee H. Blablabla

L’ensemble des applications de E dans F est note ou encore

3.3 Famille d’elements d’un ensemble

Definition (Famille)


Injectivite et surjectivite

4.1 Equation

Soit f une application de E dans un ensemble F, On appelle equation une egalite de la forme (avec ici x solution de l’equation) ou est un element fixe de F ; on appelle la solution de l’equation blabla

Definition (Application injective)

Soit f une application d’un ensemble E blabla A l’aide de quantificateurs, l’injectivite de f s’ecit :

Theoreme 2

  1. La composee de deux injectives est une injection
  2. Si la composee est injective, f est injective

Definition (Application surjective)

A l’aide de quantificateurs, la surjectivite de f s’ecit :

Theoreme 2

  1. La composee de deux surjectives est une surjection
  2. Si la composee est injective, g est injective

4.4 Application bijective

5 Image directe ou reciproque d’une partie

5.1 Image d’une partie de l’ensemble de depart

Definition (image directe)

Pvar definition :

Definition (image reciproque)

Par definition :

6. Relation d’ordre

6.1 Relation binaire

On appelle relation binaire definie sur un ensemble E la donnee de e et d’une partie quelconque de . On note pour

Exemples : Dans divise y, etc

Une relation binaire definie sur E est une relation d’ordre si elle est :