Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 10-10-2019 23:34:30

Aethernalis
Invité

Recherche de magmas universels

Bonsoir,

Voici un exercice d'algèbre universelle qui me donne du fil à retordre, il s’agit de déterminer des magmas ayant des propriétés d’universalité fonctionnelles :

Soit B = [[0,n-1]]

Soit (B,*) un magma, on appellera formule bien formée de (B,*) toutes succession de symbole suivant les règles suivantes :

- Tout élément de B est une formule
- Si f et g sont des formules f*g est une formule

On notera φ(B²,*) l’ensemble des formules bien formés composées uniquement de 3 symboles distincts (au parenthésage près) : 2 éléments de B (que l’on notera « P et Q ») et la loi de composition interne (LCBI) « * ».

Par exemple P*(Q*P*P*(P*Q)*(P*Q)) ∈ φ(B²,*)

F(B²,B) désigne l’ensemble des fonctions de B² vers B.

Une LCBI « * » sur B est dite est dite fonctionnellement universelle (FU) ssi :
F(B²,B) ⊂ φ(B²,*)

C’est à dire que toute fonction a deux variables dans B qui renvoie un élément de B peut être écrite par une formule composée que de l’opérateur « * » et ces deux variables en question.

1. Trouver les tables de compositions des LCBI FU pour n = 2.
2. démontrer qu’il existe une telle LCBI pour n = 3.
3. Généraliser pour tout entier naturel n.
4. Donner l’allure de la table de composition de toutes les LCBI FU en fonction de n.


J’ai réussi à résoudre la question 1 facilement mais à partir de la 2 je bloque complètement...

merci d’avance pour votre aide !

#2 11-10-2019 20:39:19

Maenwe
Membre confirmé
Inscription : 06-09-2019
Messages : 409

Re : Recherche de magmas universels

Aethernalis a écrit :

Soit (B,*) un magma, on appellera formule bien formée de (B,*) toutes succession de symbole suivant les règles suivantes :

- Tout élément de B est une formule
- Si f et g sont des formules f*g est une formule

On notera φ(B²,*) l’ensemble des formules bien formés composées uniquement de 3 symboles distincts (au parenthésage près) : 2 éléments de B (que l’on notera « P et Q ») et la loi de composition interne (LCBI) « * ».

Bonjour,

J'ai du mal à comprendre vos définitions, notament celle de formule bien formée, qu'est ce qu'est donc cela ? Je veux dire par là que vous avez définis ce que sont les formules : ce sont les éléments de B. Mais vous n'avez pas défini ce qu'était une formule bien formée, à part quand vous dites "succession de symboles" or qu'est ce que c'est qu'un symbole et quel est son lien avec les éléments de B ?
Autre chose : la règle "- Si f et g sont des formules f*g est une formule" n'est pas très utile puisque f et g sont des éléments de B or B est un magma pour * donc par définition on a f*g est dans B. J'ai plus l'impression que cette définition est celle d'un magma et non d'une formule bien formée...

Pour la definition de φ(B²,*), pareil je n'ai pas compris. Pourquoi parler de 3 éléments puis après n'en que de 2 ? Une erreur de frappe ?
Ce qui me rend le plus perplexe c'est cette phrase : "2 éléments de B (que l’on notera « P et Q ») et la loi de composition interne (LCBI) « * »." Pouvez vous précisez son sens ?

Cordialement

Hors ligne

#3 12-10-2019 04:27:42

Aethernalis
Invité

Re : Recherche de magmas universels

Bonjour, tout d’abord merci de votre réponse,

Je vais clarifier les quelques points évoquées dans votre message :

Ce qu’en j’entends par formule, c’est simplement une suite de symboles quelconques, des espaces, des lettres, des parenthèses, etc. la formule est définie uniquement syntaxiquement comme telle.

Une formule est dite « bien formée » ssi elle répond aux règles suivantes :

1] les (symboles représentant les) éléments de B sont des formules bien formées
2] si f et g sont des formules bien formées, alors « f*g » est une formule bien formée (je rappelle que le symbole * représentera une loi de composition binaire interne entre les éléments de B)

Notez que deux formules différents peuvent avoir la même table de composition, par exemple : A*B sera une formule différente de A*A*B même si elles peuvent avec la même table de en composition en choisissant bien *. Deux formules distincts ayant la même table sont dite équivalentes, j’insiste sur le fait que deux formules peuvent être équivalentes et distincts.


Pour ce qui est de la définition des ensembles de formules que j’ai noté phi(B^2,*), il y a bien 3 symboles : le « P », le « Q » et le « * », (et aussi des possibilités de les parenthéser si Le parenthesage est valide), parmi ces trois symboles, les lettres représentent des variables de l’ensemble B et * est la loi de composition binaire interne, c’est à dire une fonction à deux variables de B qui renvoie une troisième variable dans B.

