Communications mathématiques

Communication 1

20 septembre 2020

Samuel,

 

Chapitre 1 : Dénombrement, récurrence

Le premier chapitre de ton cours de maths-spécialité terminales traite des ensembles. La théorie des ensembles est une branche importante des mathématiques. Le mathématicien qui pensa cette théorie est Georg Cantor, né à Saint-Pétersbourg en 1845, d’un père industriel danois et d’une mère violoniste autrichienne. Georg qui fut lui-même un excellent violoniste, associa toute sa vie musique et mathématique. Pour lui les mathématiques étaient aussi un art : il était permis de penser tous nouveaux concepts pourvu qu’ils ne mènent à aucune contradiction logique.

Son père partit en Allemagne en 1856 le climat de la capitale de Pierre le Grand étant trop rigoureux pour sa santé. C’est ainsi que Cantor devint allemand. Il garda toujours la nostalgie de Saint-Pétersbourg.

En 1874 Cantor introduisit pour la première fois le concept de « nombre d’éléments d’un ensemble infini » concept qu’il nomma « puissance d’un ensemble infini » rebaptisé aujourd’hui « cardinal d’un ensemble infini». Ainsi lança-t-il la notion d’ensemble en l’associant à ses études sur l’infini.

Le choix du mot « cardinal » plutôt que celui de nombre d’éléments pour un ensemble infini revenait à se dégager de l’idée usuelle de nombre, concept toujours déterminé et fini dans son écriture, pour accéder à l’idée générale de nombre, au-delà de son écriture finie.

Ce faisant Cantor affirmait qu’il était possible d’atteindre par l’entendement le cardinal d’un ensemble infini ce qui était à l’époque considéré comme une hérésie. Seul Dieu avait le pouvoir de penser l’infini.

Depuis Aristote, il était convenu que l’infini ne pouvait jamais être atteint, qu’il ne pouvait qu’être approché. L’infini existait en puissance (en possibilité) mais pas en acte. Par exemple il était possible de commencer à compter à partir de 0 : 0-1-2-3-4 mais il n’était pas possible de terminer ce comptage, ce dénombrement. Il était possible de s’engager dans le dénombrement 0-1-2-3-4 … mais impossible de l’achever. L’infini existait en puissance, pas en acte. Cantor, en artiste qu’il était, imagina que cet impossible était possible, qu’il était possible d’atteindre l’infini en pensée, qu’il était possible de passer de la puissance à l’acte. Cette audace fonda l’un des monuments les plus imposants des mathématiques : la théorie des ensembles.

Dans les mathématiques courantes nous utilisons l’infini en puissance. Il est noté ∞.

Ainsi lorsque nous étudions la limite d’une somme d’une suite géométrique S_n de premier terme u₀ et de raison q, S_n = u_n (1 – qⁿ⁺¹) / (1- q) et que nous écrivons, quand 0 < q < 1

lim S_n = u₀ / (1 – q) [car qⁿ⁺¹ tend vers 0 quand n tend vers l’infini] )

n→∞

l’expression n→∞ signifie : n tend vers l’infini, mais il ne l’atteint pas ; nous raisonnons alors sur un infini en puissance, pas en acte.

 

1/ Les ensembles finis

Un ensemble fini est une collection d’un nombre fini d’éléments. En général nous étudions des éléments qui sont des nombres ou des lettres. Mais l’idée d’ensemble réfère à des éléments qui peuvent être n’importe quels objets. Notons bien que nous nous intéressons ici à des ensembles finis, non pas aux ensembles infinis, ces ensembles qui portèrent la pensée de Cantor.

Le cardinal d’un ensemble est son nombre d’éléments. Le titre de ce chapitre est : « dénombrement, récurrence ». Le dénombrement est la détermination du nombre d’éléments (le cardinal) d’un ensemble. Quand il s’agit d’un ensemble infini ce cardinal doit être, en tant que signe, écrit, inventé. Cantor pensa à la première lettre de l’alphabet hébreu, l’aleph, ℵ, pour désigner les cardinaux infinis. Comme il trouva qu’il existait différents cardinaux infinis, certains plus grands que d’autres, bien qu’ils fussent tous infinis, il les indiça pour les différencier.

Un ensemble est une donnée d’éléments non ordonnés. Ainsi l’ensemble E : {a ; b} formé de deux lettres, peut aussi s’écrire {b ; a} (les éléments sont séparés par un ; )

Notons que lorsqu’il s’agit de désigner la liste des éléments d’un ensemble nous devons encadrer cette liste par des accolades. Le choix des accolades signifie que nous parlons d’un ensemble.

Notons aussi qu’un ensemble est un concept différent de ses éléments. Ainsi l’ensemble des chevaux n’est pas lui-même un cheval (dixit un autre mathématicien de renom : Bertrand Russel).

Un ensemble ne contient pas de doublon. Tous les éléments sont différents. On ne peut donc pas parler de l’ensemble {a,b,a} mais de l’ensemble {a,b}.

On note ∅ et on appelle ensemble vide l’ensemble qui ne contient aucun élément. Cet ensemble est aussi noté : { } avec un vide à l’intérieur des deux accolades.

Soient E et F deux ensembles finis. L’inclusion de F dans E est notée ⊂ .

On écrira F ⊂ E (F inclus dans E) et l’on dira que F est un sous-ensemble de E ou encore que F est une partie de E pour signifier que tous les éléments de F sont contenus dans E et en sont des éléments.

La proposition F ⊂ E est donc synonyme de : ∀ x, ( x ∈ F) ⇒ ( x ∈ E)

Deux ensembles E et F sont égaux si E ⊂ F ET si F ⊂ E,

c’est à dire ∀ x, ( x ∈ F) ⇔ ( x ∈ E) [flèche double implication]

 

a) Notion d’union et d’intersection d’ensembles finis

Soient E et F deux ensembles finis. La réunion de E et de F est un unique ensemble. La réunion est notée : ∪

A = E ∪ F signifie : ∀ x ∈ A, x ∈ E ou x ∈ F.

L’intersection de E et de F est un unique ensemble. L’intersection est notée : ∩

A = E ∩ F signifie ∀ x ∈ A, x ∈ E et x ∈ F

Si E et F sont disjoints, c’est-à-dire s’ils n’ont aucun élément commun alors A = E ∩ F = ∅

 

Il est utile de pouvoir visualiser ces définitions. Visualiser, c’est recourir à la pensée spatiale, à ton imaginaire. La compréhension des mathématiques passe par deux modes de pensée. La pensée analytique, qui raisonne, qui progresse d’une étape du raisonnement à une autre étape, pensée qui est programmable (informatique). Cette pensée travaille sur de pures abstractions. Comme elle progresse d’une étape à une autre, il y a succession temporelle, c’est-à-dire qu’une étape en suit une autre, etc. Aussi cette pensée est qualifiée de temporelle ou de linéaire.

Il y a la pensée qui travaille avec l’imaginaire, c’est-à-dire qui travaille sur des images. Cette pensée ne passe pas par le raisonnement, elle est visionnaire. Cette pensée est qualifiée de spatiale. L’image donne un panorama dans son ensemble, dans le même instant, d’un événement mathématique même complexe. L’image est le plus souvent suscitée volontairement, mais parfois, plus rarement, l’image te vient sans intervention volontaire. Alors tu es inspiré, alors tu es le messager à qui une réalité que nul ne connaît te confie ses secrets. A charge pour toi, ensuite, de transmettre ce savoir qui t’est donné. Ce qui t’inspire parle certes à toi, mais cela parle aussi au monde par ton intermédiaire.

