1.7. Ensembles finis, n-uplets,
familles, produit
1.8. Opérations, relations
1.9. Construction des termes et énoncés
1.7. Ensembles finis, n-uplets, familles, produit Existence des ensembles finis
Soit une liste finie donnée d'objets fixés, par exemple trois objets notés a, b, c. Alors, au vu des explications précédentes sur quelles classes sont des ensembles, on voit aisément que la classe des objets x tels que (x=a ou x=b ou x=c) est un ensemble. On le notera {a,b,c}. Les ensembles qu'on peut obtenir par ce prodédé sont des ensembles finis. Le nombre d'éléments d'un ensemble fini E est un nombre entier naturel appelé le cardinal de E et noté #E.
Ceci n'est pas une définition rigoureuse dans le cas général. Nous ne définirons rigoureusement les notions d'ensemble fini et de cardinal que bien plus tard. En attendant, il suffira pour nos besoins de considérer des ensembles finis à un petit nombre d'éléments énumérés comme nous venons de faire, où la notion de leur cardinal est "évidente". Reprenons-les en commençant par les plus petits, suivant leur cardinal:
- L'ensemble vide ∅, à zéro élément
- Les singletons, ensembles à un unique élément, de la forme {a} pour un objet a.
- Les paires, ensembles à deux éléments, de la forme {a, b} pour deux objets a ≠ b (car si a=b l'ensemble {a, b} ne serait que le singleton {a}).
Certaines expressions axiomatiques de théorie des ensembles comportent l'axiome de la paire qui énonce que pour tous objets a et b, la paire {a, b} existe (comme ensemble objet de l'univers; le cas a=b redonnant les singletons).
De là, et par l'axiome de réunion, on peut définir la réunion de deux ensembles E et F, notée E∪F, par
E∪F= ⋃ {E,F}
Elle se caractérise par : E ⊂ E∪F, F ⊂ E∪F et ∀x ∈ E∪F, x ∈ Eoux ∈ F.
Remarquons que les axiomes de la paire et de la réunion suffisent à assurer la construction à la main de tous les autres ensembles finis, par exemple
{a,b,c,d,e}={a,b}∪({c,d}∪{e,e}).
n-uplets
Pour chaque entier naturel n on appellera n-uplet
toute application de domaine un ensemble à n éléments, qu'en pratique on supposera fixé une fois pour toutes pour chaque n.
En particulier on l'appelle un couple pour n=2, un triplet pour n=3, un quadruplet pour n=4, etc.
Par exemple une interprétation d'une liste de symboles de variables libres se formalise comme une application
de l'ensemble de ces symboles dans l'univers des objets mathématiques.
Comme en pratique on n'utilise qu'un nombre fini n de symboles à la fois,
c'est alors un n-uplet.
Pour spécifier par le langage un n-uplet particulier, la méthode usuelle est de spécifier séparément l'image
de chaque élément de son domaine, en figurant ce domaine à n éléments sous forme des n lieux successifs séparés par des virgules à l'intérieur d'une parenthèse, et en mettant en chacun de
ces n lieux un terme définissant l'objet qu'on assigne pour image à cet élément.
Ainsi par exemple étant donnés x variable libre et f application, on désigne par (3,f(x)) le couple dont l'image du premier élément est 3 et l'image du deuxième élément est l'image de x par f.
Parmi tous les couples de même domaine, la condition restante d'égalité entre couples, cas particulier de condition d'égalité entre applications, s'explicite par développement du
quantificateur universel sur son domaine à deux éléments:
(x,y)=(z,t) ⇔ (x=zety=t)
et on peut en dire de même pour les n-uplets (avec ce qu'on expliquera sur les connecteurs).
Familles
La notion de famille est rigoureusement synonyme de celle d'application; son appellation
(par rapport à celle des applications) est donc une vague affaire de contexte, de point de vue ou de caractère pratique des notations. On pourrait plus ou moins l'expliquer comme une généralisation de l'usage des n-uplets au cas où le domaine peut être infini, alors qu'il n'intervient encore que plus ou moins comme une sorte d'ensemble de symboles: à savoir, une manière d'étudier les éléments images en s'intéressant plus aux propriétés du côté de l'ensemble d'arrivée qu'à celles du domaine, lequel est généralement vu comme fixe et "en dehors" du système étudié, comme les symboles sont en dehors de l'univers mathématique considéré.
Pour désigner l'image d'un élément i par une famille u, on utilise la notation ui plus compacte que celle u(i) employée quand u est appelée une application. Ce qui était entre parenthèse est ici en indice, ne laissant guère de place pour y insérer de grosses opérations, conformément au fait de ne pas étudier le domaine comme système mathématique. Ceci a pour effet de suggérer en quelque sorte qu'il y aurait au fond un symbole différent pour chaque valeur de cet indice.
Pour définir une famille u de domaine I par un terme de variable i ∈ I, on emploie au lieu de (I ∋ i ⟼ terme) la notation suivante imitée de la notation utilisée pour les n-uplets qui mettait les termes entre parenthèses, sauf que la multiplicité des places et l'écriture d'un différent terme dans chaque place sont remplacées par la multiplicité des valeurs possibles du symbole i qui intervient dans le terme:
u=(terme)i ∈ I ⇔ (
Dom
u=Iet ∀i ∈ I,ui=terme).
On dit que la famille u est indexée par I, pour dire que son domaine est I.
On peut introduit une famille u en précisant en notation mathématique son domaine I, en l'écrivant par exemple (ui)i ∈ I de même que la notation E ∋ x ⟼ f(x) désigne l'application f en précisant son domaine E.
On peut préciser en langage courant la classe à laquelle doivent appartenir les éléments images (autrement dit l'ensemble d'arrivée, si c'est un ensemble), par un complément de nom: par exemple on appelle "famille d'ensembles" une famille dont tous les éléments images sont des ensembles.
Ainsi, on parlera de "famille de..." (une certaine sorte d'objets) de la même manière qu'on parle d'un "ensemble de...", et ces deux notions joueront un rôle similaire: on passe d'une famille à un ensemble en prenant son image, et inversement, d'un ensemble à une famille, en prenant une famille ayant pour image cet ensemble (ceci sera expliqué dans le prochain texte).
Produit d'une famille d'ensembles Définition. Etant donnée une famille d'ensembles (Ei)i ∈ I on appelle produit des Ei pour i ∈ I (ou produit de la famille (Ei)i ∈ I), et on note ∏i ∈ IEi, la classe des familles (xi)i ∈ I (ou applications de domaine I) telles que ∀i ∈ I, xi ∈ Ei.
Pour chaque entier n explicite on a
Proposition. Tout produit d'un n-uplet d'ensembles est un ensemble.
Preuves (une preuve différente pour chaque valeur de n): soient n ensembles E1,...,En. Introduisons successivement n symboles de variables x1,..., xn, où chaque symbole de variable xi est introduit comme ayant pour domaine l'ensemble Ei. Alors, on peut facilement vérifier que d'un point de vue global, l'ensemble des valeurs possibles de l'expression constituée du n-uplet de ces symboles, (x1,…, xn), est le produit de la famille (E1,…, En). Donc ce produit est bien un ensemble. CQFD
Avec n=2 le produit d'un couple (E,F) se nomme le produit cartésien (ou simplement produit) de E et F, et se note E×F. C'est l'ensemble des couples (x,y) où x ∈ E et y ∈ F.
Le produit du n-uplet (E1,…, En) de domaine (pour fixer les idées) I={1,…,n}, se note également E1×...×En. Par exemple pour n=4 on note E1×E2×E3×E4.
1.8. Opérations, relations Opérations
La notion d'opération généralise la notion d'application au cas où le résultat dépend de la valeur, non plus d'une seule variable de domaine donné, mais d'une liste finie de variables de domaines respectifs donnés. Le nombre de ces variables s'appelle l'arité de cette opération.
Une opération d'arité zéro est une constante; une opération d'arité 1 est une application. Il ne reste plus qu'à regarder le cas des opérations d'arité 2 ou plus.
Par exemple on note f(x,y) le résultat d'une opération f, suivant les valeurs des variables libres x et y. Mais on peut aussi lire cette même notation en regardant les variables x et y comme liées de domaines ceux des variables de f. Elle désigne alors cette même opération f où le rôle des symboles de variables est joué par x et y au lieu des positions gauche et droite dans la parenthèse.
Les opérations sont parfois notées suivant différentes dispositions du symbole de relation et des positions des variables. En particulier une opération à deux variables comme par exemple l'addition se note souvent en posant les variables de part et d'autre du symbole d'opération. L'important est d'arriver à bien distinguer parmi les symboles d'une formule (terme ou énoncé), lequel est le principal (qui donne le résultat) et comment les autres se répartissent en groupes (sous-formules) donnant les valeurs respectives des variables dont dépend le symbole principal pour donner son résultat (du moins si le résultat dépend de cette répartition). Pour cela, on peut utiliser des parenthèses.
Pour ramener la notion d'opération à celle précédente des applications, on peut considérer des points de vue intermédiaires entre celui où toutes les variables sont libres (fixées), où donc on voit une constante, et le cas où toutes les variables sont liées, où on voit toute l'opération. A savoir, des points de vue suivant lesquels certaines variables sont libres, d'autres liées chacun par son domaine. On voit alors une opération ayant pour seules variables celles qu'on a liées.
Par exemple, dans le cas d'une opération à deux variables f(x,y), si on fixe x mais on voit y variable, on voit alors une
application de variable y, mais cette application dépend de x.
Ceci définit une application g de variable x, qui à toute valeur de x associe une application g(x) de variable y. Ainsi, pour toutes valeurs de x et y dans leurs domaines respectifs,
f(x,y)=g(x)(y).
Cette formule constitue une définition de g en termes de f mais
aussi de f en termes de g, de sorte que ces f et g sont au fond deux manières de représenter une même information.
Une opération sera dite constante par rapport à une de ses variables x ssi l'application qui à toute valeur de x associe l'opération qui en résulte sur les autres variables, est une application constante.
Cela équivaut à dire que quelles que soient les valeurs fixées des autres variables, l'application de variable x qui en résulte est constante.
Une opération peut également s'interpréter comme une application de domaine le produit des domaines de ses variables. Cette interprétation est plus naturelle que la précédente (qui consistait à fixer successivement les variables une par une) car elle préserve la symétrie des rôles entre les symboles de variables, et permet de se ramener directement au seul usage d'applications, sans nécessiter de multiples décompositions intermédiaires quand le nombre de variables augmente.
Ainsi, toute expression qui donne un résultat dépendant des valeurs d'une liste de n variables, se voit comme dépendant en fait du n-uplet des valeurs de ces variables. Par exemple la notation de l'ensemble {x,y,z}, qui dépend des variables x,y,z, est en fait synonyme de la notion d'ensemble image du triplet (x,y,z). Ainsi (x=y=z), qui d'abord est l'abbréviation de ((x=y) et(y=z)), signifie finalement que le triplet (x,y,z) est une application constante, de sorte qu'il en résulte aussi x=z.
Remarquons que quand on considère une application comme cas particulier d'opération, puis cette opération comme cas particulier d'application, ce n'est plus la même application, car son domaine E est remplacé par le produit du 1-uplet (E) qui en est une copie: le rôle d'un élément x de E est joué par le 1-uplet (x) ∈ ∏(E). Aussi, quand partant d'une opération on se met à considérer le cas particulier d'opération que constitue le cas particulier d'application qu'elle constitue, cette deuxième opération
est d'arité 1 même si ce n'était pas le cas de la première.
Relations
On appelle relation une opération arrivant dans V.
On pourrait employer pour jouer le rôle de relation, l'ensemble des n-uplets sur lesquels la relation donne la valeur "vrai", appelé son graphe. La même remarque que nous avions faite avec les relations unaires s'applique: la notion de relation comporte, en plus de la donnée du graphe, celle de son domaine, produit des domaines de ses variables, qui englobe le graphe.
De même que pour les opérations, les relations à deux variables sont souvent notées en plaçant les variables de part et d'autre du symbole de relation.
Opération conditionnelle
On appelle variable propositionnelle une variable de domaine V.
Considérons d'abord une application de domaine V. C'est donc un couple. On choisira la convention de représentation de V par le domaine d'un couple, suivant le couple (vrai,faux). Ainsi pourra-t-on appliquer un couple à une valeur de vérité : par définition, l'expression (x,y)(P) où P est une variable propositionnelle, vaudra x si P est vrai, et y si P est faux.
Plus généralement, considérons une opération dont une des variables est une variable propositionnelle. Fixer d'abord cette variable fait de cette opération un couple d'opérations, ayant chacune pour variables les seules autres variables. On peut donc exprimer une opération dépendant d'une variable propositionnelle sous forme d'un couple de deux opérations n'ayant pas cette variable.
Connecteurs logiques
On appelle connecteur logique toute relation ne dépendant que de variables propositionnelles. Ils serviront à construire les énoncés.
Enumérons ceux qui seront utilisés en pratique en étant nommés par un symbole. Seuls seront considérés ceux qui
ne sont constants par rapport à aucune de leurs variables, tout connecteur constant par rapport à une variable étant remplaçable par un connecteur d'arité plus petite, oubliant cette variable.
Ceux d'arité zéro sont les deux constantes propositionnelles.
Nous noterons ici A,B,C les variables propositionnelles suivant les besoins, et emploierons la convention ci-dessus d'écriture d'applications de domaine V sous forme de couples.
Il reste alors deux connecteurs d'arité 1: (vrai,faux) et (faux,vrai). Le premier rendant la même valeur qu'il reçoit, on n'a pas besoin de le nommer (il disparaît dans les formules). Le deuxième est le "non".
Trions les connecteurs restants d'arité 2 suivant le cardinal de leur graphe (partie de l'ensemble V×V à 4 éléments): 1,2 ou 3 (les autres étant constants).
Parmi les connecteurs où il y a un seul couple de valeurs sur lequel il donne vrai, seul le cas où c'est le couple (vrai,vrai) reçoit habituellement une notation, à savoir "et". On peut également écrire (AetB) sous la forme (A,faux)(B). Les autres connecteurs qui ne valent vrai que pour un couple, s'écrivent au moyen du "et" et de négations sur les variables: par exemple (Aet(nonB)). Ceci exprime bien la signification de l'énoncé, en décrivant le cas où il est vrai: il signifie que A est vrai et que B est faux.
Les cas où il y en a 3 pourraient se ramener au cas où il y en a un par la négation du résultat, mais deux autres symboles sont habituellement employés: le "ou" et l'implication (⇒).
(A ou B) se définit par non((nonA) et(nonB)), ou de manière équivalente par (vrai,A)(B). Ainsi il vaut vrai sauf si A et B sont tous deux faux.
Le connecteur d'implication A⇒B est celui qui vaut faux uniquement si A=vrai et B=faux. On peut le traduire par non(AetnonB), par ((nonA) ouB), ou encore par (B,vrai)(A). Donc dire que A⇒B est vrai, exprime que, si A est vrai alors B est vrai, mais ne nous renseigne pas (étant toujours vrai) si A est faux. L'implication A⇒B est équivalente à nonB⇒nonA, appelée sa contraposée.
Pour les cas de connecteurs où il y a exactement deux éléments de V×V donnant vrai, ne devant pas se trouver sur la même ligne ou colonne du tableau afin qu'il ne soit constant par rapport à aucune variable, il ne reste que deux possibilités qui sont les deux diagonales du tableau.
Ce sont l'équivalence ⇔ (égalité dans V) et sa négation A ⇎ B qu'on peut aussi écrire A XOR B ("ou exclusif" car se réécrivant ((AouB)etnon(AetB))), ou encore A ⇔ nonB.
L'énoncé A ⇔ B peut également s'écrire (A,nonA)(B), ou encore ((AetB)ou(nonAetnonB)), voire même ((AouB)⇒(AetB)). Mais la traduction la plus utilisée en pratique est ((A⇒B) et(B⇒A)).
Ainsi, pour prouver une équivalence, la méthode souvent employée consiste à prouver séparément chacune de ces deux implications, dont la première (A⇒B) est dite directe, et la deuxième, (B⇒A), est dite réciproque.
Voyons maintenant les quelques cas de connecteurs d'arité 3 et plus qui ont leur propre notation.
D'une part, celle consistant en une répétition de "et" ou de "ou":
D'autre part on retrouve l'abbréviation qu'on avait pour une chaîne d'égalités, ici notées par le symbole
d'équivalence: (A ⇔ B ⇔ C) est d'abord l'abréviation de ((A ⇔ B) et(B ⇔ C)), qui implique que A ⇔ C.
Enfin, on définit de même la double implication (A⇒B⇒C) comme l'abréviation de ((A⇒B) et(B⇒C)), et qui implique A⇒C. Ceci se généralise à des chaînes d'implications de longueur quelconque, par exemple
(et en fait Ai⇒Aj dès que i < j).
Les connecteurs que nous venons d'énumérer suffisent à exprimer tous les connecteurs de toutes les arités plus grandes, puisque nous avons vu que ceux-ci peuvent se ramener à des expressions de la forme (A,B)(C) qui se réécrivent, au choix: ((CetA)ou(nonCetB)), ou encore ((C⇒A) et(CouB)), ou enfin sous forme de double implication: (nonB⇒C⇒A).
Remarquant que (A⇒B⇒C) peut également s'écrire (C,nonA)(B), on en déduit la formule amusante mais inutile
non
(A⇒B⇒C) ⇔ ((
non
A)⇒B⇒(
non
C)) ⇔ (C⇒(
non
B)⇒A).
1.9. Construction des termes et énoncés. Nous allons maintenant récapituler et compléter la description de la manière dont se construisent les termes et les énoncés.
Un terme (respectivement un énoncé), est un assemblage de symboles construit par une succession d'usage des procédures décrites plus bas. Il désignera un objet (respectivement une valeur de vérité)
dépendant des valeurs d'une liste donnée de symboles de variables appelés ses variables libres,
et calculé en considérant ces variables comme des constantes. Puis, passant au point de vue global en liant ces variables à leurs domaines respectifs, il désignera une opération (respectivement une relation) de variables ces variables libres. Les valeurs d'un terme (résultats possibles de l'opération) peuvent être, suivant les cas, soit des éléments de nature non précisée, soit des ensembles, des applications, des opérations ou des relations.
Il n'est pas nécessaire que toutes les variables libres soient effectivement utilisées dans
l'écriture d'un terme ou énoncé; un terme où ne figure pas une variable libre désignera donc une opération constante par rapport à cette variable. Tout ensemble de symboles de variables contenant ceux qui apparaissent effectivement comme paramètres dans l'écriture d'un terme ou énoncé peut donc tenir lieu d'ensemble de ses variables libres.
1) Termes atomiques: tout symbole de constante ou de variable (alors libre) est un terme, dit terme atomique. Du côté des énoncés, il n'y en a que deux ainsi: les deux valeurs de vérité.
Les procédés suivants 2) à 10) permettent de construire de nouveaux termes et énoncés à partir de termes et énoncés existants ayant tous la même liste de variables libres, interprétées comme fixes dans toutes ces opérations.
2) On peut construire un terme, respectivement un énoncé, de variables libres données, sous forme des données de:
• un terme de valeur une opération T, respectivement une relation (cas particulier); notons X la liste (finie) des variables de l'opération T (donc, autres que les variables libres).
• une famille indexée par X, de termes de valeurs appartenant aux domaines respectifs des variables de T (donc si un élément de X est une variable propositionnelle, le terme à lui associer est un énoncé).
La valeur de ce terme est le résultat de l'opération T appliquée aux valeurs des termes de la deuxième donnée.
3) On constitue un terme de valeur un n-uplet, par une liste de n termes entourés des ponctuations adéquates (parenthèses et virgules). Les n éléments du domaine de ce n-uplet pourront s'énumérer par n symboles de constantes (les chiffres de 1 à n), de sorte qu'appliquer suivant 2) ce n-uplet, vu comme application, au k-ième de ces symboles, redonnera la valeur du k-ième terme (quelque soit k de 1 à n).
4) Le symbole d'égalité, avec la donnée de deux termes ou plus, constitue un énoncé.
5) Le symbole d'appartenance, avec la donnée de deux termes dont le deuxième désigne un ensemble, constitue un énoncé.
6) Le symbole d'union, avec la donnée d'un terme désignant un ensemble d'ensembles, donne un terme désignant un ensemble.
7) Le symbole de produit cartésien ou d'union, avec la donnée de deux termes désignant chacun un ensemble, donne un terme désignant un ensemble.
8) Chacun des symboles Dom et Im (domaine et image) avec la donnée d'un terme désignant une application, donne un terme désignant un ensemble.
9) Le symbole Gr, avec la donnée d'un terme designant une relation unaire, désigne un ensemble.
10) On peut construire de nouveaux énoncés à partir d'énoncés donnés, en leur appliquant des connecteurs logiques.
Puis il y a les procédés permettant de construire un terme ou énoncé dont l'ensemble A des variables libres sera strictement inclus dans l'ensemble B des variables libres de celui utilisé pour cette construction. Les variables libres de A se comportent exactement comme plus haut: comme des constantes. Les autres variables deviennent des variables liées et n'intéressent donc plus le statut de l'énoncé obtenu, ni par leur nom (remplaçable sans changement de résultat) ni par leur valeur (qu'elles n'ont plus puisqu'elles les ont toutes dans leurs domaines respectifs). Pour cela, il faut énumérer les symboles de variables à lier (non dans A), et rapporter chacun à son domaine, ensemble donné comme valeur d'un terme (le plus souvent atomique) n'ayant que A comme ensemble de variables libres. Le principal procédé est le suivant (les autres pouvant être vus comme faits de 11) suivi d'un opérateur appliqué à la relation ou opération obtenue):
11) On constitue un terme (resp. un énoncé) pour désigner une opération (resp. une relation) en écrivant sa définition: par exemple on notera (E ∋ x, F ∋ y ⟼ t)
où x et y sont des symboles de variables, E et F sont des termes souvent atomiques désignant des ensembles, et à la place de t figure un terme (resp. un énoncé) ayant x et y comme variables libres supplémentaires. Si E=F on simplifie la notation en (E ∋ x, y ⟼ t). Par exemple, (E ∋ x ⟼ f(x,y)) est un terme de variable libre y, et de valeur une application de domaine E.
On pourrait de manière équivalente l'écrire (E×F) ∋ (x,y) ⟼ t. En effet, posant z=(x,y), cela revient à écrire (E×F) ∋ z ⟼ t′ où t′ est le terme obtenu en remplaçant dans t les variables x et y respectivement par les termes z(0) et z(1), où {0,1}=Domz de sorte que z(0)=x et z(1)=y.
12) Compréhension: constitué du 11) dans le cas d'un énoncé A, suivi de la prise du graphe et donc de valeur un ensemble. On note {(x,y) ∈ E×F| A}=Gr(E ∋ x, F ∋ y ⟼ A). Le plus souvent il n'y a qu'une variable à lier, ce qui donne une partie de son domaine. Mais si on veut le faire avec n variables (n > 1), on a alors un ensemble de n-uplets.
13) Usage d'un quantificateur sur une ou plusieurs variables: ceci construit un énoncé à partir d'un énoncé donné. L'application d'un même quantificateur à n variables successives revient aussi à le faire d'un seul coup à leur n-uplet de domaine le produit de leurs domaines, et donc ne dépend pas de leur ordre : étant donné un énoncé R de variables libres x et y, (∃(x,y) ∈ (E×F), R) équivaut à (∃x ∈ E, ∃y ∈ F, R). Pour le cas F=E on abbrègera ∀x ∈ E, ∀y ∈ E en ∀x,y ∈ E.
14) Notant l'image d'une application f de domaine E sous la forme {f(x) | x ∈ E}, cette notation polyvalente permet à la fois de définir f en posant son terme à la place de f(x), et/ou de définir son domaine par compréhension en écrivant "x ∈ E et..." au lieu du simple x ∈ E, en prenant soin de garder une telle condition d'appartenance à un ensemble, pour avoir bien ici un ensemble et non une classe.
Par la suite seront introduits de même pour la construction des termes des symboles d'union, de produit et d'intersection (pour des familles), d'intersection (pour 2 ensembles ou un ensemble non vide d'ensembles), d'ensembles des parties (pour un ensemble), ainsi que le symbole (invisible mais rigoureusement ordinaire) de puissance entre 2 ensembles. Chacun ayant de même ses propres contraintes naturelles sur la nature des constituants qu'ils utilisent.
File translated from
TEX
by
TTH,
version 3.78. On 5 Sep 2008, 14:01.