6. Il problema del downcast

Prerequisito: I tratteggi lineari di primo ordine

Come si può intuire dagli articoli precedenti, la difficoltà del calcolo delle funzioni \mathrm{t}, \mathrm{t\_valore} e \mathrm{t\_spazio} aumenta con l’aumentare dell’ordine del tratteggio.
Nell’articolo precedente abbiamo visto che le formule che calcolano queste funzioni per i tratteggi di primo ordine sono molto semplici, in particolare quelle per le funzioni \mathrm{t} e \mathrm{t\_valore} derivano direttamente dalla definizione di tratteggio lineare. Nei tratteggi lineari di ordini superiori le cose si complicano. Infatti, la funzione tratteggio viene definita in modo diverso per ciascun indice di riga (come nella formula (5) dell’articolo Tratteggi, trattini e spazi: alcune definizioni e semplici proprietà), mentre ad esempio la funzione \mathrm{t\_valore} continua a restituire il valore dell’n-esimo trattino in generale, ossia combinando le righe rispettando l’ordinamento definito dalla Definizione T.4 (Ordinamento dei trattini).
Una situazione analoga vale anche per le funzioni \mathrm{t} e \mathrm{t\_spazio}: è molto semplice calcolarle per tratteggi di primo ordine, mentre per tratteggi di ordini superiori il loro calcolo presenta maggiore difficoltà, trattandosi di funzioni che riguardano il tratteggio nel complesso e non le singole righe.
Il principale approccio per risolvere questo problema consiste, come spesso si fa in matematica, nel ricondursi ad un caso più semplice: per calcolare una delle funzioni \mathrm{t}, \mathrm{t\_valore} o \mathrm{t\_spazio} per un tratteggio di secondo ordine, ci si riconduce al calcolo della stessa in un tratteggio di primo ordine; per un tratteggio di terzo ordine, ci si riconduce al secondo, che a sua volta è ricondotto al primo, e così via: il calcolo per un ordine generico avviene scendendo da un ordine all’altro, fino al primo, dove non vi sono difficoltà.

Alla base di questo meccanismo di discesa da un ordine all’altro vi è il concetto di sottotratteggio (Definizione T.6). Partendo da un tratteggio di ordine k ed escludendo una delle sue righe, si ottiene un sottotratteggio di ordine k - 1. Trattandosi di un sottotratteggio proprio, i suoi trattini costituiscono un sottoinsieme proprio di quelli del tratteggio originale. Questo implica due cose:

  • L’x-esimo trattino del tratteggio originale può trovarsi o non trovarsi nel sottotratteggio;
  • Nel caso in cui si trovi nel sottotratteggio, rispetto a quest’ultimo non sarà più l’x-esimo, ma l’y-esimo, per qualche y che in generale è diverso da x.

Confrontiamo il tratteggio (3, 4) col suo sottotratteggio (3). In questo caso nel passaggio al sottotratteggio i trattini della seconda riga vengono persi, mentre quelli della prima riga vengono conservati, ma in generale cambiano ordinale:

Figura 1: cambio dell’ordinale dei trattini quando si passa da un tratteggio ad un suo sottotratteggio proprio

Dunque l’approccio per il calcolo di \mathrm{t}_T(x) per un tratteggio T di ordine k \gt 1 è il seguente:

  1. Trovare un sottotratteggio proprio U di T che contiene il trattino da calcolare
  2. Calcolare l’ordinale del trattino in U: si troverà così un numero y tale che \mathrm{t}_T(x) = \mathrm{t}_U(y)
  3. Calcolare \mathrm{t}_U(y)

L’ultimo passaggio è il calcolo della funzione \mathrm{t} sul tratteggio U che ha ordine minore di k, al massimo k - 1. A questo punto, se U è di ordine 1 possiamo calcolare direttamente \mathrm{t}_U(y); altrimenti con lo stesso meccanismo possiamo trovare un sottotratteggio proprio V di U tale che t_U(y) = t_V(z) per qualche z, scendendo ad un ordine ancora inferiore, e così via fino ad arrivare, prima o poi, al primo ordine.

