CH1

LOGIQUE ET THEORIE DES ENSEMBLES

  1. Elément logique
    1. Opérations logiques
    2. Quelques types de démonstrations
  2. Les ensembles et applications
    1. Définition sur les ensembles
    2. Application
    3. La loi de composition interne
  3. Relations binaires
    1. Relation d'équivalence
    2. Relation d'ordre

I] Elément logique

1. Opérations logiques

A partir de 2 proposition P et Q, on peut définir 2 autres proposition : "non P" et "non Q".
Par définition, la proposition "non P" est vraie si P est fausse.
Notation : non P = Pb

Ex : P = (x>2), Pb = (x £ 2)
P = ($ x Î E, x > 0), Pb = ( " x Î E, x £ 0)

Tableau de vérité :

P Q Non P P et Q P ou Q P => Q PÛ Q
V V F V V V V
V F F F V F F
F V V F V V F
F F V F F V V

2. Quelques types de démonstrations

Le but est de démontrer l'implication entre 2 propositions P et Q

II] Les ensembles et applications

1. Définition sur les ensembles

Soit E un ensemble

x appartient à E : x Î E
x n'appartient pas à E : x Ï E
F sous ensemble de E : F Í E

P(E) : Ensemble des sous-ensembles de E

Æ Î P(E)
E Î P(E)
A Í E Û A Î P(E)

Soit A, B, C des sous-ensembles de E

A Í B et B Í C => A Í C

Soit A et B 2 sous-ensembles de E.

Si A Ç B = Æ , A et B sont disjoints
X Î A Ç B Û x Î A et x Î B

Soit A, B, C 3 sous-ensembles de E

A Ç B = B Ç A
A Ç (B Ç C) = (A Ç B) Ç C = A Ç B Ç C
A È B = B È A

Soit E1, ..., En, n ensembles

L'intersection se note : Ç (Ei,i,1,n)
L'union se note : È (Ei,i,1,n)

Soit A une partie de E, on appelle complément de A dans E CE(A), CA, CA, AbE :

Si A Í B, alors CE(B) Í CE(A)

Soit A et B 2 sous-ensembles de E, on appelle différence de A et B noté A\B l'ensemble des éléments de A qui n'appartiennent pas à B

A\B = A Ç CE(B)

 2. Applications

Soit E et F 2 ensembles. On appelle graphe tout sous-ensembles de E x F.

On appelle application la donnée du triplet (E,F,G), où G est un graphe tel que à tout élément x de E, soit associé un unique couple G.

" x Î E, $ ! (x , y) Î G ou " x Î E, $ ! Y Î F/(x , y) Î G

Soit A Í E, f(A) = {f(x), x Î A} = {y Î F, $ x Î A, y = f(x)}

B Í F, f -1(B) = {x Î A, f(x) Î B}

On note F(E,F), l'ensemble des applications de E dans F.

Si E = I un ensemble indice, F(I,F) = FI, et un élément de FI est appelé une famille d'élément de F indexée par I noté (xi)iÎ I.

Soit f : E ® F, soit L Í E

On appelle restriction de f à L, noté f/L l'application L ® F de graphe G Ç (L x F) où G est le graphe de f.

Soit f : E ® F et g : F ® G 2 applications.

On définit l'application composée de f par g, noté f o g comme l'application de E dans G " x Î E, g o f(x) = g[f(x)]

Si f et g sont injectives, g o f est injective

Si f et g sont surjectives, g o f est surjective

Si g o f est injective, alors f est injective

Si g o f est surjective, alors g est surjective.

Soit f : E ® F une application

f est injective Û $ g : F ® E, g o f = IdE

f est surjective Û $ h : F ® E, f o h = IdF

Soit f : E ® F une application.

f est bijective Û $ f -1 : F ® E, f -1o f = IdE et f o f -1 =IdF

f -1 s'appelle la fonction réciproque de f.

Si f et g sont bijectives, alors g o f est bijective et (g o f)-1 = f-1 o g-1.

ATTENTION : Si g o f est bijective alors f et g ne le sont pas forcément.

3. La loi de composition interne

Def : On appelle loi de composition interne sur E, toute application de E x E dans E.

E x E ® E
(a x b)® a o b ou a ^ b ou a * b ...