Dans le fichier joint l’image associée le plus souvent aux ensembles s’appelle diagramme de Venn. Il existe d’autres images dont je te parlerai.

 

Voici un addendum à l’étude des ensembles, hors programme terminales, mais parfois utile, même en terminales pour résoudre certains problèmes. Il est possible de comprendre ces propositions en t’appuyant sur ta seule intuition analytique. Il est nécessaire bien entendu de les démontrer, mais ce type de démonstration est du programme de première année de prépa ou de licence.

Voici cet addendum.

Propositions.

Soient quatre ensembles finis A, B, C, D. On a alors :

1) A ⊂ C et B ⊂ C ⇒ A ∪ B ⊂ C

2) A ⊂ B ⇒ A ∩ C ⊂ B ∩ C

3) A ⊂ B ⇒ A∪ C ⊂ B ∪ C

4) A ⊂ B et C ⊂ D ⇒ A∪ C ⊂ B ∪ D

5) A ⊂ B et C ⊂ D ⇒ A ∩ C ⊂ B ∩ D

Attention, il s’agit de simples implications. Les réciproques ne sont pas toujours vraies.

Du reste il n’est pas si compliqué que cela de démontrer ces propositions. Il suffit de recourir aux définitions.

Prenons par exemple la première proposition.

A ⊂ C et B ⊂ C ⇒ A ∪ B ⊂ C

Quelles sont les hypothèses ? (Toujours noter les hypothèses de départ pour démarrer le raisonnement, cette notation est le moment 1 du déroulé linéaire ou temporel du raisonnement).

Ces hypothèses sont les suivantes :

∀ x ∈ A, x ∈ C et ∀ y ∈ B, y ∈ C

Or A ∪ B est l’ensemble qui contient tous les éléments et seulement tous les éléments de A et de B. Donc ∀ x ∈ A et ∀ y ∈ B, x et y ∈ A ∪ B et réciproquement tout élément z de A ∪ B appartient à A ou à B. Donc tout élément z de A ∪ B appartient à C (puisque z ∈ A ou B et que tout élément de A ou de B appartient à C) . Donc par définition de l’inclusion A ∪ B ⊂ C. Attention, nous ne sommes pas sûrs que tout élément de C appartient à A ou B. Cela peut être, mais cela peut aussi ne pas être. C’est pourquoi nous ne pouvons pas mettre une double implication, double implication qui signifierait que A ∪ B = C.

 

Remarquons bien que lorsqu’il s’agit d’un élément et d’un ensemble, la relation entre cet élément et cet ensemble est une relation d’appartenance.

Ainsi soit A = { a ; b }

Alors nous noterons a ∈ A et non pas : a ⊂ A. Parfois l’élément est mis entre parenthèses (mais pas entre accolades) et nous noterons alors : (a) ∈ A

 

Autres propositions qu’il est aisé de comprendre par pure intuition analytique :

6) A ∩ B ∩ C = A ∩ (B ∩ C) = (A ∩ B) ∩ C

7) A ∪ B ∪ C = A ∪ (B ∪ C) = (A ∪ B) ∪ C

8) A ∩ ( B ∪ C ) = (A ∩ B) ∪ (A ∩ C)

9) A ∪ ( B ∩ C ) = (A ∪ B) ∩ (A ∪ C)

 

b) Notion de produit cartésien d’ensembles finis

Prenons deux ensembles finis E et F.

Alors le produit cartésien de E et de F, noté E x F est l’ensemble des couples (x ; y) où x ∈ E et y ∈ F. Attention ici les constituants de chaque couple sont ordonnés, le premier appartient à E le deuxième appartient à F.

Nous pouvons prendre plus de deux ensembles, par exemple E x F x G. Nous obtenons un nouvel ensemble dans lequel les éléments sont formés d’abord d’un élément de E puis d’un élément de F puis d’un élément de G.

Reprenons l’exemple qui comprend deux ensembles finis, E et F.

Soit E = { a, b} et F = {1 ; 2}

Alors G = E x F = { (a ; 1) ; (a ; 2) ; (b ; 1) ; (b ; 2) }

Nous donnons en fichier joint une image de ce type d’opération, cette image consistant en l’établissement d’un tableau à double entrée.

Je pense que tu vas pouvoir reprendre tes cours en direct, la période de confinement étant arrivée à sa fin. J’espère que tu pourras reprendre tes conférences mais vu l’activité du virus cela risque d’être difficile.

 

Je t’embrasse.

 

 

Communication 2

 

26 septembre 2020

 

Samuel,

 

Chapitre 1 : Dénombrement, récurrence (suite)

b) Principe additif (dénombrement d’une union d’ensembles finis)

Soient A et B deux ensembles disjoints finis (pas d’éléments communs) et card A = m, card B = n

Alors card (A ∪ B) = card A + card B = m + n

Cette règle s’étend à une suite quelconque d’ensembles finis disjoints deux à deux.

Card (A U B U C U D …) = card A + card B + car C + card D …

 

Supposons que A et B ne soient pas disjoints, c’est-à-dire que A ∩ B = ∅, et que card A = m et card B = n.

Appelons A qui se lit : non A, l’ensemble qui ne comprend aucun élément de A. Visualisons ces ensembles dans le diagramme de Venn en fichier joint.

Alors A U B = A U A et card (A U B) = card (A U A) = card A + card A puisque A et A sont disjoints.

En analysant le diagramme de Venn nous voyons que card A = card B – card (A ∩ B)

Donc card (A U B) = card (A U A) = card A + card A = card A + card B – card (A ∩ B)

La formule générale de l’additivité est donc :

card (A U B) = card A + card B – card (A ∩ B)

 

Nous voyons que si A et B sont disjoints nous retrouvons bien la première formule :

card (A U B) = card A + card B car card (A ∩ B) est alors égal à 0.

 

 

c) Principe multiplicatif (dénombrement d’un produit cartésien d’ensembles finis)

 

Soient A et B deux ensembles finis, card A = m, card B = n.

Alors card (A x B) = mn

Cette formule peut s’étendre à une suite quelconque d’ensembles finis.

Soient A, B, C, D… une suite d’ensembles finis de cardinaux respectifs : a,b,c,d..

alors card (A x B x C x D…) = abcd…

 

d) Ensemble des k-uplets ou k-listes d’un ensemble fini E.

Nous pouvons imaginer le produit cartésien d’un ensemble fini E par lui-même. Ainsi E x E est-il l’ensemble des couples, ou encore des doublets, constituant ses éléments, dont le premier signe comme le deuxième appartiennent à E.

Nous notons E x E = E ², E x E x E = E³, E x E x E x E (k fois) = E^k.

Nous voyons ainsi que les éléments de l’ensemble E^k sont des k-uplets formés chacun de k signes ordonnés pris successivement dans E.

Si n est le cardinal de E alors le cardinal de E^k = n x n x n (k-fois) = n^k, ce qui signifie qu’il existe n^k éléments dans E^k , chaque élément étant formé de k signes ordonnés, pris chacun dans E.

On distingue dans les k-uplets, des doublets, des triplets, des quadruplets, des quintuplets, etc. (on appelle singleton l’élément d’un ensemble qui n’en comporte qu’un).

