Avec le début des cours, ce blog reprendra vie...
Etudiants du master Linguistique Théorique et Descriptive (parcours Linguistique Formelle et Théorique) et... les autres, ceux que cela intéresse, je vous invite donc à y venir de temps en temps, et à y déposer éventuellement des commantaires (questions, remarques). Je laisse ici les billets de l'an dernier (le plus récent étant le premier à l'écran) car j'aurai l'occasion d'y faire référence à nouveau.
Bonnes cogitations.
vendredi 15 octobre 2010
dimanche 8 novembre 2009
L'homme au chapeau
La logique « classique » a parfois d’amusantes conséquences….
Supposez que je dise devant une assemblée d’hommes : « s’il y a un homme ici qui a un chapeau, alors tout le monde a un chapeau ! ». On s’attend à ce que cette phrase signifie quelque chose comme « il y a un homme dont c’est tellement peu l’habitude qu’il porte un chapeau que, si même lui en porte un, alors… tout le monde en porte un ! » et on s’attend à ce que, face à une mise en doute de ma phrase, je désigne cette personne. Or, cette phrase est trivialement vraie !
Pourquoi ?
mercredi 4 novembre 2009
Marx et maths
Quel rapport entre Marx et la théorie des ordinaux finis? je propose celui-ci:
Dans « Le Capital », livre 1, chapitre premier (chapitre sur la marchandise), K. Marx explique la genèse théorique de la forme valeur des biens produits par les hommes. Les biens en certaines quantités entrent en équivalence les uns avec les autres par le biais de l’échange. Par exemple, dans une économie de troc, on en vient à admettre que 20 mètres de toile peuvent s’échanger contre un habit. On a une équation : « 20 mètres de toile = un habit », le terme de gauche est dit être la forme relative de la valeur et le terme de droite la forme équivalent. On peut aussi avoir en généralisant :
Un habit =
10 livres de thé =
40 livres de café =
2 onces d’or = 20 mètres de toile
½ tonne de fer =
X marchandise A
Etc
Toutes les marchandises expriment maintenant leurs valeurs d’une manière simple, parce qu’elles l’expriment dans une seule espèce de marchandise et avec ensemble parce qu’elles l’expriment dans la même espèce de marchandise. Ceci dit, le choix des mètres de toile était arbitraire, on pourrait tout aussi bien avoir :
Un habit =
10 livres de thé =
20 mètres de toile =
2 onces d’or = 40 livres de café
½ tonne de fer =
X marchandise A
Etc
Il vient donc un moment où un type de marchandise est choisi pour incarner cette forme équivalent de la valeur, et du même coup, exclue par les autres. Cette marchandise spéciale est par exemple l’or. La forme simple de la marchandise est ainsi le germe de la forme argent.
On peut mettre ce chapitre en parallèle avec la genèse du nombre telle que proposée par les logiciens du début du XXème siècle, Frege et Russell. Les quantités de marchandises sont remplacées par les ensembles. L’échange est remplacé par l’équipotence (existence d’une bijection entre ensembles). Deux quantités de marchandises différentes équivalentes, cela devient : deux ensembles équipotents (ayant « le même nombre d’éléments »). On en vient à chercher là aussi des ensembles spéciaux, qui vont servir à l’expression de la forme « cardinalité » de chaque ensemble. Ces ensembles spéciaux sont les ordinaux.
Un ensemble de trois fleurs =
Un ensemble de trois images =
Un ensemble de trois personnes = l’ensemble {0, {0}, {0, {0}}}
Un ensemble de trois arbres =
Un ensemble de trois livres =
vendredi 30 octobre 2009
Du fini à l'infini
Georg Cantor, 1845 - 1918
En cours, lundi dernier, nous avons parlé des ensembles ordinaux, qui servent « à compter ». Il ne s’agissait que d’ordinaux finis. Par exemple, les ensembles suivants sont des ordinaux finis :
J’ai dit ensuite que chaque classe d’équipotence (classe pour la relation qui existe entre deux ensembles A et B quand ils sont en bijection – one to one) avait « son » ordinal. Evidemment, cela marche bien pour les ensembles finis. Mais que se passe-t-il quand nous atteignons les marécages de l’infini ?
Noter que l’infini existe… mais sous quelle forme ? Il y a des ensembles bizarres, prenez N, l’ensemble des entiers naturels, par exemple, prenez P, l’ensemble des nombres pairs, P est strictement inclus dans N et pourtant… il existe une bijection entre P et N ! Donc, littéralement : P et N ont le même « nombre d’éléments » ! C’est cela justement qui caractérise l’infini, par quoi on peut définir l’infini. N, Z, Q sont trois ensembles différents, chacun strictement inclus dans le suivant, et pourtant ils sont tous les trois en bijection, donc ont le même nombre d’éléments !
Généralisons donc la définition de la notion d’ordinal : on dit qu’un ensemble alpha est un ordinal s’il a les deux propriétés suivantes :
1) La relation
est sur alpha une relation d’ordre total strict qui est un bon ordre ;
2)
(Dire qu’un ordre sur alpha est un « bon » ordre, c’est dire que tout sous-ensemble non vide de alpha possède un élément minimum, mais nous n’attacherons pas trop d’importance ici à ce « détail »).
On voit que « curieusement » dès qu’on a un ensemble « initial » d’ordinaux (c’est-à-dire un ensemble d’ordinaux commençant par le plus petit d’entre eux et qui se suivent)... on a un nouvel ordinal : cet ensemble justement ! et ainsi de suite. On peut voir aussi sur cet exemple que si alpha est un ordinal, alors alpha U {alpha} est un ordinal. On note alors ce nouvel ordinal : alpha+1, c’est le successeur de alpha.
Un ordinal est dit fini si lui-même et chacun de ses éléments est successeur d’un ordinal. Dans le cas contraire, on parle d’ordinal limite. Or, si nous considérons l’ensemble de tous les ordinaux finis, on peut démontrer assez facilement qu’il s’agit aussi d’un ordinal, mais on ne peut pas trouver d’ordinal dont il soit le successeur ! autrement dit c’est un ordinal limite.
Notons-le
. On peut montrer que tout ordinal inférieur à cet est un ordinal fini, donc est « le plus petit des ordinaux finis ». Mais on peut évidemment noter que le procédé qui nous a permis d’obtenir un ordinal à partir d’un autre par l’opération de « successeur » s’applique toujours ! U {} a évidemment un sens, et c'est un ordinal distinct de . Donc + 1 est un autre ordinal infini, mais distinct du précédent (puisque c’est son successeur) et ainsi de suite. On engendre ainsi la suite :
est encore un ordinal et ainsi de suite ! Cantor avait bien vu qu’à partir du moment où on ouvrait la porte à un infini actuel, c’est toute une myriade d’infinis qui s’engouffrent, qu’il appelait les ordinaux transfinis.
Etablissons maintenant un lien avec les cardinaux. Les ordinaux et les cardinaux coïncident dans le cas fini, c’est acquis, mais considérons par exemple et + 1 : ce sont deux ordinaux différents et pourtant ils ont le même cardinal car on peut construire une bijection entre les deux. Associons à 0, l’élément rajouté à , qui n’est autre que {}, à 1 associons 0, etc. à n > 1 associons n-1 et ainsi de suite, cette application existe et est réversible, donc c’est une bijection. On a ainsi trouvé deux ordinaux pour une même classe d’équipotence, mais bien sûr on peut en trouver une infinité. La bonne nouvelle néanmoins est que cet ensemble d’ordinaux possède un plus petit élément, donc nous pouvons corriger notre affirmation initiale en disant que pour chaque classe d’équipotence, il existe un plus petit ordinal en bijection avec tous les éléments de la classe, c’est lui qu’on retient pour désigner le nombre associé à la classe.
Ceci dit… par quoi l’existence de ce plus petit élément est-elle garantie ?
Cela n’est pas évident et en réalité va découler … d’un axiome, le fameux axiome du choix !
J’ai dit ensuite que chaque classe d’équipotence (classe pour la relation qui existe entre deux ensembles A et B quand ils sont en bijection – one to one) avait « son » ordinal. Evidemment, cela marche bien pour les ensembles finis. Mais que se passe-t-il quand nous atteignons les marécages de l’infini ?
Noter que l’infini existe… mais sous quelle forme ? Il y a des ensembles bizarres, prenez N, l’ensemble des entiers naturels, par exemple, prenez P, l’ensemble des nombres pairs, P est strictement inclus dans N et pourtant… il existe une bijection entre P et N ! Donc, littéralement : P et N ont le même « nombre d’éléments » ! C’est cela justement qui caractérise l’infini, par quoi on peut définir l’infini. N, Z, Q sont trois ensembles différents, chacun strictement inclus dans le suivant, et pourtant ils sont tous les trois en bijection, donc ont le même nombre d’éléments !
Généralisons donc la définition de la notion d’ordinal : on dit qu’un ensemble alpha est un ordinal s’il a les deux propriétés suivantes :
1) La relation
est sur alpha une relation d’ordre total strict qui est un bon ordre ;2)
(Dire qu’un ordre sur alpha est un « bon » ordre, c’est dire que tout sous-ensemble non vide de alpha possède un élément minimum, mais nous n’attacherons pas trop d’importance ici à ce « détail »).
On voit que « curieusement » dès qu’on a un ensemble « initial » d’ordinaux (c’est-à-dire un ensemble d’ordinaux commençant par le plus petit d’entre eux et qui se suivent)... on a un nouvel ordinal : cet ensemble justement ! et ainsi de suite. On peut voir aussi sur cet exemple que si alpha est un ordinal, alors alpha U {alpha} est un ordinal. On note alors ce nouvel ordinal : alpha+1, c’est le successeur de alpha.
Un ordinal est dit fini si lui-même et chacun de ses éléments est successeur d’un ordinal. Dans le cas contraire, on parle d’ordinal limite. Or, si nous considérons l’ensemble de tous les ordinaux finis, on peut démontrer assez facilement qu’il s’agit aussi d’un ordinal, mais on ne peut pas trouver d’ordinal dont il soit le successeur ! autrement dit c’est un ordinal limite.
Notons-le
. On peut montrer que tout ordinal inférieur à cet est un ordinal fini, donc est « le plus petit des ordinaux finis ». Mais on peut évidemment noter que le procédé qui nous a permis d’obtenir un ordinal à partir d’un autre par l’opération de « successeur » s’applique toujours ! U {} a évidemment un sens, et c'est un ordinal distinct de . Donc + 1 est un autre ordinal infini, mais distinct du précédent (puisque c’est son successeur) et ainsi de suite. On engendre ainsi la suite :
est encore un ordinal et ainsi de suite ! Cantor avait bien vu qu’à partir du moment où on ouvrait la porte à un infini actuel, c’est toute une myriade d’infinis qui s’engouffrent, qu’il appelait les ordinaux transfinis.
Etablissons maintenant un lien avec les cardinaux. Les ordinaux et les cardinaux coïncident dans le cas fini, c’est acquis, mais considérons par exemple
et + 1 : ce sont deux ordinaux différents et pourtant ils ont le même cardinal car on peut construire une bijection entre les deux. Associons à 0, l’élément rajouté à , qui n’est autre que {}, à 1 associons 0, etc. à n > 1 associons n-1 et ainsi de suite, cette application existe et est réversible, donc c’est une bijection. On a ainsi trouvé deux ordinaux pour une même classe d’équipotence, mais bien sûr on peut en trouver une infinité. La bonne nouvelle néanmoins est que cet ensemble d’ordinaux possède un plus petit élément, donc nous pouvons corriger notre affirmation initiale en disant que pour chaque classe d’équipotence, il existe un plus petit ordinal en bijection avec tous les éléments de la classe, c’est lui qu’on retient pour désigner le nombre associé à la classe.Ceci dit… par quoi l’existence de ce plus petit élément est-elle garantie ?
Cela n’est pas évident et en réalité va découler … d’un axiome, le fameux axiome du choix !
vendredi 23 octobre 2009
La réponse
Si "voyelle" est apparent, alors (voy => pair) n'est vrai que si "pair" est au dos. Il faut donc retourner la carte "voyelle".
Si "consonne" est apparent (autrement dit si "voyelle" est faux), que le chiffre soit pair ou impair, la table de vérité dit que dans tous les cas, (voy => pair) est vrai, donc inutile de retourner la carte.
Si "pair" est apparent ("pair" vrai), alors idem: que la carte au dos soit une voyelle ou une consonne, la table de vérité dit que dans tous les cas, (voy => pair) est vrai, donc inutile de retourner la carte.
Si "impair" est apparent ("pair" faux), alors (voy => pair) n'est vrai que si "voyelle " est faux, autrement dit s'il y a une consonne au dos de la carte. Il faut donc aussi retourner la carte "impair".
Il faut donc retourner A et 9.
Un fort pourcentage de gens répondent faussement à ce test (autour de 80%) alors même qu'ils ont atteint le stade dit "des opérations formelles", selon la terminologie de Piaget. Le psychologue Olivier Houdé explique cela en disant que dans ce genre de tâche, le sujet est fortement enclin à répondre selon ce que lui dictent les aires visuo-perceptuelles du cerveau plutôt que le cortex frontal où se trouve le siège de la logique. Autrement dit, il explique cela par un "manque d'inhibition".
Si "consonne" est apparent (autrement dit si "voyelle" est faux), que le chiffre soit pair ou impair, la table de vérité dit que dans tous les cas, (voy => pair) est vrai, donc inutile de retourner la carte.
Si "pair" est apparent ("pair" vrai), alors idem: que la carte au dos soit une voyelle ou une consonne, la table de vérité dit que dans tous les cas, (voy => pair) est vrai, donc inutile de retourner la carte.
Si "impair" est apparent ("pair" faux), alors (voy => pair) n'est vrai que si "voyelle " est faux, autrement dit s'il y a une consonne au dos de la carte. Il faut donc aussi retourner la carte "impair".
Il faut donc retourner A et 9.
Un fort pourcentage de gens répondent faussement à ce test (autour de 80%) alors même qu'ils ont atteint le stade dit "des opérations formelles", selon la terminologie de Piaget. Le psychologue Olivier Houdé explique cela en disant que dans ce genre de tâche, le sujet est fortement enclin à répondre selon ce que lui dictent les aires visuo-perceptuelles du cerveau plutôt que le cortex frontal où se trouve le siège de la logique. Autrement dit, il explique cela par un "manque d'inhibition".
Connaissez-vous le test de Wason?
Ce test donne une illustration de la table de vérité du "si... alors". Le voilà: on dispose 4 cartes, avec pour chacune une lettre d'un côté et un chiffre de l'autre. Evidemment, on ne voit que l'un des deux : on n'a accès qu'à la face visible de chaque carte. La question est : "est-il vrai qu'au dos de chaque carte montrant une voyelle, il y a un chiffre pair?". Vous avez devant vous : A, S, 4, 9. Vous avez deux cartes à retourner, pas une de plus, pas une de moins. Lesquelles retournez-vous?
jeudi 15 octobre 2009
Turing
En cours de master, ce lundi, j'ai évoqué l'oeuvre et la vie (et la mort) d'Alan Turing, probablement l'un des plus grands génies du XXème siècle, à qui notre monde doit l'invention de l'informatique et le décryptage des codes secrets utilisés par les Nazis pendant la seconde guerre mondiale. On lui doit également des idées révolutionnaires sur les mécanismes de la vie (dont des biologistes commencent seulement à s'inspirer) et l'idée même d'"Intelligence Artificielle". Il se trouve que le journal "Le Monde" d'aujourd'hui (14/10) lui consacre une pleine page à l'occasion des excuses que Gordon Brown lui a adressées à titre posthume, concernant la manière odieuse dont il a été traité par son pays dans les années cinquante (et qui l'a acculé au suicide). Bonne lecture.
PS: il existe une BD, probablement introuvable aujourd'hui, de Goffin et Peeters (qui date de 1992) sur Turing, intitulée: "Le Théorème de Morcom". Turing y apparaît sous le nom de Julius Morcom.
PS: il existe une BD, probablement introuvable aujourd'hui, de Goffin et Peeters (qui date de 1992) sur Turing, intitulée: "Le Théorème de Morcom". Turing y apparaît sous le nom de Julius Morcom.
Inscription à :
Articles (Atom)