Per quanto riguarda il passo 2, nei prossimi articoli vedremo che si può trovare una funzione che, dati T ed il suo sottotratteggio U, trasforma qualunque x nel corrispondente y, ossia trasforma l’ordinale di un trattino di T nell’ordinale dello stesso in U, a patto che esso appartenga ad U. Una tale funzione è detta funzione di downcast di \mathrm{t} da T ad U.

Consideriamo il tratteggio T = (3, 4, 5) e focalizziamoci sul suo settimo trattino. Come possiamo vedere in Figura 2, questo trattino è il secondo della terza riga, ossia \mathrm{t}_T(7) = (3, 2). Se però consideriamo il sottotratteggio U = T[2,3] = (4, 5), il trattino (3, 2) non ha più ordinale 7, bensì 4. Ancora, possiamo considerare il sottotratteggio V = U[3] = T[3] = (5), nel quale il trattino di partenza ha ordinale 2:

Figura 2: cambio dell’ordinale di un trattino del tratteggio (3, 4, 5), scendendo fino ad un sottotratteggio di primo ordine

Dunque, ricapitolando, \mathrm{t}_T(7) = \mathrm{t}_U(4) = \mathrm{t}_V(2) = (3, 2). In questi passaggi abbiamo applicato:

  • Un metodo per stabilire che \mathrm{t}_T(7) \in U = T[2, 3] (per ora si tratta di un metodo esclusivamente grafico)
  • Una funzione di downcast di \mathrm{t} da T ad U, che partendo dall’ordinale 7 calcola l’ordinale 4
  • Un metodo per stabilire che \mathrm{t}_U(4) \in V = U[3] = T[3] (sempre di tipo grafico)
  • Una funzione di downcast di \mathrm{t} da U a V, che partendo dall’ordinale 4 calcola l’ordinale 2
  • La funzione \mathrm{t} per il tratteggio di primo ordine V: essendo 3 l’indice dell’unica riga di V, per la Proposizione T.1 (Funzioni \mathrm{t} e \mathrm{t\_valore} lineari di primo ordine) si ha che \mathrm{t}_V(2) = (3, 2).

Possiamo descrivere schematicamente questo procedimento come segue:

T \longrightarrow T[2,3] \longrightarrow T[3]

In alternativa, usando altri sottotratteggi, potremmo ottenere lo stesso risultato finale nel modo seguente:

T \longrightarrow T[1,3] \longrightarrow T[3]

Oppure, più rapidamente, possiamo pensare di effettuare un downcast direttamente da T al suo sottotratteggio di primo ordine T[3], passando direttamente dall’ordinale 7 all’ordinale 2:

T \longrightarrow T[3]

Non è detto, cioè, che nel downcast si debba scendere sempre di un ordine alla volta. Tuttavia, le funzioni di downcast che consentono di scendere di più di un ordine in un solo passo possono essere più complesse, o soggette a maggiori limitazioni (approfondiremo questo tema nei prossimi articoli).

Possiamo ripetere il ragionamento del downcast anche per quanto riguarda la funzione \mathrm{t\_valore}.
Dato un tratteggio T ed un intero positivo x, sappiamo che per definizione l’x-esimo trattino di T ha valore v := \mathrm{t\_valore}_T(x). Allora, dato un sottotratteggio proprio U di T, possiamo chiederci se U contiene anch’esso un trattino di valore v e, in caso affermativo, quale sia un numero y tale che \mathrm{t\_valore}_T(x) = \mathrm{t\_valore}_U(y). Se trovassimo una funzione che, fissati T ed U, trasformi un generico x nel corrispondente y, essa sarebbe una funzione di downcast di \mathrm{t\_valore} da T ad U.
Ma, a ben vedere, una tale funzione la conosciamo già, ed è la stessa del downcast di \mathrm{t}. Cerchiamo di capire perché. Fissiamo un intero positivo x, chiamiamo t l’x-esimo trattino di T, ed indichiamo con v il suo valore, cioè \mathrm{t\_valore}_T(x). Abbiamo che:

  • Se t \in U, possiamo applicare una funzione di downcast di \mathrm{t} per l’ordinale x. Questa funzione associerà ad x un certo numero y, ad indicare che t è l’y-esimo trattino di U;
  • Ma, trattandosi sempre dello stesso trattino, il suo valore è sempre v sia se lo vediamo in T che se lo vediamo in U, cioè T(t) = U(t);
  • Allora \mathrm{t\_valore}_T(x) = T(t) = U(t) = \mathrm{t\_valore}_U(y).

