^^Sottoinsiemi invarianti di una endofunzione.

Sottoinsiemi invarianti rispetto ad un'endofunzione

f:X→X   f e' un'endofunzione

sottoinsieme invariante nella endofunzione
f(A)⊆A  la sua immagine e' contenuta nell'insieme di partenza 

es: Laterale di un sottogruppo. Coset.

Casi particolari

  1. Rispetto all'Identita', tutti i sottoinsiemi sono invarianti.
  2. Un sottoinsieme invariante fatto di 1 solo punto, e' detto Punto fisso della endofunzione.

Successioni generate da una endofunzione.
Potenze di una endofunzione.

an+1 = f(an)   dato a0 elemento iniziale

riapplicare la funzione al suo risultato
a  f(a)  f(f(a))  f(f(f(a)))  ...
a  f(a)   f2(a)     f3(a)      ...  fn(a)  ...

Teo: il range della successione e' un insieme invariante dell'endofunzione che la genera

ed e' invariante sotto l'azione di ognuna delle sue potenze.

es: Per ragionarci consideriamo una endofunzione su un insieme finito

sia

  1. X={1,2,3,4,5}    un insieme di 5 elementi
  2. f={ (1,1), (2,2), (3,3), (4,1), (5,2) }   una f:X→X

 

f= 1 2 3 4 5
2 3 1 1 2
   e' la funzione scritta in forma tabella "orizzontale"

Es successioni che partono da ogni punto dello spazio

1→2→3→1→ ...  {1,2,3}

2→3→1→2→ ...   idem

3→1→2→3→ ...   idem

4→1→2→3→1→ ...   {4,1,2,3}

5→2→3→1→2→ ...   {5,1,2,3}

Per pensare alla situazione conviene pensare alla funzione come grafo orientato >>>.

  1 2 3 4 5 valori iniziali
f      2 3 1 1 2 funzione
f2 3 1 2 2 3  
f3 1 2 3 3 1  
f4 2 3 1 1 2 ripete f   f4=f1
f5 3 1 2 2 3 ripete f2  f5=f2
f6 1 2 3 3 1 ripete f3  f6=f3
f7 2 3 1 1 2 ripete f   f7=f
   f funzione non iniettiva

 

f0 1 2 3 4 5 valori iniziali
f      2 3 1 5 4 funzione
f2 3 1 2 4 5  
f3 1 2 3 5 4  
f4 2 3 1 4 5  
f5 3 1 2 5 4  
f6 1 2 3 4 5 ripete f0  f6=f0
f7 2 3 1 5 4 ripete f   f7=f1
   f funzione iniettiva

 

 

Comportamento delle successioni

2 casi:

  1. la successione ritorna ad un elemento gia' presentato
    ⇒ deve ripetere anche i valori seguenti, entra in un ciclo infinito, cioe' da li' in avanti diventa ciclica
  2. la successione non si ripete mai
    ⇒ l'endofunzione ha dominio infinito
    es: ℕ→ℕ  n→n+m

Teo: se l'insieme e' finito, la successione non puo' proseguire all'∞ senza ripetersi, quindi si ripete, e si distinguono 2 casi:

  1. ritorna al 1 elemento
    la f ristretta alla successione e' iniettiva
  2. non torna al 1 elemento

    la funzione non e' iniettiva, poiche' allo stesso elemento arriva da 2 elementi.

    Caso particolare: l'ultimo elemento elemento della successione e' l'immagine di se', cioe' e' un elemento fisso della funzione; le sue controimmagini sono se' e almeno chi lo precede nella successione.

Teo: la funzione e' iniettiva

tutte le successioni tornano al 1 elemento.
tutte non hanno elementi comuni
sono una partizione dell'insieme.

Teo: i range di tutte le successioni sono una copertura dell'insieme.

Unendo i range delle successioni con elementi comuni, si ottiene una partizione dell'insieme, fatta di sottoinsiemi invarianti.

 

 

Links

  1. Punto fisso di una endofunzione.
  2. Gruppo algebrico.
  3. Symmetric group. Gruppo delle permutazioni.
  4. Le traslazioni dell'opbin.

 

yt We're Building Computers Wrong

yt Microsoft and Nuance partner to deliver ambient clinical intelligence

Physician burnout is at epidemic levels as doctors spend two hours on administrative tasks for every hour they spend with patients, plus one to two hours of after-hours work at night. Discover how doctors from Nebraska Medicine use ambient clinical intelligence solutions from Nuance and Microsoft to lessen their administrative burden and to spend more time focusing on patients.

Approfond

Dirlo

  1. successione dei discendenti di un elemento, secondo f
  2. successione delle img successive di un elemento tramite la funzione, riapplicandola

Es successione generata in X5

1→2→3→1→2→ ...

2→3→1→2→3→ ...

3→1→2→3→1→ ...

4→1→2→3→1→ ...

5→2→3→1→2→ ...

          |←←←|

 

f:X→X      genera  una successione in  X|X|

a0 = (1,2,3,4,5)

an+1 = ( f(an,1), f(an,2), f(an,3), f(an,4), f(an,5) )

Endofunzione generata in  X|X|

volendo invece di una sola successione, si potrebbe estendere a endofunzione su tutto lo spazio   X|X|

f:X→X      genera  una endofunzione in  X|X|

f:X|X|→X|X|  (a1, a2, a3, a4, a5 ) →  ( f(a1), f(a2), f(a3), f(a4), f(a5) )