Si E a pour cardinal n, alors le nombre d’éléments (doublets) de E², sera égal à n², le nombre d’éléments (triplets) de E³ sera égal à n³, le nombre d’éléments (quadruplets) de E⁴ sera de n⁴, etc.

Pour construire les n^k éléments de E^k il est recommandé de passer par la construction d’un arbre (voir bas de la page 30 du livre maths-spécialités).

 

 

Exercices afférents au paragraphe 1) du chapitre ( les ensembles finis).

Les exercices afférents au principe additif sont le plus souvent construits de la même manière. Il est nécessaire d’utiliser un diagramme de Venn puis de représenter les ensembles mentionnés. Voir le modèle de la page 31, en haut de la page.

Les exercices afférents au principe multiplicatif comme au calcul des k-uplets ne présentent pas de difficultés majeures. Quand seulement deux ensembles sont mis en jeu il suffit d’utiliser un tableau à double entrée. Sinon recourir à l’écriture d’un arbre sur le modèle de la page 30 du livre précité.

 

Nous allons travailler sur l’exercice suivant (n° 79 de la page 43).

a) Démontrer que si A, B et C sont trois parties d’un ensemble fini E,

card (A U B U C) est égal à card A + card B + card C – card (A ∩ B) – card (A ∩ C) – card (B ∩ C) + card (A ∩ B ∩ C).

 

Nous allons appliquer les règles présentées dans la communication 1 en faisant remarquer que l’union et l’intersection sont commutatives. Ainsi A ∩ B ∩ C = A ∩ C ∩ B = B ∩ A ∩ C etc. Peu importe l’ordre des ensembles. Même règle pour l’union.

card (A U B U C) = [card A U (B U C)] = card A + card (B U C) – card [A ∩ (B U C)]

= card A + card B + card C – card (B ∩ C) – card [ (A∩ B) U (A ∩ C)]

= card A + card B + card C – card (B ∩ C) – [ card (A∩ B) + card (A ∩ C) – card (A∩ B) ∩ (A ∩ C)]

= card A + card B + card C – card (B ∩ C) – card (A∩ B) - card (A ∩ C) + card (A ∩ B ∩ A ∩ C)

= card A + card B + card C – card (B ∩ C) – card (A∩ B) - card (A ∩ C) + card (A ∩ B ∩ C)

car A ∩ B ∩ A ∩ C = A ∩ A ∩ B ∩ C = A ∩ B ∩ C [ A ∩ A = A]

C’est un peu abstrait mais c’est typique des raisonnements menés sur les ensembles.

 

Nous allons terminer cette étude des ensembles finis en étudiant la résolution de deux exercices. Au lieu d’utiliser un diagramme de Venn, nous utiliserons une autre méthode en recourant au modèle de Carroll. Ce modèle permet de résoudre certains problèmes de manière plus rapide que le recours au diagramme de Venn.

 

Ces exercices et ce modèle sont repris dans les fichiers joints.

 

 

Cette année scolaire promet d’être chargée. Mais elle t’introduit aux classes préparatoires scientifiques où le travail fourni sera intense.

Que tu puisses reprendre tes conférences au lycée est une bonne nouvelle. Je poursuivrais cette année les leçons en histoire générale, histoire des Judéens et histoire des Russes. Aborder le XVIII siècle sera une entreprise lourde. Le XVIII siècle annonce et fonde notre monde d’aujourd’hui.

 

Je t’embrasse,

 

 

 

 

Le 20/09/2020 à 17:28, Annalevine a dit :

Communication 1

20 septembre 2020

Samuel,

 

Chapitre 1 : Dénombrement, récurrence

Le premier chapitre de ton cours de maths-spécialité terminales traite des ensembles. La théorie des ensembles est une branche importante des mathématiques. Le mathématicien qui pensa cette théorie est Georg Cantor, né à Saint-Pétersbourg en 1845, d’un père industriel danois et d’une mère violoniste autrichienne. Georg qui fut lui-même un excellent violoniste, associa toute sa vie musique et mathématique. Pour lui les mathématiques étaient aussi un art : il était permis de penser tous nouveaux concepts pourvu qu’ils ne mènent à aucune contradiction logique.

Son père partit en Allemagne en 1856 le climat de la capitale de Pierre le Grand étant trop rigoureux pour sa santé. C’est ainsi que Cantor devint allemand. Il garda toujours la nostalgie de Saint-Pétersbourg.

En 1874 Cantor introduisit pour la première fois le concept de « nombre d’éléments d’un ensemble infini » concept qu’il nomma « puissance d’un ensemble infini » rebaptisé aujourd’hui « cardinal d’un ensemble infini». Ainsi lança-t-il la notion d’ensemble en l’associant à ses études sur l’infini.

Le choix du mot « cardinal » plutôt que celui de nombre d’éléments pour un ensemble infini revenait à se dégager de l’idée usuelle de nombre, concept toujours déterminé et fini dans son écriture, pour accéder à l’idée générale de nombre, au-delà de son écriture finie.

Ce faisant Cantor affirmait qu’il était possible d’atteindre par l’entendement le cardinal d’un ensemble infini ce qui était à l’époque considéré comme une hérésie. Seul Dieu avait le pouvoir de penser l’infini.

Depuis Aristote, il était convenu que l’infini ne pouvait jamais être atteint, qu’il ne pouvait qu’être approché. L’infini existait en puissance (en possibilité) mais pas en acte. Par exemple il était possible de commencer à compter à partir de 0 : 0-1-2-3-4 mais il n’était pas possible de terminer ce comptage, ce dénombrement. Il était possible de s’engager dans le dénombrement 0-1-2-3-4 … mais impossible de l’achever. L’infini existait en puissance, pas en acte. Cantor, en artiste qu’il était, imagina que cet impossible était possible, qu’il était possible d’atteindre l’infini en pensée, qu’il était possible de passer de la puissance à l’acte. Cette audace fonda l’un des monuments les plus imposants des mathématiques : la théorie des ensembles.

Dans les mathématiques courantes nous utilisons l’infini en puissance. Il est noté ∞.

Ainsi lorsque nous étudions la limite d’une somme d’une suite géométrique S_n de premier terme u₀ et de raison q, S_n = u_n (1 – qⁿ⁺¹) / (1- q) et que nous écrivons, quand 0 < q < 1

lim S_n = u₀ / (1 – q) [car qⁿ⁺¹ tend vers 0 quand n tend vers l’infini] )

n→∞

l’expression n→∞ signifie : n tend vers l’infini, mais il ne l’atteint pas ; nous raisonnons alors sur un infini en puissance, pas en acte.

 

1/ Les ensembles finis

Un ensemble fini est une collection d’un nombre fini d’éléments. En général nous étudions des éléments qui sont des nombres ou des lettres. Mais l’idée d’ensemble réfère à des éléments qui peuvent être n’importe quels objets. Notons bien que nous nous intéressons ici à des ensembles finis, non pas aux ensembles infinis, ces ensembles qui portèrent la pensée de Cantor.

