Mi e' tornato in mente pensando alla funzionale postata da Matthew, girava qualche anno fa qui a Pisa...
La funzione "shift" è una funzione che prende una sequenza di numeri naturali
$ (a)=(a_1,a_2,\ldots,a_n,\ldots) $ e ritorna la stessa successione privata del primo elemento:
$ S(a)=(a_2,a_3,\ldots,a_{n-1},\ldots) $
Esiste una funzione dalle sequenze di naturali in se' che sia un "mezzo shift", cioè $ f $ t.c.
$
f(f(a))=S(a)
$
?
bye,
Il mezzo shift
Il mezzo shift
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
-
HumanTorch
- Messaggi: 281
- Iscritto il: 01 gen 1970, 01:00
- Località: Tricase
Vorrei chiedere qualcosa se non dispiace, dato che in funzioni (come nel resto del resto) sono una schiappa: se ad esempio la successione è una successione aritmetica, è possibile definire una sorta di "funzione casello"?:
cioè se il primo termine è maggiore dell'unità, lo elevo alla $ -1 $; se è minore lo cancello; o (nel caso la funzione sia definita $ \mathbb{N}\rightarrow\mathbb{N} $) se abbiamo una prograssione aritmetica di ragione $ b $, maggioriamo di $ k\neq 0 $ il primo termine se esso rispetta la progressione mentre lo scartiamo se non la rispetta..insomma definire una sorta di funzione che prenda un bivio o un trivio (come il simbolo di Legendre, anche se non so se l'esempio calzi perfettamente) alternante.
Se non erro si potrebbe usare un concetto del genere anche per la funzionale proposta da EuLEr tempo fa (o magari possono centrare altre funzioni particolari, come totienti o strutture del genere, dopo aver ricondotto ogni variabile a valori dati? Aspetto delucidazioni, grazie in anticipo
EDIT: Grazie a EvaristeG e a fph per i chiarimenti
cioè se il primo termine è maggiore dell'unità, lo elevo alla $ -1 $; se è minore lo cancello; o (nel caso la funzione sia definita $ \mathbb{N}\rightarrow\mathbb{N} $) se abbiamo una prograssione aritmetica di ragione $ b $, maggioriamo di $ k\neq 0 $ il primo termine se esso rispetta la progressione mentre lo scartiamo se non la rispetta..insomma definire una sorta di funzione che prenda un bivio o un trivio (come il simbolo di Legendre, anche se non so se l'esempio calzi perfettamente) alternante.
Se non erro si potrebbe usare un concetto del genere anche per la funzionale proposta da EuLEr tempo fa (o magari possono centrare altre funzioni particolari, come totienti o strutture del genere, dopo aver ricondotto ogni variabile a valori dati? Aspetto delucidazioni, grazie in anticipo
EDIT: Grazie a EvaristeG e a fph per i chiarimenti
Ultima modifica di HumanTorch il 18 giu 2005, 13:43, modificato 3 volte in totale.
Puoi definire una funzione come più ti pare...
Una funzione è una regola per associare ad ogni elemento del dominio uno e un solo elemento del codominio.
In termini insiemistici, una funzione $ f:X\to Y $ è un sottoinsieme $ F\subseteq X\times Y $ tale che, comunque preso x in X e y_1, y_2 in Y, se $ (x,y_1)\in F,\ (x,y_2)\in F $ allora $ y_1=y_2 $.
Ad esempio, la funzione di Dirichlet $ f:\mathbb{R}\to\mathbb{R} $ è il seguente mostro :
$ f(x)=\left\{\begin{array}{ll}1& \textrm{ se } x\in\mathbb{Q}\\0&\textrm{ se } x\notin\mathbb{Q}\end{array}\right. $
Questa cosa vale 1 se il numero x è razionale e 0 se è irrazionale.
Basta che ad ogni elemento del dominio sia associato uno ed un solo elemento del codominio.
Una funzione è una regola per associare ad ogni elemento del dominio uno e un solo elemento del codominio.
In termini insiemistici, una funzione $ f:X\to Y $ è un sottoinsieme $ F\subseteq X\times Y $ tale che, comunque preso x in X e y_1, y_2 in Y, se $ (x,y_1)\in F,\ (x,y_2)\in F $ allora $ y_1=y_2 $.
Ad esempio, la funzione di Dirichlet $ f:\mathbb{R}\to\mathbb{R} $ è il seguente mostro :
$ f(x)=\left\{\begin{array}{ll}1& \textrm{ se } x\in\mathbb{Q}\\0&\textrm{ se } x\notin\mathbb{Q}\end{array}\right. $
Questa cosa vale 1 se il numero x è razionale e 0 se è irrazionale.
Basta che ad ogni elemento del dominio sia associato uno ed un solo elemento del codominio.
Qui trovi due parole in piu' su "che cos'e' una funzione", ma in pratica EvaristeG ti ha gia' risposto esaurientemente...
ciao,
ciao,
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
acqua, molta acqua allora...Sisifo ha scritto:Io ci sto provando da un po' e più ci penso più mi convinco che non esiste il 'mezzo shift'.
hint: prova a considerare l'insieme 0,1,2,...,99, al posto dei naturali...
EDIT: specificato meglio "insieme finito", con molti "insiemi finiti" il problema e' decisamente piu' incasinato del caso $ \mathbb N $
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Ok. Allora dato che non sono capace di contare fino a 99, mi fermo prima. Diciamo che mi fermo a 0. Allora l'unica sequenza a valori in {0} è la sequenza costante (0, 0, 0, ...) [sai che allegria!!]
L'unica funzione possibile è la funzione identità che manda l'unica sequenza in sé, quindi se prendo f = id., f^2 = Shift, quindi l'identità è il mezzo shift cercato.
Evvai, il primo caso è mio!!!
Ciao. M.
L'unica funzione possibile è la funzione identità che manda l'unica sequenza in sé, quindi se prendo f = id., f^2 = Shift, quindi l'identità è il mezzo shift cercato.
Evvai, il primo caso è mio!!!
Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Sia S l'insieme degli elementi della sequenza e sia H tale che $ |H \times H| = |S| $ e g una funzione bigettiva $ g: S \to H \times H $.
H esiste sse S è infinito (H = S) o S ha cardinalità quadrata e g esiste per la definizione di cardinalità.
Allora la funzione di mezzo shift si puo costruire splittando in due ogni elemento della sequenza usando g, shiftando la sequenza risultante e infine mergiando gli elementi due a due usando g^-1.
Il caso di S insieme finito con cardinalità non quadrata rimane aperto.
H esiste sse S è infinito (H = S) o S ha cardinalità quadrata e g esiste per la definizione di cardinalità.
Allora la funzione di mezzo shift si puo costruire splittando in due ogni elemento della sequenza usando g, shiftando la sequenza risultante e infine mergiando gli elementi due a due usando g^-1.
Il caso di S insieme finito con cardinalità non quadrata rimane aperto.
-
MindFlyer
@LB: Sì, funziona. "Splittando", "mergiando", "shiftando". Bleah! Ma un modo umano di parlare, no, eh?
La mia sol invece è un po' più complicata, e fa uso dell'Assioma di Scelta, però si generalizza a qualunque insieme di base S.
Ok. Rilancio: dimostrare che il mezzo shift esiste per qualunque S finito. Pane e nutella offerti dal sottoscritto se qualcuno ci riesce senza la Scelta.
Ciao. M.
La mia sol invece è un po' più complicata, e fa uso dell'Assioma di Scelta, però si generalizza a qualunque insieme di base S.
Ok. Rilancio: dimostrare che il mezzo shift esiste per qualunque S finito. Pane e nutella offerti dal sottoscritto se qualcuno ci riesce senza la Scelta.
Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Mi sembra di avere dimostrato l'impossibilità nel caso 2...
La dimostrazione è la seguente.
Consideriamo tutte le soluzioni di S(S(x)) = x. Si vede facilmente che sono le sequenze periodiche con periodo di lunghezza 1 o 2.
Dunque ce ne sono 4, che chiamamo a = 010101..., b = 101010..., z = 000000..., u = 111111...
Chiaramente S(a) = b, S(b) = a, S(z) = z e S(u) = u.
Quindi ovviamente f(a) != a e f(b) != b.
Inoltre f(a) != b poichè altrimenti deve essere f(b) = b e analogamente f(b) != a.
Quindi esiste c diverso da a e b tale che f(a) = c e f(c) = b.
Analogamente esiste d diverso da a e b tale che f(b) = d e f(d) = a.
Inoltre c != d perchè altrimenti a = f(d) = f(c) = b.
Ma allora S(c) = f(f(c)) = d ed S(d) = f(f(d)) = c.
Quindi S(S(c)) = c ed S(S(d)) = d e inoltre S(c) != c e S(d) != d.
Ma a, b sono le uniche soluzioni di S(S(x)) = x tali che S(x) != x ed essendo c != a, c != b, d != a, d != b si ottiene un assurdo.
Questo sembra generalizzabile alla dimostrazione che la cardinalità deve essere della forma 4k o 4k + 1.
La dimostrazione è la seguente.
Consideriamo tutte le soluzioni di S(S(x)) = x. Si vede facilmente che sono le sequenze periodiche con periodo di lunghezza 1 o 2.
Dunque ce ne sono 4, che chiamamo a = 010101..., b = 101010..., z = 000000..., u = 111111...
Chiaramente S(a) = b, S(b) = a, S(z) = z e S(u) = u.
Quindi ovviamente f(a) != a e f(b) != b.
Inoltre f(a) != b poichè altrimenti deve essere f(b) = b e analogamente f(b) != a.
Quindi esiste c diverso da a e b tale che f(a) = c e f(c) = b.
Analogamente esiste d diverso da a e b tale che f(b) = d e f(d) = a.
Inoltre c != d perchè altrimenti a = f(d) = f(c) = b.
Ma allora S(c) = f(f(c)) = d ed S(d) = f(f(d)) = c.
Quindi S(S(c)) = c ed S(S(d)) = d e inoltre S(c) != c e S(d) != d.
Ma a, b sono le uniche soluzioni di S(S(x)) = x tali che S(x) != x ed essendo c != a, c != b, d != a, d != b si ottiene un assurdo.
Questo sembra generalizzabile alla dimostrazione che la cardinalità deve essere della forma 4k o 4k + 1.
Mannaggia alla fretta!! E sia. Mi sono allargato troppo.
Ecco i miei risultati [modulo altre stupidaggini]:
Claim: Se S è finito, il mezzo shift esiste sse #S=0,1 (mod.4). Se S è infinito il mezzo shift esiste. Se invece consideriamo solo le sequenze non periodiche, allora il mezzo shift esiste sempre, salvi i casi banali.
Ecco i miei risultati [modulo altre stupidaggini]:
Claim: Se S è finito, il mezzo shift esiste sse #S=0,1 (mod.4). Se S è infinito il mezzo shift esiste. Se invece consideriamo solo le sequenze non periodiche, allora il mezzo shift esiste sempre, salvi i casi banali.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."