In altri termini, leggendo gli estremi dell’uguaglianza del terzo punto, abbiamo che la funzione di downcast di \mathrm{t} del primo punto, che associa x ad y, è anche una funzione di downcast di \mathrm{t\_valore}, sempre da T ad U, perché questi x ed y soddisfano la condizione \mathrm{t\_valore}_T(x) = \mathrm{t\_valore}_U(y).

Nell’esempio precedente abbiamo visto che, posto T = (3, 4, 5) ed U = T[2, 3], \mathrm{t}_T(7) = \mathrm{t}_U(4), dunque una funzione di downcast di \mathrm{t} da T ad U associa l’ordinale 7 all’ordinale 4. Ora proviamo a fare la stessa cosa con la funzione \mathrm{t\_valore}, ossia cerchiamo un numero y tale che

\mathrm{t\_valore}_T(7) = \mathrm{t\_valore}_U(y)

Abbiamo visto che il settimo trattino di T, \mathrm{t}_T(7), è (3, 2). Possiamo chiamare questo trattino \mathrm{t} e scrivere:

\mathrm{t\_valore}_T(7) = T(\mathrm{t}_T(7)) = T(t) = T(3, 2) = 10

Ma abbiamo visto che t è il quarto trattino di U: in formule, t = \mathrm{t}_U(4). Allora:

\mathrm{t\_valore}_U(4) = U(\mathrm{t}_U(4)) = U(t) = U(3, 2) = 10

Quindi:

\mathrm{t\_valore}_T(7) = 10 = \mathrm{t\_valore}_U(4)

cioè anche una funzione di downcast di \mathrm{t\_valore} da T ad U associa l’ordinale 7 all’ordinale 4.
Lo stesso ragionamento si può ripetere per qualsiasi x, non solo per x = 7: in generale possiamo dire che una funzione di downcast di \mathrm{t} è anche una funzione di downcast di \mathrm{t\_valore}, per la medesima coppia tratteggio-sottotratteggio.

Essendo il problema del downcast di \mathrm{t\_valore} riconducibile a quello del downcast di \mathrm{t}, la teoria dei tratteggi focalizza la sua attenzione su quest’ultimo, anche se il downcast di \mathrm{t\_valore} meriterebbe una maggiore attenzione.

Abbiamo detto che una funzione di downcast di \mathrm{t} è anche una funzione di downcast di \mathrm{t\_valore}, ma non tutte le funzioni di downcast di \mathrm{t\_valore} sono funzioni di downcast di \mathrm{t}. Cerchiamo di capire perché. Consideriamo il tratteggio T = (3, 4, 5) ed il suo sottotratteggio V^{\prime} = T[1, 2] = (3, 4):

Figura 3: il tratteggio T = (3, 4, 5) ed il suo sottotratteggio V’ = T[1, 2] = (3, 4)

Consideriamo il downcast T \longrightarrow V^{\prime}. Chiediamoci: quale risultato restituisce una funzione di downcast di \mathrm{t\_valore} da T a V^{\prime}, per x = 8? In altri termini, ci chiediamo qual è quel numero y tale che

\mathrm{t\_valore}_T(8) = 12 = \mathrm{t\_valore}_{V^{\prime}}(y) \tag{1}

Notiamo che in V^{\prime} ci sono due trattini di valore 12: (1, 4) e (2, 3), rispettivamente il sesto ed il settimo. Quindi la (1) ha due soluzioni, y = 6 ed y = 7:

Figura 4: Una funzione di downcast di t_valore da (3, 4, 5) a (3, 4) può associare al numero 8 il numero 6 oppure il numero 7
\mathrm{t\_valore}_T(8) = 12 = \mathrm{t\_valore}_{V^{\prime}}(6) = \mathrm{t\_valore}_{V^{\prime}}(7)