Le cardinal d’un ensemble est son nombre d’éléments. Le titre de ce chapitre est : « dénombrement, récurrence ». Le dénombrement est la détermination du nombre d’éléments (le cardinal) d’un ensemble. Quand il s’agit d’un ensemble infini ce cardinal doit être, en tant que signe, écrit, inventé. Cantor pensa à la première lettre de l’alphabet hébreu, l’aleph, ℵ, pour désigner les cardinaux infinis. Comme il trouva qu’il existait différents cardinaux infinis, certains plus grands que d’autres, bien qu’ils fussent tous infinis, il les indiça pour les différencier.

Un ensemble est une donnée d’éléments non ordonnés. Ainsi l’ensemble E : {a ; b} formé de deux lettres, peut aussi s’écrire {b ; a} (les éléments sont séparés par un ; )

Notons que lorsqu’il s’agit de désigner la liste des éléments d’un ensemble nous devons encadrer cette liste par des accolades. Le choix des accolades signifie que nous parlons d’un ensemble.

Notons aussi qu’un ensemble est un concept différent de ses éléments. Ainsi l’ensemble des chevaux n’est pas lui-même un cheval (dixit un autre mathématicien de renom : Bertrand Russel).

Un ensemble ne contient pas de doublon. Tous les éléments sont différents. On ne peut donc pas parler de l’ensemble {a,b,a} mais de l’ensemble {a,b}.

On note ∅ et on appelle ensemble vide l’ensemble qui ne contient aucun élément. Cet ensemble est aussi noté : { } avec un vide à l’intérieur des deux accolades.

Soient E et F deux ensembles finis. L’inclusion de F dans E est notée ⊂ .

On écrira F ⊂ E (F inclus dans E) et l’on dira que F est un sous-ensemble de E ou encore que F est une partie de E pour signifier que tous les éléments de F sont contenus dans E et en sont des éléments.

La proposition F ⊂ E est donc synonyme de : ∀ x, ( x ∈ F) ⇒ ( x ∈ E)

Deux ensembles E et F sont égaux si E ⊂ F ET si F ⊂ E,

c’est à dire ∀ x, ( x ∈ F) ⇔ ( x ∈ E) [flèche double implication]

 

a) Notion d’union et d’intersection d’ensembles finis

Soient E et F deux ensembles finis. La réunion de E et de F est un unique ensemble. La réunion est notée : ∪

A = E ∪ F signifie : ∀ x ∈ A, x ∈ E ou x ∈ F.

L’intersection de E et de F est un unique ensemble. L’intersection est notée : ∩

A = E ∩ F signifie ∀ x ∈ A, x ∈ E et x ∈ F

Si E et F sont disjoints, c’est-à-dire s’ils n’ont aucun élément commun alors A = E ∩ F = ∅

 

Il est utile de pouvoir visualiser ces définitions. Visualiser, c’est recourir à la pensée spatiale, à ton imaginaire. La compréhension des mathématiques passe par deux modes de pensée. La pensée analytique, qui raisonne, qui progresse d’une étape du raisonnement à une autre étape, pensée qui est programmable (informatique). Cette pensée travaille sur de pures abstractions. Comme elle progresse d’une étape à une autre, il y a succession temporelle, c’est-à-dire qu’une étape en suit une autre, etc. Aussi cette pensée est qualifiée de temporelle ou de linéaire.

Il y a la pensée qui travaille avec l’imaginaire, c’est-à-dire qui travaille sur des images. Cette pensée ne passe pas par le raisonnement, elle est visionnaire. Cette pensée est qualifiée de spatiale. L’image donne un panorama dans son ensemble, dans le même instant, d’un événement mathématique même complexe. L’image est le plus souvent suscitée volontairement, mais parfois, plus rarement, l’image te vient sans intervention volontaire. Alors tu es inspiré, alors tu es le messager à qui une réalité que nul ne connaît te confie ses secrets. A charge pour toi, ensuite, de transmettre ce savoir qui t’est donné. Ce qui t’inspire parle certes à toi, mais cela parle aussi au monde par ton intermédiaire.

Dans le fichier joint l’image associée le plus souvent aux ensembles s’appelle diagramme de Venn. Il existe d’autres images dont je te parlerai.

 

Voici un addendum à l’étude des ensembles, hors programme terminales, mais parfois utile, même en terminales pour résoudre certains problèmes. Il est possible de comprendre ces propositions en t’appuyant sur ta seule intuition analytique. Il est nécessaire bien entendu de les démontrer, mais ce type de démonstration est du programme de première année de prépa ou de licence.

Voici cet addendum.

Propositions.

Soient quatre ensembles finis A, B, C, D. On a alors :

1) A ⊂ C et B ⊂ C ⇒ A ∪ B ⊂ C

2) A ⊂ B ⇒ A ∩ C ⊂ B ∩ C

3) A ⊂ B ⇒ A∪ C ⊂ B ∪ C

4) A ⊂ B et C ⊂ D ⇒ A∪ C ⊂ B ∪ D

5) A ⊂ B et C ⊂ D ⇒ A ∩ C ⊂ B ∩ D

Attention, il s’agit de simples implications. Les réciproques ne sont pas toujours vraies.

Du reste il n’est pas si compliqué que cela de démontrer ces propositions. Il suffit de recourir aux définitions.

Prenons par exemple la première proposition.

A ⊂ C et B ⊂ C ⇒ A ∪ B ⊂ C

Quelles sont les hypothèses ? (Toujours noter les hypothèses de départ pour démarrer le raisonnement, cette notation est le moment 1 du déroulé linéaire ou temporel du raisonnement).

Ces hypothèses sont les suivantes :

∀ x ∈ A, x ∈ C et ∀ y ∈ B, y ∈ C

Or A ∪ B est l’ensemble qui contient tous les éléments et seulement tous les éléments de A et de B. Donc ∀ x ∈ A et ∀ y ∈ B, x et y ∈ A ∪ B et réciproquement tout élément z de A ∪ B appartient à A ou à B. Donc tout élément z de A ∪ B appartient à C (puisque z ∈ A ou B et que tout élément de A ou de B appartient à C) . Donc par définition de l’inclusion A ∪ B ⊂ C. Attention, nous ne sommes pas sûrs que tout élément de C appartient à A ou B. Cela peut être, mais cela peut aussi ne pas être. C’est pourquoi nous ne pouvons pas mettre une double implication, double implication qui signifierait que A ∪ B = C.

 

Remarquons bien que lorsqu’il s’agit d’un élément et d’un ensemble, la relation entre cet élément et cet ensemble est une relation d’appartenance.

Ainsi soit A = { a ; b }

Alors nous noterons a ∈ A et non pas : a ⊂ A. Parfois l’élément est mis entre parenthèses (mais pas entre accolades) et nous noterons alors : (a) ∈ A

 

Autres propositions qu’il est aisé de comprendre par pure intuition analytique :

6) A ∩ B ∩ C = A ∩ (B ∩ C) = (A ∩ B) ∩ C

7) A ∪ B ∪ C = A ∪ (B ∪ C) = (A ∪ B) ∪ C

8) A ∩ ( B ∪ C ) = (A ∩ B) ∪ (A ∩ C)

9) A ∪ ( B ∩ C ) = (A ∪ B) ∩ (A ∪ C)

 

b) Notion de produit cartésien d’ensembles finis

Prenons deux ensembles finis E et F.

Alors le produit cartésien de E et de F, noté E x F est l’ensemble des couples (x ; y) où x ∈ E et y ∈ F. Attention ici les constituants de chaque couple sont ordonnés, le premier appartient à E le deuxième appartient à F.