#4 12-10-2019 08:55:46

Maenwe
Membre confirmé
Inscription : 06-09-2019
Messages : 409

Re : Recherche de magmas universels

Bonjour,

Si j'ai bien compris, par exemple 2*5 est une formule bien formée (que l'on ne considère pas comme élément de B mais comme une suite de symbôle, les formules bien formée permettent donc d'étudier les différentes "representations" d'un même élément de B) ? (Pour $n\geq 6$) et on a égalité entre deux formules ssi ils ont les mêmes symbôles et dans le même ordre. (C'est une notion similaire à celle des "mots" en théorie des groupes non ?).

Et du coup φ(B²,*) est l'ensemble des fonctions à deux variables, définie sur B à valeur dans l'ensemble des formules (bien formées par définition de φ(B²,*)), et du coup vous identifiez chaques éléments de l'ensemble des formules bien formée à un élément de B (pour pouvoir avoir l'éventuelle inclusion : F(B²,B) ⊂ φ(B²,*)).

Ce qui veut dire qu'à moins que vous précisez que la loi est associative (ce que je ne pense pas que l'exercice fait car j'ai l'impression que l'on étudie les magmas en général, il y a un rapport directe avec la théorie des catégories j'ai l'impression, notamment à cause du mot universelle, et j'ai l'impression que l'on cherche une loi permettant de former un objet universel final... dans une certaine catégorie), il faut mettre des parenthèses lorsque l'on compose deux formules bien formée, au risque si l'on considère trois élément de B, a, b et c, a*b*c n'est pas de sens (en dehors de celui de formules) car on pourrait avoir $a*(b*c) \not = (a*b)*c $.
Ais je bien compris ce que vous vouliez dire ?

Dernière modification par Maenwe (12-10-2019 08:56:31)

Hors ligne

#5 12-10-2019 10:48:32

Aethernalis
Invité

Re : Recherche de magmas universels

Oui c’est ça, j’ajouterai pour être encore plus clair que l’inclusion F(B²,B) ⊂ φ(B²,*)) peut s’interpréter de la façon suivante :

Pour toute fonction f de B² dans B, il existe une formule φ  de φ(B²,*)) telle que quelque soit les valeurs de a et b (dans B), on a f(a,b) = φ(a,b) (ou l’on identifiera ici la formule comme sa valeur).

En termes plus simple, on peut dire que toute fonction f peut s’ecrire avec une formule de φ(B²,*)).

Par exemple :

si l'on donne à la loi « * » la table de composition suivante :

     A : 0 0 0 1 1 1 2 2 2
     B : 0 1 2 0 1 2 0 1 2
A* B : 0 0 1 2 1 1 1 0 2

Et si l’on pose une fonction f : B² -> B, définie par la table de composition suivantes :

       A : 0 0 0 1 1 1 2 2 2
       B : 0 1 2 0 1 2 0 1 2
f(A,B) : 0 0 0 1 1 1 0 1 2

Alors f peut être réécrite par la formule  : A*(A*B) 


De plus, Le parenthésage est en effet indispensable pour distinguer les formules car la loi n’es pas nécessairement associative.

Pour ce qui est du lien avec la théorie des catégories, je ne suis malheureusement pas assez familiarisé avec cette théorie pour pouvoir vous répondre mais je pensequ’io Est tout à fait possible que le problème puisse être étudié sous cet angle.

#6 12-10-2019 19:03:54

Maenwe
Membre confirmé
Inscription : 06-09-2019
Messages : 409

Re : Recherche de magmas universels

Bonsoir,

J'ai peut être une piste (que je n'ai pas encore dévellopé), on peut peut être essayer de construire une telle loi à partir d'une des lois que tu as trouvé dans le cas $n=2$. Ce qui me semble cohérent car lorsque l'on regarde la question 3, ils nous demandent de généraliser ce qui semble indiquer un raisonnement par récurrence  (on pourrait éventuellement essayer de combiner récurrence et raisonnement par l'absurde), mon idée est donc :

Étendre  $*_{n} $ (qui est une loi qui fonctionne par hypothèse de récurrence pour  $B_{n} $) en une loi $*_{n+1} $ qui fonctionne, on a déjà : $B_{n}^{2} \subset  B_{n}^{2} $ (avec $B_{n} = [|0, n-1|] $) ce qui limite déjà  grandement nos choix de tables pour $*_{n+1} $

On peut déjà commencer avec $n=3$ et voir quelle est la manière la plus efficace d'étendre  $*_{2} $ à  $*_{3} $...

Dernière modification par Maenwe (12-10-2019 19:06:24)

Hors ligne

Pied de page des forums