Allora una funzione di downcast di \mathrm{t\_valore} da T a V^{\prime}, per x = 8, può restituire 6 oppure 7. Ma naturalmente una funzione può assumere un solo valore per volta, per cui in questo caso esistono almeno due funzioni di downcast: una funzione f tale che f(8) = 6 ed una funzione g tale che g(8) = 7 (la parola almeno è d’obbligo in quanto la stessa situazione si potrebbe verificare per altri valori di x, e in questo caso si avrebbe una funzione diversa per ogni combinazione di valori possibili). La funzione g si comporta, per x = 8, come una funzione di downcast di \mathrm{t}, perché l’ottavo trattino di T è il sesto di V^{\prime}. Tuttavia anche il settimo trattino di V^{\prime}, pur non coincidendo con l’ottavo di T, ha lo stesso valore: ecco perchè la funzione f è una funzione di downcast di \mathrm{t\_valore}, ma non di \mathrm{t}.

Da questo esempio è chiaro che, in generale, l’esistenza di funzioni di downcast di \mathrm{t\_valore} che non sono funzioni di downcast di \mathrm{t}, deriva dalla presenza, nel tratteggio e nel sottotratteggio considerati, di trattini diversi aventi lo stesso valore. Questo aspetto della teoria dei tratteggi non è stato ancora studiato in modo generale: costituisce pertanto un punto aperto.

Il termine inglese downcast, intraducibile in italiano se non con locuzioni complesse, proviene dal mondo dei linguaggi di programmazione. In questo contesto il termine indica, in generale, una conversione del tipo di una variabile, da un tipo più generale ad uno più specifico.

Dopo aver analizzato il problema del downcast per le funzioni \mathrm{t} e \mathrm{t\_valore}, resta da vedere cosa succede per la funzione \mathrm{t\_spazio}. In quest’ultimo caso la differenza sostanziale è che, mentre non tutti i trattini di un tratteggio appartengono ad un suo sottotratteggio proprio (e di conseguenza anche i loro valori, in generale, non è detto che siano valori di trattini del sottotratteggio), non si può dire la stessa cosa degli spazi. Infatti, come conseguenza della definizione di spazio, tutti gli spazi di un tratteggio sono anche spazi di qualunque suo sottotratteggio, mentre non è vero il viceversa: è l’esatto contrario di ciò che avviene per i trattini. In altri termini, nel passaggio da un tratteggio ad un suo sottotratteggio, in generale i trattini diminuiscono, mentre gli spazi aumentano. Ad esempio, il tratteggio V = (3, 4) della Figura 4:

  • ha meno trattini di T = (3, 4, 5), perché non ha tutti quelli della terza riga;
  • ha più spazi: infatti tutti gli spazi di T (1, 2, 7, 11, 13, 14, 17, …) li ritroviamo anche in V, in più 5 e 10 sono spazi di V ma non di T.

Comunque, il fatto che un sottotratteggio abbia simultaneamente “meno trattini” e “più spazi” appare abbastanza naturale, dato che intuitivamente i trattini occupano posizioni che, in loro assenza, diventano spazi.

Tornando alla differenza tra le funzioni \mathrm{t}, \mathrm{t\_valore} e \mathrm{t\_spazio}, diremo che la funzione \mathrm{t\_spazio} è down-conservativa per indicare il fatto che essa “conserva” gli spazi passando da un tratteggio ad un suo sottotratteggio (aggiungendone eventualmente di nuovi), mentre \mathrm{t} e \mathrm{t\_valore} non lo sono, perchè i trattini non si conservano nei sottotratteggi, anzi, in generale si perdono.

Per il suo essere down-conservativa, la funzione \mathrm{t\_spazio} facilita l’operazione di downcast rispetto alle altre due funzioni: non dobbiamo chiederci, come facevamo coi trattini, se lo spazio del tratteggio di partenza lo troviamo anche nel sottotratteggio: sappiamo già che è così, per cui dobbiamo solo trovare una funzione di downcast.

Con riferimento ai tratteggi T, U e V della Figura 1, vediamo che il quarto spazio di T è 11, ed esso corrisponde al settimo spazio di U ed al nono di V:

Figura 5: downcast di t_spazio da (3, 4, 5) a (4, 5) e da quest’ultimo a (5)

In formule:

\mathrm{t\_spazio}_T(4) = 11 = \mathrm{t\_spazio}_U(7) = \mathrm{t\_spazio}_V(9)