Nous pouvons prendre plus de deux ensembles, par exemple E x F x G. Nous obtenons un nouvel ensemble dans lequel les éléments sont formés d’abord d’un élément de E puis d’un élément de F puis d’un élément de G.

Reprenons l’exemple qui comprend deux ensembles finis, E et F.

Soit E = { a, b} et F = {1 ; 2}

Alors G = E x F = { (a ; 1) ; (a ; 2) ; (b ; 1) ; (b ; 2) }

Nous donnons en fichier joint une image de ce type d’opération, cette image consistant en l’établissement d’un tableau à double entrée.

Je pense que tu vas pouvoir reprendre tes cours en direct, la période de confinement étant arrivée à sa fin. J’espère que tu pourras reprendre tes conférences mais vu l’activité du virus cela risque d’être difficile.

 

Je t’embrasse.

 

 

Bonjour Samuel, 

Je me permets juste d'être un peu plus précis concernant le travail de Cantor...

Être dénombrable ne signifie pas être comptabilisable ou pouvoir être compté en faisant des séries qui seraient inaccessibles en actes mais accessibles en pensées....

En réalité penser l'infini reste totalement hors de portée y compris par Cantor, toi, moi, ou Riemann...malgré la poésie russe de ton oncle

Etre dénombrable signifie simplement pouvoir être mis en relation bi univoque avec un nombre entier

Donc bien que les nombres entiers soient en nombre infini, par définition ils sont dénombrables puisque les denombrer revient à les mettre en relation avec eux-mêmes

C'est cet infini qui est baptisé Aleph zéro

En revanche, les nombres reels ne sont pas dénombrables et il est impossible de faire correspondre à tout nombre réel un nombre entier naturel

Un reel peut toujours s'ecrire en décimales...

Soit cette suite de decimales est finie, soit elle est infinie mais avec une séquence de chiffres qui se répète, soit elle est decimale avec une suite de chiffres infinis qui ne se repètent pas (souviens toi de pi mon enfant)

Les deux premières catégories sont associés à des nombres rationnels.

La dernière aux nombres irrationnels 

Cantor fait le tour de force de démontrer que les nombres rationnels sont parfaitement dénombrables, on peut les ranger, les ordonner et les numeroter, on peut les mettre en relation biunivoque avec les entiers

Donc Aleph 0 est le ... même infini pour les entiers naturels et les nombres  rationnels

Aleph est la première lettre de notre alphabet hébreu et est le symbole de l'infini dans ... la cabale

Mais....il est impossible de faire une relation biunivoque entre les entiers et les nombres réels...

Tous les infinis ne sont donc pas égaux 

Mais il démontre par exemple des choses contre intuitives

Par exemple...que le nombre de points dans un plan (une surface) peut se voir attribuer une relation biunivoque avec les points d'une droite unique 

"Je n'arrive pas a y croire" ecrivit il a Richard Dedekind

C'est ce dernier qui demontra que la théorie de Cantor était cohérente avec les mathématiques 

Retiens de l'infini cette citation de Levinas "le rapport avec l'infini ne peut certes pas se dire en terme d'expérience car l'infini déborde la pensée qui le pense"

On est loin des certitudes de tonton

Mais Cantor est cependant très fort

Et il démontre que le degré d'infinité des nombres reels est infiniment plus grand que celui des nombres entiers 

Il demontre que la taille de cet infini infiniment plus grand est précisément de 2 puissance aleph 0

Ou qu'en d'autres termes, que l'ensemble de tous les sous ensembles constituables dans Aleph possède exactement le même nombre d'éléments ad infinitum que l'ensemble des nombres reels

Essayant de mieux cerner le rapport entre ces deux infinis, il pose ce qu'on appelle l'hypothèse du continu, donc l'hypothèse que n'existeraient ni vide ni discontinuité entre les deux formes différentes d'infini (dénombrable vs indenombrable)

C'est Kurt Gödel qui a démontré que cette hypothèse est un indécidable de ZFC qui est la théorie la plus aboutie et cadre des mathématiques aujourd'hui 

Sache petit samuel que persecuté notamment par Kronecker, il sombra dans une froide depression et il mourut dans un hôpital psychiatrique en 1918

Gödel aussi mourru de sa folie

Je te recommande d'oublier les infinis et leur folie auquel tonton t'invite à des pensées absolues et d'aller embrasser la finitude de tes relations avec lui avant que nous ne tirions la révérence 

Bisous Samuel

 

@zenalpha

Tiens, il semblerait que le Roblochon accuse le Camembert de sentir mauvais.

Mais rassure-toi, cher Archange, en ce moment Roblochon subit ses ultimes crises de ménopause. 

il y a 5 minutes, azad2B a dit :

@zenalpha

Tiens, il semblerait que le Roblochon accuse le Camembert de sentir mauvais.

Mais rassure-toi, cher Archange, en ce moment Roblochon subit ses ultimes crises de ménopause. 

Venant d'un casgiù merzu, le vers est dans le verbe.

Communication 3

 

29 septembre 2020

 

Samuel,

 

Chapitre 1 : Dénombrement, récurrence (suite)

 

2/ Le raisonnement par récurrence

Le raisonnement par récurrence est utilisé pour démontrer qu’une proposition P(n), dépendant d’une variable n appartenant à l’ensemble des entiers naturels est vraie.

Une proposition P(x) est un énoncé mathématique qui dépend d’une variable x appartenant à n’importe quel ensemble de nombres. Nous notons P(n) une proposition qui dépend d’une variable n appartenant à l’ensemble ℕ.

 

Toute proposition dépendant d’une variable appartenant à un quelconque ensemble de nombres contient dans son libellé une propriété purement mathématique exprimée de diverses façons, égalité, inéquation, etc. et, en général, une présentation écrite, littéraire, qualifiée de « métamathématique ».

 

Par exemple la proposition P(n) ainsi libellée « la somme des n premiers carrés naturels est égale à [n(n+1)(2n+1)] / 6 » est un énoncé qui contient implicitement la propriété purement mathématique :

0² + 1² + 2² + … + n² = [n(n+1)(2n+1)] / 6, mais qui contient aussi un passage « littéraire » non formalisé en signes mathématiques purs : « la somme des n premiers carrés naturels est égale à », d’où le qualificatif de « métamathématique » donné à l’ensemble de la proposition.

 

Le raisonnement par récurrence s’applique exclusivement aux propositions mathématiques qui dépendent d’une variable prenant ses valeurs dans ℕ

 

Ce raisonnement est ainsi conduit.

Soit une proposition P(n) contenant une propriété mathématique donnée.

 

a) Initialisation

Nous cherchons le nombre le plus petit possible n₀ appartenant à ℕ vérifiant cette propriété. Si n₀ existe, P(n₀) est vraie.

 

b) Hérédité

Nous démontrons que si la proposition est vraie pour un quelconque entier naturel k plus grand ou égal à n₀ alors P(k+1) est vraie. L’expression « si P… alors Q », P et Q étant deux propositions, s’appelle « implication », notée ⇒ . P ⇒ Q

 

