Un petit résultat d'existence assez étonnant

EtNonLesShills
Modifié (June 2023) dans Shtam
Un résultat élémentaire mais étonnant au vu du manque d'hypothése demandée.
Peut-être certaines personnes plus érudites que moi en maths pourront le relier à une théorie déjà existante plus générale.
Soit f : E x {0;1} -> E x {0;1} bijective avec E fini.
Soient s0 : E x {0;1} -> E x {0;1} (x,b) -> (x,0); s1: E x {0;1} -> E x {0;1}  (x,b) -> (x,1).  Soit S= {s0, s1}.
Soient n dans IN et A dans S^n on définit récursivement f <- A = f o A_n o f<- A|n-1, ou A|n-1 désigne A restreint à ses n-1 premières coordonnées (et bien sûr initialisation f<- A =  f o A_1 si A n'est composé que d'un élément).
Alors il existe A dans S^IN  et x dans E tq pour tout n f<-A|n (x,0) ait pour deuxième coordonnée 0.

Réponses

  • [Utilisateur supprimé]
    Modifié (June 2023)
    Tu aurais un ou des exemples ?
    On comprendrais un peu mieux le sens de tes notations.
  • EtNonLesShills
    Modifié (June 2023)
    Prenons un  automate cellulaire réversible fini où chaque cellule a deux états 0 et 1. Focalisons nous sur une cellule en particulier C. Alors il existe un état de départ où en réitérant le procédé de changer C d'état si je le souhaite ou non puis d'appliquer la règle d'évolution de l'automate, C a pour valeur 0 et cela reste vrai en réiterant un nombre infini de fois.
  • lourrran
    Modifié (June 2023)
    Je recopie le message initial de EtNonLesShills en mettant des symbole dollars là où il faut, peut-être que ce sera plus lisible ?

    Soit $f$ : $E \times \{0;1\} \rightarrow E \times \{0;1\}$ bijective avec $E$ fini.
    Soit $s_0$ : $E \times \{0;1\} \rightarrow  E \times \{0;1\} (x,b) \rightarrow (x,0)$;
    Soit $s_1$ : $E \times \{0;1\} \rightarrow  E \times \{0;1\} (x,b) \rightarrow (x,1)$;
    Soit  $S= \{s_0, s_1\}$.
    Soit $n \in \mathbb{N} $ et $A \in S^n$ ; on definit recursivement $f<- A = f o A_n o f<- A|n-1$, ou $A|n-1$ désigne $A$ restreint à ses $n-1$ premiers termes (et bien sur initialisation $f<- A =  f o A_1$ si $A$ n'est compose que d'un element).

    Alors  $ \exists A \in  S^{\mathbb{N}}$  et $x \in E$ tq pour tout $n$ $f<-A|n (x,0)$ ait pour deuxième coordonnée $0$.

    Reste à comprendre l'avant-dernier paragraphe.
    Et ça me gêne un peu d'avoir un dernier paragraphe qui commence par $ \exists A $, alors qu'on avait déjà un $A$ auparavant.

    Edit : édité suite à la remarque de Exxx
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • EtNonLesShills
    Modifié (June 2023)
    c'est sympa mais la dernière ligne c'est il existe A appartenant à S^ lN pas S^n :)

    et le A avant appartient juste à la définition de f<- A, le A dans le dernier paragraphe je ne sais pas comment le dire mais voilà quoi y a pas de problème, enfin je crois

    edit : j'ai aussi changé terme pas coordonnées je pense que c'est le "terme" approprié.
  • J'avais bien vu, mais comme je ne voyais vraiment pas le sens que ça peut avoir, j'avais rectifié.
    Ca reste du chinois pour moi. 
    Mais le paragraphe précédent est encore plus incompréhensible. 



    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • EtNonLesShills
    Modifié (June 2023)
    je vais essayer de le dire plus explicitement avec un exemple 

    si A = (s_0, s_0, s_1, s_0, s-1)

    F<-A = f o s_1 o f o s_0 o f o s_1 o f o s_0 o f o s_0

    et par exemple
    F<- A|2 = F <- (s0, s0) = f o s_0 o f o s_0

    pour bien formaliser ca on fait une definition recursive
  • gerard0
    Modifié (June 2023)
    Bonjour.
    Tu utilises des notations qui sont incompréhensibles sur un forum de maths. Peux-tu expliquer ce que veut dire "F<-A" ? Pour un matheux, c'est dire que F est strictement inférieur à -A, qui n'a pas de sens dans ce contexte. Au pire, on pourrait penser à une affectation ($F\leftarrow A$), mais le = qui suit détruit cette signification.
    Pour être lu, il faut être compris, donc écrire de façon compréhensible pour les lecteurs. Il y a dans ce sous-forum un bon nombre de messages dont les auteurs refusent de faire l'effort d'être compris, se croyant au dessus de cette élémentaire politesse, ou incapable de préciser ce qu'ils ont en tête; ne fais pas partie de cette cohorte, merci !
  • J'ai retranscrit  <- avec les 2 symboles < suivi de -, et ça semblait convenir à notre ami. 
    Mais effectivement, de là à en déduire que < se traduit par 'strictement inférieur', il reste un grand pas à franchir.

    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Bibix
    Modifié (June 2023)
    Je pense avoir compris, et je trouve que la notation $f <- A$ n'est pas non plus horrible. Vu les objets en jeu, il n'y a pas de risque de confusion. Par contre, le résultat n'est pas étonnant si $f$ est surjective.
    Cela reste vrai si $E$ est un ensemble quelconque (possiblement infini) et $E \times \{0\} \subset f(E \times \{0,1\})$ (avec $f$ possiblement non surjective).
  • gerard0
    Modifié (June 2023)
    Désolé, moi je ne comprends pas ! Il n'y a pas de risque de confusion, puisque le symbole<$ n'est pas utilisé de façon traditionnelle.
    Je n'ai même pas compris quel est le nom de l'objet défini récursivement !! En général, quand on dit "on définit récursivement" c'est suivi du nom de ce qu'on définit, or ici c'est "on définit récursivement f...." et f n'a pas à être défini puisqu'il est donné au départ.
    Mais si tu as compris, rien ne t'interdit de dire ce que tu as compris en termes cohérents. On verra si Enonlesshills reconnaît son idée.
    Cordialement.
  • Bibix
    Modifié (June 2023)
    Voilà ce que j'ai compris : 
    On définit récursivement pour $A \in S^{\mathbb{N}}$ la fonction $(f\leftarrow A \mid_{n}) = f \circ A_n \circ (f\leftarrow A \mid_{n-1})$ si $n \geqslant 2$, avec l'initialisation $(f\leftarrow A \mid_{1}) = f \circ A_1$.
    On peut construire pour $A \in S^n$ et $n \in \N^*$ $f \leftarrow A = f \leftarrow A^* \mid_n$ où $A^* \in S^{\mathbb{N}}$ prolonge naturellement $A$.

    On obtient alors qu'il existe $\hat{A} \in S^{\mathbb{N}}$ et $x \in E$ tel que $\forall n \in \N^*, \exists y \in E, \, (f\leftarrow \hat{A}\mid_n)(x,0) = (y,0)$. Je trouve ça évident vu les hypothèses sur $f$.
  • gerard0
    Modifié (June 2023)
    Désolé,
    je ne comprends toujours pas ce que signifie cette notation $(f\leftarrow A \mid_{n})$. Je suis un peu obtus, mais je sais définir une fonction par le triplet (ensemble de départ, ensemble d'arrivée, graphe). ici, je en vois aucun de ces trois termes. Et $A_n$ n'est pas défini.
    Cordialement.
  • EtNonLesShills
    Modifié (June 2023)
    Bibix a dit :
    Je pense avoir compris, et je trouve que la notation $f <- A$ n'est pas non plus horrible. Vu les objets en jeu, il n'y a pas de risque de confusion. Par contre, le résultat n'est pas étonnant si $f$ est surjective.
    Cela reste vrai si $E$ est un ensemble quelconque (possiblement infini) et $E \times \{0\} \subset f(E \times \{0,1\})$ (avec $f$ possiblement non surjective).
    pas tout à fait vrai mais pas loin, si on n'a pas l'hypothèse de finitude on a le résultat sur S^n pour n arbitrairement grand avec ton hypothèse mais S^lN lui nécessite la finitude pour étendre il me semble (n'hésite pas à me corriger si je me goure).
    C'est vrai que c'est plutôt trivial mais de base c'est assez contre intuitif je trouve qu'il existe un élément aussi "stable" alors qu'on suppose pas grand chose ^^. On peut bien sûr prendre autre chose que {0;1} pour l'ensemble produit, je ne sais pas pourquoi je me suis limité à ça. gerard0 a dit :
    Désolé,
    je ne comprends toujours pas ce que signifie cette notation $(f\leftarrow A \mid_{n})$. Je suis un peu obtus, mais je sais définir une fonction par le triplet (ensemble de départ, ensemble d'arrivée, graphe). ici, je en vois aucun de ces trois termes. Et $A_n$ n'est pas défini.
    Cordialement.
    le concept définit par récursion est f <- A, la récursion porte sur le nombre de coordonnées de A, f <- A est une fonction de E x {0;1} ->   E x {0;1}, Si A a une seule coordonnée, mettons A= a alors f <- A = f o a et la récursion est f <- (a1, ....., an) = f o an o f<-(a1, ...., a_n-1). Désolé pour le latex ça fait trop longtemps que je n'y ai pas touché :)
    Aussi |k désigne la restriction aux k premières coordonnes donc soit k <= n (a_1, ...., a_n)|k = (a_1, ..., a_k) , _k désigne la kieme coordonne (a_1, ...., a_n)_k = a_k. D'où la définition par récursion qui peut aussi s'écrire plus proprement :
     si A a n coordonées: f<-A = f o A_n o f <- A|n-1.
  • J'ai vérifié et effectivement, j'ai fait une erreur de raisonnement dans le cas $E$ infini. Cependant, cela peut marcher si $E$ est infini. Par exemple : $f(x,b) = (x+1,b)$ avec $E = \mathbb{Z}$. Le cas infini est plus compliqué et donc plus intéressant. Tu as un contre-exemple pour $E$ infini ? Je n'ai pas eu le temps d'en trouver un.
  • EtNonLesShills
    Modifié (June 2023)
    mhh mhh
    soit E={ {0;1}^Z contenant une infinité de 1 de coordonne dans lN}
    f E x Z x{0;1} -> E x Z x{0;1}
    permutant la coordonnée d'indice le second membre du premier membre avec le troisième membre puis ajoutant 1 au deuxieme membre doit faire l'affaire je pense.
    Je reecris un peu si c'est pas clair:
    (....u_k-1, u_k, u_k+1 ....), k , b ->  (....u_k-1, b , u_k+1 ....), k+1 , u_k 
Connectez-vous ou Inscrivez-vous pour répondre.