Quindi una funzione di downcast di \mathrm{t\_spazio} da T ad U manda 4 in 7, ed una da U a V manda 7 in 9. Per inciso, notiamo che non è un caso che l’ordinale dello spazio aumenti man mano che si scende nei sottotratteggi: un sottotratteggio contiene in generale più spazi del tratteggio di provenienza e quindi, essendo \mathrm{t\_spazio} crescente, per raggiungere lo stesso spazio bisogna utilizzare, in generale, un ordinale più grande.

Riassumiamo quanto visto finora nelle seguenti definizioni:

Funzione di downcast

Sia f_T una funzione definita su \mathbb{N}^{\star}, la cui definizione dipende da un tratteggio T, come \mathrm{t}_T, \mathrm{t\_valore}_T e \mathrm{t\_spazio}_T. Siano U un tratteggio e V un suo sottotratteggio.
Sia d: \mathbb{N}^{\star} \rightarrow \mathbb{N}^{\star} una funzione tale che:

\exists y \text{ tale che } f_T(x) = f_U(y) \implies d(x) = y \tag{2}

allora d si dice funzione di downcast di f da T ad U. L’operazione che consiste nell’applicazione di tale funzione, verificando l’esistenza dell’y della (2), si chiama downcast da T ad U. Se y non esiste, si dice che il downcast da T ad U di f per x non è possibile.

Funzione down-conservativa

Sia f_T una funzione definita su \mathbb{N}^{\star}, la cui definizione dipende da un tratteggio T, come \mathrm{t}_T, \mathrm{t\_valore}_T e \mathrm{t\_spazio}_T. Siano U un tratteggio e V un suo sottotratteggio. Se l’insieme dei possibili valori assunti da f_V è un sottoinsieme dei possibili valori assunti da f_U, cioè se

f_V(\mathbb{N}^{\star}) \subseteq f_U(\mathbb{N}^{\star})

Allora la funzione f_U si dice down-conservativa. Inoltre, coerentemente con le definizioni di \mathrm{t}, \mathrm{t\_valore} e \mathrm{t\_spazio} (Definizioni T.7, T.8 e T.9):

  • Se f_U è down-conservativa per ogni U, si dice che la funzione f è down-conservativa.
  • Se esiste un tratteggio U tale che f_U non è down-conservativa, allora si dice che la funzione f non è down-conservativa.

Con riferimento al tratteggio T = (3, 4, 5) ed al suo sottotratteggio U = (3, 4) mostrato nella Figura 5, posto f = \mathrm{t\_spazio}, abbiamo che

\mathrm{t\_spazio}_T(\mathbb{N}^{\star}) = \mathrm{t\_spazio}_T(\{1, 2, 3, 4, 5, 6, 7, \ldots\}) = \{1, 2, 7, 11, 13, 14, 17, \ldots\}
\mathrm{t\_spazio}_U(\mathbb{N}^{\star}) = \mathrm{t\_spazio}_T(\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \ldots\}) = \{1, 2, 3, 6, 7, 9, 11, 13, 14, 17, 18, \ldots\}

Dunque, come previsto nella Definizione T.11:

\mathrm{t\_spazio}_T(\mathbb{N}^{\star}) = \{1, 2, 7, 11, 13, 14, 17, \ldots\} \subseteq \{1, 2, 3, 6, 7, 9, 11, 13, 14, 17, 18, \ldots\} = \mathrm{t\_spazio}_U(\mathbb{N}^{\star})

Poichè questo accade per ogni sottotratteggio U, diciamo che \mathrm{t\_spazio}_T è down-conservativa. In realtà questo comportamento non dipende nemmeno dal tratteggio di partenza T, perciò diciamo che la funzione \mathrm{t\_spazio} è down-conservativa.

Si noti che la terminologia “la funzione f è down-conservativa” è impropria, perchè f non è tecnicamente una funzione, ma lo diventa quando si specifica un tratteggio nel pedice. Tuttavia risulta più semplice dire, ad esempio, “la funzione \mathrm{t\_spazio} è down-conservativa” rispetto a dire “la funzione \mathrm{t\_spazio}_T è down-conservativa per ogni T“.
Al posto del termine down-conservativa si potrebbe usare l’italiano sotto-conservativa, ma preferiamo il termine inglese per uniformità con downcast.