Nous posons P(k) vraie, décision appelée hypothèse de récurrence et nous démontrons en nous appuyant sur l’énoncé mathématique de la proposition P(k) et en effectuant un raisonnement assujetti aux règles de la mathématique que P(k+1) est vraie. Nous avons alors démontré l’hérédité de la propriété de la proposition P, car de proche en proche, cette propriété passe de P(k) à) P(k+1) puis à P(k+2) et cela jusqu’à l’infini. N’ayant en effet rien supposé quant à la valeur numérique de la lettre k, nous voyons qu’il suffit de prendre (k+ 1) = m par exemple puis de rééditer le raisonnement précédent pour m plutôt que pour k pour démontrer que P(m) vraie implique P(m+1) vraie soit P(m = k+1) vraie implique P(m + 1 = k+2) vraie. Nous pouvons ainsi raisonner de proche en proche, en partant de k, puis en passant à k + 1 puis à k + 2 etc. jusqu’à l’infini.

 

c) Nous pouvons maintenant conclure :

P(k) vraie impliquant P(k+1) vraie alors pour tout entier naturel n plus grand ou égal à n_{0 ,} P(n) est vraie.

 

Néanmoins il peut rester un doute. Nous avons démontré l’hérédité de P(n) en supposant que P(k) était vraie. Mais existe-t-il un k tel que P(k) soit vraie ? Oui pour k = n₀  P(k) est vraie. Donc de proche en proche à partir de n₀, en augmentant n₀ d’une unité, puis d’une autre unité, etc. la proposition finit par devenir vraie pour tout n plus grand ou égal à n₀ d’où l’impérative obligation d’initialiser la proposition.

 

Nous allons illustrer le raisonnement par récurrence avec deux exemples.

Premier exemple

Soit à démontrer la proposition P(n) suivante :

«La somme des n premiers carrés naturels est égale à [n(n+1)(2n+1)] / 6 »

Nous mathématisons tout de suite la proposition en la traduisant en termes purement mathématiques, soit : 0² + 1² + 2² + … + n² = [n(n+1)(2n+1)] / 6 

a) Initialisation

Essayons n = 0.

Le premier terme de l’égalité est alors égal à 0 ; et le deuxième terme est égal à 0.

Donc l’égalité est vraie pour n=0 ; P(0) est donc vraie.

b) Hérédité

Supposons P(k) vraie. Il faut tout de suite exprimer en termes mathématiques l’assertion P(k) vraie.

Nous écrivons donc :

P(k) vraie signifie que 0² + 1² + 2² + ….+ k² = [k(k+1)(2k+1]/6

Avant de continuer à travailler sur cette égalité il est recommandé de savoir où nous voulons en venir. Ici nous voulons en venir à cette égalité :

0² + … + k²2 + (k+1)² = [(k+1)(k+1+1)(2(k+1) + 1)]/6 = [(k+1)(k+2)(2k + 3)]/6

Savoir où nous voulons en venir permet de nous guider. Ce calcul doit être fait au brouillon plutôt qu’au propre.

Reprenons notre raisonnement.

Nous avons posé l’hypothèse de récurrence : 0² + 1² + 2² + ….+ k² = [k(k+1)(2k+1]/6

En ajoutant aux deux termes de l’égalité (k+1)² nous trouvons :

0² + ...+ (k+1)² = [k(k+1)(2k+1)]/6 + (k+1)² =[k(k+1)(2k+1)]/6 + 6(k+1)²/6

0² + ...+ (k+1)² = (k+1) [k(2k+1) + 6(k+1)]/6 =(k+1) [2k² + 7 k + 6]/6

 

Comme nous savons où nous voulons en venir il nous suffit de démontrer que

2k² + 7k+ 6 = (k+2)(2k+3)

Les racines de 2k²+ 7k +6 sont -2 et -3/2. Donc 2k² + 7k + 6 = 2(k+2)(k+3/2) = (k+2)(2k+3)

[Si l’équation ax² + bx + c = 0 admet deux racines distinctes x₁ et x₂ alors le polynôme

ax² + bx + c peut ainsi être factorisé : ax² + bx + c = a(x- x₁)(x -x₂)]

Et 0² + ...+ (k+1)² = (k+1) [2k² + 7 k + 6]/6 = [(k+1)(k+2)(2k+3)]/6

Ce qu’il fallait démontrer.

C) Conclusion

La proposition P(n) est vraie pour tout n appartenant à ℕ.

 

Deuxième exemple

Soit à démontrer la proposition suivante : 4ⁿ – 1 est divisible par 3 pour tout n ∈ ℕ.

Traduction en termes mathématiques : ∃ q ∈ ℕ tel que 4ⁿ – 1 = 3q.

 

a) Initialisation

Pour n = 0, 4ⁿ – 1 = 4⁰ – 1 = 1 – 1 = 0

0 est divisible par tout nombre donc divisible par 3. P(0) est donc vraie.

 

b) Hérédité

Hypothèse de récurrence : ∃ q ∈ ℕ tel que 4^k -1 = 3q.

Où voulons en venir ? ∃ t ∈ ℕ tel que 4^k+1 -1 = 3t.

Nous voyons que pour arriver à cette égalité nous devons multiplier les deux termes de l’égalité 4^k -1 = 3q par 4.

Soit 4(4^k -1) = 12q et 4^k+1 – 4 = 12q, soit 4^k+1 - 1 = 12q +3 = 3(4q + 1)

Donc 4^k+1 - 1 est bien un multiple de 3 puisqu’il existe t = 4q +1 tel que 4^k+1 - 1 = 3t.

 

c) Conclusion

La proposition est donc vraie pour tout n ∈ ℕ.

 

 

 

 

Je continuerai l’étude de la récurrence dans la prochaine communication.

 

Bon courage,

 

Je t’embrasse,

 

 

 

 

Communication 4

 

3 octobre 2020

 

Samuel,

 

Chapitre 1 : Dénombrement, récurrence (suite)

 

2/ Le raisonnement par récurrence (fin)

 

Il existe au programme deux autres récurrences, la récurrence forte et la double récurrence que tu peux étudier dans ton livre page 42.

 

Je traite ci-après de la manière de résoudre un problème de récurrence en illustrant cette manière par la résolution d’un exercice.

 

Soit (u_n) une suite définie pour u0 = 0 et pour tout entier naturel n, u n+1 = √ (0,5 u²n+ 8)

[La racine concerne (0,5 u²n+ 8)].

 

On note P(n) la propriété 0 ⩽ un ⩽ 8.

 

Démontrer la propriété.

 

1) Initialisation

 

Pour n = 0, u0 = 0 donc 0 ⩽ u0 ⩽ 8

P(0) vraie.

 

2) Hérédité

 

Posons P(k) vraie soit 0 ⩽ uk ⩽ 8.

