1.8. Ensembles finis, n-uplets,
familles, produit
1.9. Opérations, relations
1.10. Construction des termes et énoncés
Sommaire général de l'ouvrage 1.8. 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 de la différence que nous avons expliquée entre les notions d'ensembles et de classes, on comprend aisément que la classe des objets x tels que (x=a ou x=b ou x=c) est un ensemble. Cet ensemble sera noté {a,b,c}. En général, les ensembles obtenus d'une telle manière s'appellent 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, où ensembles à un é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, qui a été 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 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 avec un x fixé 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'énumérer des éléments images en s'intéressant bien plus aux propriétés mathématiques du côté de l'ensemble d'arrivée de cette application qu'à celles de son domaine, lequel est généralement vu comme "en dehors" du système étudié, tout 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 peut introduire 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 dont les éléments images doivent faire partie (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 d'image cet ensemble (ceci sera expliqué dans le prochain texte).
Produit d'une famille d'ensembles
On appelle produit cartésien (ou simplement produit) de E et F, et on note E×F, l'ensemble des couples (x,y) où x ∈ E et y ∈ F. Plus généralement:
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.
En effet, le produit cartésien E×F est ainsi le produit du couple (E,F).
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
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 cela donne E1×E2×E3×E4.
Les deux cas particuliers de produit d'une famille d'ensembles, que sont le produit
de n ensembles et la puissance d'ensembles, ont en commun le cas, avec I={1,…,n}, de
EI=En=E×...×E (où E apparaît n fois).
1.9. 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 de x et y. Mais cette même notation peut se lire en regardant les variables x et y comme liées de domaines ceux de cette opération, et désigne alors cette même opération, de variables renommées de gauche et droite en x et y.
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 varibles de part et d'autre du symbole d'opération. L'important est d'arriver à bien distinguer parmi les symboles d'une formule, lequel est le principal (symbole de l'opération finale utilisant les autres symboles pour définir ses variables), du moins si cela risque autrement de donner un résultat différent. 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. Notons-la g(x)
cette application de variable y. Ainsi g est une application de domaine le domaine de x, à valeurs parmi les applications de domaine celui de 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 également la donnée de son domaine, produit des domaines de ses variables.
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.
Ceux d'arité zéro sont les deux constantes propositionnelles.
Pour les autres, on peut se contenter de ceux qui ne sont constants par rapport à aucune de leurs variables.
En effet, un connecteur qui serait constant par rapport à une variable pourrait être écrit plus simplement en oubliant cette variable, par un connecteur ayant une variable de moins. 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 en entrée est inintéressant. Le deuxième est le "non".
Pour énumérer les connecteurs restants d'arité 2, on peut déjà les classer suivant le nombre d'éléments de leur domaine V×V à 4 éléments, pour lesquels
ils donnent vrai: 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 d'habitude en se ramenant à l'usage du "et" au moyen de négations sur les variables: par exemple (Aet(nonB)). Ceci est bien une forme expressive de la signification de l'énoncé, à savoir la description du cas où il est vrai: sa véracité 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((nonA)et(nonB)), 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)) qui peut également s'écrire (C,nonA)(B), et dont une conséquence est 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).
1.10. 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
comme décrit 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. Ses valeurs (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. On peut donc admettre comme ensemble de variables libres d'un terme ou énoncé donné tout ensemble de symboles de variables libres contenant ceux qui sont effectivement utilisés dans son écriture. Ainsi la liste des variables libres peut-elle s'étendre sans rien faire.
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 peut construire terme de valeur un n-uplet par une liste de n termes entourés des ponctuations adéquates (parenthèses et virgules).
4) Le symbole d'égalité, avec la donnée de deux termes ou plus, donne un énoncé.
5) Le symbole d'appartenance, avec la donnée de deux termes dont le deuxième désigne un ensemble, donne 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. De même fera-t-on plus loin pour les unions, intersections et produits avec un terme désignant une famille d'ensembles.
7) Le symbole de produit cartésien ou d'union ou d'intersection (voir plus loin), avec la donnée de deux termes désignant chacun un ensemble, donne un terme désignant un ensemble. De même fera-t-on plus loin avec le symbole (invisible) de puissance.
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) On peut construire de nouveaux énoncés à partir d'énoncés donnés, en leur appliquant des connecteurs logiques.
Passons maintenant aux 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, partout les mêmes. 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.
10) On constitue un terme désignant une opération (resp. une relation) en écrivant sa définition: par exemple on notera (E×F) ∋ (x,y) ⟼ t
où "x" et "y" sont des symboles de variables, et à la place de t figure un terme (resp. un énoncé) admettant entre autres x et y comme variables libres, E et F sont des termes mais n'ont ni x ni y comme variable libre. On pourra aussi l'écrire (x ∈ E, y ∈ F ⟼ t). Par exemple, (E ∋ x ⟼ f(x,y)) est un terme de variable libre y.
Remarque: on pourrait de manière équivalente poser z=(x,y), et réécrire ce terme sous forme (E×F) ∋ z ⟼ t′ où t′ est le terme obtenu en remplaçant dans t les variables x et y par les termes constitués de l'application de z à un des deux éléments de son domaine, suivant que c'était x ou y.
11) Compréhension: même chose que pour une relation, sauf que le résultat est un ensemble; ce procédé rassemble en une même notation la définition d'une relation décrite en 10), et la prise de son graphe. 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. Cela s'écrit par exemple {(x,y) ∈ E×F| t}=Gr(x ∈ E, y ∈ F ⟼ t).
12) Usage d'un quantificateur sur une ou plusieurs variables: ceci construit un énoncé à partir d'un énoncé donné. Du moment qu'on utilise le même quantificateur, l'appliquer successivement à n variables dans un certain ordre est équivalent à le faire dans un autre ordre, et aussi à le faire d'un seul coup à leur n-uplet de domaine le produit de leurs domaines. On écrira aussi par exemple ∀x,y ∈ E comme abbréviation de ∀x ∈ E, ∀y ∈ E.
Ainsi, étant donné un énoncé R de variables libres x et y (entre autres), l'énoncé (∃(x,y) ∈ (E×F), R) équivaut à (∃x ∈ E, ∃y ∈ F, R).
Enfin, on se permettra parfois de noter l'image d'une application f de domaine E sous la forme {f(x) | x ∈ E}, ce qui permet du même coup de définir f en posant son terme à la place de f(x), et de l'autre côté (au lieu du simple x ∈ E), de définir son domaine par compréhension en écrivant "x ∈ E et...", en faisant attention de garder une telle condition d'appartenance à un ensemble, pour avoir bien ici un ensemble et non une classe.
File translated from
TEX
by
TTH,
version 3.78. On 26 Oct 2007, 14:29.