Def : F Í E on dit que F est stable pour la loi de composition interne (LCI) ^ si " (x,y) Î F², x ^ y Î F

Def : Soit ^ une LCI sur E, on dit que ^ est :

Soit a Î E, on dit que a est régulier à gauche (resp. droite) si l'application E ® E, x ® a ^ x est injective (resp. E® E, x ® x ^ a est injective)
On dit que a est régulier si a est régulier à gauche et à droite.

Def : Soit ^ une LCI qui admet un élément neutre e. Soit a Î E.

On dit que a est inversible à gauche ou symétrisable à gauche si $ b Î E, b ^ a = e.
Alors b s'appelle l'inverse à gauche ou le symétrique à gauche de a. (idem à droite)

Théo : Si ^ est une LCI sur E qui est associative et qui admet un élément neutre e.

Si a Î E, a admet un symétrique à gauche b et un symétrique à droite c, alors b = c.
On dit que a est inversible ou symétrisable, l'inverse de a est noté a-1.
Si a et b sont inversibles dans E, alors a ^ b est inversible d'inverse b-1

III] Relations binaires

1. Relations d'équivalence

Def : Une relation binaire sur E est une partie de E x E. On dit que  est :

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

Def : Soit  une relation d'équivalence sur E. Soit x Î E. On appelle classe d'équivalence de x noté C(x), x(point) ou x (barre), l'ensemble des élément de E qui sont en relation avec x.
On appelle ensemble quotient de E par  , noté E/Â, l'ensemble des classes d'équivalences de E.

Propriétés : Si x1 ¹ x2, 2 éléments de E,

Soit C(x1) Ç C(x2) = Æ
Soit C(x1) = C(x2)

 2. Relations d'ordre

Def : C'est une relation binaire qui est réflexive, antisymétrique et transitive.

Def : Soit (E,£ ) une ensemble ordonné. On dit que E est totalement ordonné ou que l'ordre est total, si " (x,y) Î E², x£ y ou y £ x. Dans le cas où £ est total, le contraire de x £ y est x > y.
Si £ n'est pas totale, on dit que la relation d'ordre est partielle.

Def : Soit (E, Â1), (F, Â2) 2 ensembles ordonnés. Soit f : E ® F une application.

On dit que f est croissante. Si " (x,y) Î E², x Â1 y alors f(x) Â2 f(y)
On dit que f est décroissante. Si " (x,y) Î E², x Â1 y alors f(y) Â2 f(x)
On dit que f est strictement croissante. Si " (x,y) Î E², x Â1 y et x ¹ y alors f(x) Â2 f(y) et f(x) ¹ f(y)

Prop : Soit (E, Â1), (F, Â2) 2 ensembles ordonnés. Soit f : E ® F une application.

Si f est croissante et injective alors f est strictement croissante
Si f est décroissante et injective alors f est strictement décroissante.

Théo : Soit (E, Â1), (F, Â2), (G, Â3) 2 ensembles ordonnés. Soit f : E ® F et g : F ® G 2 applications.

Si f croissante sur E et G croissante sur F, alors g o f est croissante sur E
Si f décroissante sur E et G décroissante sur F, alors g o f est croissante sur E

Def : Soit (E, Â) un ensemble ordonné. Soit m Î E

m est le plus petit élément de E, si " x Î E, m  x
Soit M Î E
M est le plus grand élément de E, si " x Î E, x  M
On note m = min(E) et M = max(E). Soit A Í E
On dit que A est majoré par E, si il existe M Î E tel que " x Î A, x  M. M est un majorant de A. On dit que A est minoré dans E, s'il existe m Î E tel que " x Î A, m  x. m est un minorant de A.
Si A est majoré, et que l'ensemble des majorant admet un plus petit élément, cet élément s'appelle la borne supérieur de A noté sup(A).
Si A est minoré, et que l'ensemble des minorant admet un plus grand élément, cet élément s'appelle la borne inférieur de A noté inf(A).

Théo : Soit (E, Â) un ensemble totalement ordonné. Soit A Í E

b est la borne sup. de A Û " a Î A, a £ b et " c Î E, c < b è $ a Î A, c £ a
i est la borne inf. de A Û " a Î A, i £ a et " c Î E, i < c è $ a Î A, c £ a