0 ⩽ uk ⩽ 8 ⇒ 0 ⩽ u²k ⩽ 64 (car la fonction carré est croissante dans l’intervalle [0 ; + ∞ [)

⇒ 0 ⩽ 0,5 u²k ⩽ 32 ⇒ 8 ⩽ 0,5 u²k + 8 ⩽ 40

⇒ √ 8 ⩽ √ (0,5 u²k + 8) ⩽ √ 40

(car la fonction racine est croissante dans l’intervalle [0 ; + ∞ [ )

⇒ 0 ⩽ √ 8 ⩽ √ (0,5 u²k + 8) ⩽ √ 40 ⩽ 8

⇒ 0 ⩽ √ (0,5 u²k + 8) ⩽ 8 ⇒ 0 ⩽ u k+1 ⩽ 8

Donc 0 ⩽ uk ⩽ 8 ⇒ 0 ⩽ u k+1 ⩽ 8 et P(k+1) est vraie. CQFD.

 

3) Conclusion

 

P(n) est vraie pour tout n ⩾ 0.

 

Dans un tel exercice il faut repérer les fonctions en jeu et utiliser les définitions de la croissance ou de la décroissance des fonctions.

 

Bon courage !

 

Je t’embrasse,

 

Communication 5

 

11 octobre 2020

 

Samuel,

 

Chapitre 1 : Dénombrement, récurrence (fin)

 

3) Nombre de parties d’un ensemble

La notion de parties d’un ensemble est importante. Il est nécessaire de bien l’assimiler car elle est fréquemment employée dans le développement de la théorie des ensembles.

Soit un ensemble E = {a;b;c;d}

Les parties de cet ensemble sont elles-mêmes des ensembles constitués par les éléments de E, pris un par un, puis deux par deux, puis trois par trois, etc.

Ainsi les parties de l’ensemble E sont les sous-ensembles :

{a} ; {b}; {c} ; {d} ; {a;b} ; {a;c} ; {a;d} ; {b ;c} ; {b ;d} ;{c ;d} ; {a;b;c} ; {a ;b ;d} ; {a ;c ;d} ; {b ;c ;d}. On ajoute à ces sous-ensembles l’ensemble vide :∅, et l’ensemble E lui-même soit {a ;b ;c ;d}

On note :

P (E) = {∅ ;{a} ; {b}; {c} ; {d} ; {a;b} ; {a;c} ; {a;d} ; {b ;c} ; {b ;d} ;{c ;d} ; {a;b;c} ; {a ;b ;d} ; {a ;c ;d} ; {b ;c ;d} ; {a ;b ;c ;d}}

Bien noter que l’ensemble vide est représenté par un signe sans accolades.

Le nombre de parties d’un ensemble possédant n éléments est égal à : 2ⁿ

Cette proposition est démontrable par récurrence.

 

Rappelons maintenant que si F est un ensemble donné, de m éléments, alors un k-uplet d’éléments de E est une liste ordonnée d’éléments pris chacun dans E, puis dans E, puis dans E et cela k fois.

Cette liste ordonnée est donc construite à partir du produit cartésien E x E x...k-fois.

Notons une telle liste particulière ordonnée L(1). Alors L(1) comporte k éléments.

L’ensemble de ces listes est noté F^k. Cet ensemble construit avec des listes L(1), L(2), L(3) de chacune k éléments pris successivement à E puis à E, etc. comporte un nombre de listes égal à m^k

Card ( F^k ) = m^k

Soit un ensemble F comportant deux éléments. Alors le nombre de listes de k-uplets formées à partir de cet ensemble sera égal à 2^k

Nous constatons une relation entre le nombre des parties d’un ensemble et le nombre de listes de k-uplets formées à partir d’un ensemble comportant deux éléments. S’il s’agit de constituer des listes de n-uplets à partir de cet ensemble à deux éléments alors le nombre de parties d’un ensemble de n éléments sera égal au nombre de listes de n-uplets formées à partir de cet ensemble de deux éléments.

Cette égalité en nombre permet de faire correspondre à chaque élément de l’ensemble des parties d’un ensemble une liste de n-uplets construite à partir d’un ensemble à deux éléments (et réciproquement).

Reprenons notre exemple précédent.

P (E) = {∅ ;{a} ; {b}; {c} ; {d} ; {a;b} ; {a;c} ; {a;d} ; {b ;c} ; {b ;d} ;{c ;d} ; {a;b;c} ; {a ;b ;d} ; {a ;c ;d} ; {b ;c ;d} ; {a ;b ;c ;d}}

P (E) est formé à partir de l’ ensemble E = {a;b;c;d} comportant 4 éléments.

P (E) comporte 2⁴ éléments.

Formons les listes de 4-uplets d’un ensemble F = {0;1} comportant donc deux éléments.

Ces listes seront les suivantes :

(0,0,0,0) ; (0,0,0,1) ; (0,0,1,0);(0,0,1,1) ; (0,1,0,0) ; (0,1,0,1) ; (0,1,1, 0) ; (0,1,1,1) ;

(1,0,0,0) (1,0,0,1) (1,0,1,0) (1,0,1,1) (1,1,0,0) (1,1,0,1) (1,1,1,0) (1,1,1,1) [utiliser un arbre pour les constituer]

L’ensemble F⁴ des 4-uplets construits sur F comporte 2⁴ éléments.

Si nous affectons à chaque élément de E, a, b, c, d, un rang respectif : 1,2,3,4

Alors nous voyons qu’à chaque partie de l’ensemble P (E) nous pouvons faire correspondre une liste de l’ensemble F⁴ et réciproquement

Par exemple :

∅ ↔ (0,0,0,0)

{a} ↔ (1,0,0,0)

{a ;b} ↔ (1,1,0,0)

{a ;b ;c ;d} ↔ (1,1,1,1)

{b ;c ;d} ↔ (0,1,1,1)

Cette correspondance entre ces deux ensembles sera souvent employée plus tard dans l’étude de la théorie des ensembles. C’est certes un peu abstrait mais tout ce qui concerne les ensembles est en général abstrait.

Attention aux notations :

Si E = {x} alors x ∈ E, x ∈ {x} mais il ne faut pas écrire x = {x}

Si E = {x;y} alors P (E) = {∅ ;{x};{y};{x;y}}, alors {x} ∈ P (E), {x} ⊂ E et x ∈ E

Bon courage !

 

 

Le cours de logique mathématique de René Cori et de Daniel Lascar définit, dans son chapitre 1 (Calcul propositionnel) les formules propositionnelles.

Soit un ensemble P, non vide, fini ou infini, composé de variables propositionnelles, désignées par des lettres majuscules.

Si je passe trop rapidement sur cet incipit je ne manquerai de rencontrer pus tard quelques problèmes de compréhension.

Qu’est ce : une variable propositionnelle ? Cette question renvoie à cette autre question : qu’est-ce qu’une proposition mathématique ?

 

Prenons cette proposition mathématique : « tout nombre premier est impair » Nous voyons qu’elle est composée de deux parties : un sujet et un attribut. Il y a donc là un jugement si j’appelle jugement l’acte de relier deux concepts, deux notions entre elles. Et nous voyons ensuite qu’une proposition peut être vraie ou fausse. Une proposition mathématique ouvre donc sur des principes plutôt essentiels, puisqu’une proposition mathématique fait intervenir toujours, non seulement deux éléments de langage reliés le plus souvent par le verbe être, mais aussi les caractères vrai/faux.

 

A côté des variables propositionnelles il est défini cinq symboles de connecteur propositionnel, qui n’appartiennent pas à P, qui sont :

¬ , symbole de négation, ∨ symbole de disjonction ; ∧ symbole de conjonction, ⇒ symbole d’implication et ⇔ symbole d’équivalence.

Enfin il est défini les deux symboles suivants :

), parenthèse fermante, et (, parenthèse ouvrante (qui n’appartiennent pas à P).

 

Nous voici donc muni d’un alphabet :

A = P U {¬, ∨, ∧, ⇒ , ⇔ } U { ), ( }

 

Avec cet alphabet nous pouvons constituer des mots. Soit M (A) l’ensemble des mots constitués à partir de cet alphabet.

 

Première définition :

L’ensemble F des formules propositionnelles construites sur P est le plus petit sous ensemble de M (A) qui :

contient P

chaque fois qu’il contient un mot F contient ¬F

chaque fois qu’il contient des mots F et G contient aussi les mots (F∨ G), (F∧ G), (F ⇒ G) et (F ⇔ G)

 

Une formule propositionnelle est donc un mot construit à partir des éléments de P (chaque élément de cet ensemble étant aussi une formule propositionnelle de base), éléments ensuite combinés ensemble par l’emploi des connecteurs et des parenthèses selon les règles données ci-dessus.

 

Cette définition permet de distinguer les mots qui sont des formules propositionnelles de ceux qui n’en sont pas. Toutefois dans un premier temps cette distinction n’est pas évidente à faire. En fait à chaque fois qu’un mot est donné il faut s’assurer que le mot formé à partir de ce mot et des connecteurs est bien une formule propositionnelle.

 

Il est possible de définir autrement l’ensemble F .

 

Soit F ₀ = P

Puis F _n+1 = F _n U { ¬F ; F ∈ F _n } U { ( F α G) ; F,G ∈ F _n, α ∈ {∨, ∧, ⇒ , ⇔}}

 

Théorème = F = U F _n

 

Définition : la hauteur d’une formule F est le plus petit des entiers n tel que F ∈ F _n

Elle est notée : h[F]

 

Ainsi la hauteur de n’importe quelle variable propositionnelle est égale à 0 (puisque cette variable appartient à F ₀ )

h [((A ∨ B) ∧ ( B ⇒ A))] = 2 puisque (A ∨ B) appartient à F ₁ ainsi que (B ⇒ A) d’ailleurs, tandis que (A ∨ B) ∧ ( B ⇒ A) appartient à F ₂

Nous disposons maintenant de deux définitions de l’ensemble des formules propositionnelles, l’une appelée « par le haut », la première, l’autre appelée « par le bas », la seconde.

Si la seconde définition est directement accessible à la compréhension (il s’agit de construire étage après étage l’ensemble des formules par le procédé de la récurrence) la première est de prime abord assez difficile d’accès.

En effet poser comme définition par le haut que l’ensemble des formules propositionnelles est le plus petit sous-ensemble des mots possibles construits avec l’alphabet précité, qui contient P (l’ensemble des propositions mathématiques) et qui, à chaque fois qu’un mot fait partie de ce sous-ensemble, alors les mots construits avec les connecteurs propositionnels en font aussi partie, est loin d’être aisément compréhensible.

Cela me fait penser à la manière dont les nombres complexes sont introduits en première année de fac. On définit d’abord l’ensemble R² des couples (a,b) tels que a et b appartiennent à R. Puis on définit le corps des nombres complexes, C, comme étant l’ensemble R² muni d’une addition et d’une multiplication spécifiques. Enfin on définit le nombre complexe (0,1) et on l’appelle i. Ouf ! On retrouve le fameux nombre imaginaire i.

Il existe des étudiants qui croient que réellement il a existé un mathématicien qui, soudain, a sorti de son cerveau une telle définition. Alors que, lorsqu’on décide de comprendre cette définition obscure, on s’aperçoit qu’elle est le résultat de siècles de construction mentale, avec pour début les travaux d’un mathématicien italien du XVI siècle. Il y a donc une certaine entourloupe à faire croire que certaines définitions vont de soi. Si l’étudiant est naïf il est vite largué. S’il est roué, ou averti par son enseignant, il se fonde sur l’expression z = ai + b avec i² = -1. C’est pratique, commode et ça permet de voyager bien plus loin que ne peut le permettre la définition ampoulée fondée sur R².

Idem pour les définitions par le haut et par le bas. Il est nécessaire d’apprendre d’abord la définition par le bas, simple à comprendre, pour accéder à la compréhension de la définition par le haut qui est pour le moins contre-intuitive puisqu’elle est le résultat de phosphorations intenses et multiples. Dont l’étudiant devrait être instruit par l’enseignant. Cela dit cette définition par le haut est un petit bijou car elle introduit à des démonstrations dites par induction qui sont tout de même un chef-d’œuvre d’orfèvrerie mentale.

 

Supposons que nous voulions démontrer qu’une propriété P soit vérifiée par toute formule F appartenant à F . Nous pouvons adopter un raisonnement par récurrence, soit montrer que cette propriété est vérifiée pour F _{0 ,} puis supposer qu’elle est vraie pour F _n et démontrer qu’elle est alors vraie pour F _n+1

Mais il existe une autre démonstration dite démonstration par induction. Elle consiste d’abord à montrer que cette propriété est vérifiée pour F ₀ c’est-à-dire à démontrer que la propriété est vérifiée pour toute variable propositionnelle, puis à passer à l’étape dite d’induction qui consiste à prouver que, si une formule F satisfait la propriété, alors la formule ¬F la satisfait, et que si deux formules F et G la satisfont alors les formules (F∨ G), (F∧ G), (F ⇒ G) et (F ⇔ G) la satisfont aussi.

Dans ces conditions en effet, si F et G satisfont la propriété et que nous pouvons démontrer que ¬F, (F∨ G), (F∧ G), (F ⇒ G) et (F ⇔ G) la satisfont aussi, c’est toute la méthode de génération de l’ensemble des formules propositionnelles qui est ainsi reproduite. Le problème dans cette démonstration par induction c’est que nous partons de l’hypothèse que F et G satisfont la propriété. Et si elles ne vérifient pas la propriété ? Nous nous raccordons au fait que P, l’ensemble des variables propositionnelles vérifie la propriété. A partir de là nous générons de nouveaux mots qui satisfont la propriété, puis de proche en proche, par construction de ces nouveaux mots, nous étendons la propriété à l’ensemble des formules propositionnelles. Intuitivement ça passe, mais cela mériterait une démonstration, peut-être trop complexe car elle ne figure pas dans le cours de logique étudié.

Appliquons cette méthode à la proposition suivante : la hauteur d’une formule est toujours strictement inférieure à sa longueur. La longueur d’une formule est le nombre de « lettres » ou de signes de l’alphabet de base qu’elle comporte. Ainsi la longueur de (F ⇔ G) est 5. lg[F] = 5.La hauteur d’une formule F est le plus petit des entiers n tel que F ∈ F _{n .} Elle est notée : h[F]

La proposition à démontrer est donc notée : h[F] < lg[F]

Soit F une variable propositionnelle appartenant donc à P (ou à F ₀).

La hauteur de F est  : 0. Sa longueur est 1 puisque qu’il y a au moins un signe : F. Donc h[F] < lg[F].

La hauteur de ¬F est 1 et la longueur est 2. Donc h[F] < lg[F].

Si nous prenons une autre variable propositionnelle G, nous avons de même h[G] < lg[G]

(F∨ G) a pour longueur : 5 et pour hauteur 2. Idem pour les autres connecteurs propositionnels. Donc h[(F∨ G)] < lg[(F∨ G)] ainsi que pour les autres connecteurs. A partir des nouveaux mots constitués nous pouvons à nouveau démontrer cette proposition. Cette façon de procéder de proche en proche ressemble tout de même au raisonnement par récurrence sauf que nous n’avons pas besoin de passer par n (appartenant à N), nous n’avons pas besoin de passer par l’ensemble des entiers naturels.