Abbiamo già osservato che vale la seguente proprietà:

Down-conservatività delle funzioni \mathrm{t}, \mathrm{t\_valore} e \mathrm{t\_spazio}

La funzione \mathrm{t\_spazio} è down-conservativa, mentre \mathrm{t} e \mathrm{t\_valore} non lo sono.

Infine, analizzando in dettaglio la definizione di funzione di downcast, possiamo notare che essa non è completamente determinata, ma lo è solo per gli x che corrispondono a trattini/valori/spazi che sono presenti nel sottotratteggio: per gli altri x la definizione non specifica come la funzione debba comportarsi. Questo grado di libertà fa sì che esistano, in generale, più possibili funzioni di downcast distinte, per la stessa coppia tratteggio-sottotratteggio.

Considerando il downcast di \mathrm{t} da T = (3, 4) ad U = (3) mostrato in Figura 1, per la Definizione T.10 (Funzione di downcast), una funzione di downcast è definita per tutti gli x tali che:

\exists y \text{ tale che } \mathrm{t}_T(x) = \mathrm{t}_U(y)

Ma non sempre esiste questo y, perché la funzione \mathrm{t} non è down-conservativa. Nel dettaglio, se d è una funzione di downcast, abbiamo che:

  • Per x = 1, \mathrm{t}_T(x) = (1, 1). È un trattino della prima riga, l’unica del tratteggio U, dunque appartiene ad U. Abbiamo che \mathrm{t}_T(x) = (1, 1) = \mathrm{t}_U(1), quindi d(1) = 1.
  • Per x = 2, \mathrm{t}_T(x) = (2, 1). È un trattino della seconda riga, che quindi non appartiene ad U. Quindi il valore d(2) non è definito.
  • Per x = 3, \mathrm{t}_T(x) = (1, 2) \in U. In U si ha che (1, 2) = \mathrm{t}_U(2), quindi d(3) = 2.
  • Per x = 4, \mathrm{t}_T(x) = (2, 2) \notin U. Quindi il valore d(4) non è definito.
  • Per x = 5, \mathrm{t}_T(x) = (1, 3) \in U. In U si ha che (1, 3) = \mathrm{t}_U(3), quindi d(5) = 3.

In sintesi, analizzando le x da 1 a 5, per definizione di funzione di downcast sono definiti i valori

d(1) = 1, d(3) = 2, d(5) = 3 \tag{3}

mentre non sono definiti i valori d(2) ed d(4). Ciò significa che questa d non è univocamente determinata, ma qualunque funzione che rispetti i vincoli (3) è una funzione di downcast valida (o almeno lo è per x = 1, \ldots, 5), a prescindere da quali siano d(2) e d(4). Ad esempio, sono funzioni di downcast valide le seguenti:

  • d(1) = 1, d(2) = 1, d(3) = 2, d(4) = 2, d(5) = 3
  • d(1) = 1, d(2) = 2, d(3) = 2, d(4) = 5, d(5) = 3
  • d(1) = 1, d(2) = 34, d(3) = 2, d(4) = 125, d(5) = 3

Ma è chiaro che le possibili funzioni di downcast sono infinite, perchè possiamo inventarci qualsiasi valore per d(2) e d(4).

In generale, si può dimostrare la seguente Proprietà:

Unicità della funzione di downcast

Sia f_T una funzione definita su \mathbb{N}^{\star}, la cui definizione dipende da un tratteggio T, come \mathrm{t}_T, \mathrm{t\_valore}_T e \mathrm{t\_spazio}_T. Sia U un tratteggio e V un suo sottotratteggio.
Esiste un’unica funzione di downcast di f da U a V se il numero y della formula (2) della definizione di downcast esiste ed è unico per ogni x:

\forall x \exists! y \text{ tale che } f_U(x) = f_V(y)

In particolare:

  • se la funzione f_U è down-conservativa, y esiste per ogni x
  • se y esiste, esso è unico se la funzione f_V è iniettiva

Di conseguenza, esiste sempre un’unica funzione di downcast di f, per ogni coppia di tratteggio-sottotratteggio UV, se f è sia down-conservativa che iniettiva: è proprio il caso della funzione \mathrm{t\_spazio}.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.