Curiosità relativa alle strutture contenute in Q

[40rob]

Salve, mi sono chiesto una cosa probabilmente stupida per chi conosce la risposta , non ci ho pensato molto ma m'è venuta voglia lo stesso di porre questo problema.
In (N, <) le sottostrutture che si possono formare a meno di isomorfismi con la stessa relazione < e che hanno per sostegno un insieme numerabile, sono al più una: insomma tutte le sottostrutture (proprie o non proprie) (A, <) con A incluso in N e A numerabile sono tutte isomorfe a (N, <).

In (Q, <) (insieme dei razionali) quante sottostrutture con sostegno numerabile si possono formare a meno di isomorfismi?

Dovrebbero essere più che numerabili intuitivamente, ma si può dimostrare che sono della potenza del continuo o no?

[killing_buddha]

Permettimi di rifrasare la domanda per come l'ho capita: consideri $(Q, \le)$ come insieme ordinato e ti chiedi quanti possibili sotto-poset (o reticoli, o altro?) ci puoi trovare (saranno automaticamente finiti o numerabili, perche' lo e' $Q$), a meno di isomorfismo. Giusto?

[40rob]

"killing_buddha":Permettimi di rifrasare la domanda per come l'ho capita: consideri $(Q, \le)$ come insieme ordinato e ti chiedi quanti possibili sotto-poset (o reticoli, o altro?) ci puoi trovare (saranno automaticamente finiti o numerabili, perche' lo e' $Q$), a meno di isomorfismo. Giusto?

Si, però voglio contare solo quelli con sostegno numerabile...

Quello che mi chiedo insomma è quante sottostrutture algebriche con sostegno numerabile (a meno di isomorfismi) può contenere $(Q, <)$ (però prendo solo quelle che hanno il sostegno numerabile). Ad esempio

$({0, 1, 2 , 3, 4, 5, 6, 7,...}, <)$ e $({0, 2, 4, 8, 16, 32...}, <)$ sono due strutture che hanno il sostegno numerabile contenuto in $Q$, ma hanno lo stesso tipo di ordine (sono isomorfe) e vanno contate una sola volta tutte quante insieme (quelle isomorfe). (concedimi l'abuso di notazione in cui uso sempre $<$, in realtà bisognerebbe considerare una restrizione di $<$ agli elementi contenuti nel sostegno).
Una nuova struttura diversa da quelle ad esempio è $({1/2, 1/2 + 1/4, 1/2 + 1/4 + 1/8, 1/2 + 1/4 + 1/8 + 1/16, 1/2 + 1/4 + 1/8 + 1/16 + 1/32..., 1}, <)$ perché non è isomorfa a queste.

In pratica si dovrebbe formare l'insieme di tutte le sottostrutture algebriche di $(Q, <)$ (ho usato la relazione di ordine stretto) che hanno sostegno numerabile (il cui numero di elementi distinti è numerabile), dividere questo insieme costituito da strutture in classi di equivalenza in base alla relazione di isomorfismo tra strutture e "contare" quante classi di equivalenza ci sono.

Spero di essere riuscito a spiegarmi .

Bisogna usare però sempre $<$ (la relazione d'ordine standard in $Q$ per ordinare gli elementi). Di sicuro le classi di equivalenza che si possono formare in numero sono minori o uguali alla potenza del continuo dato che sono minori o uguali alle Parti di $Q^2$, quel che vorrei provare a dimostrare è che sono proprio uguali a questa.

[perplesso1]

Ciao, in realtà la domanda che stai facendo (se l'ho interpretata bene) è quanti tipi di ordine posso formare rimanendo sotto la cardinalità del numerabile? Embè la prima cosa che mi viene in mente è questo: detto $\omega$ l'ordine dei naturali, allora il secondo ordine che hai descritto è $\omega + 1$. In generale tutti gli ordini che puoi formare sono della forma

$\omega + n_1 + \omega + n_2 + \omega + n_3 + ....$

essendo gli $n_i$ ordinali finiti (o eventualmente l'ordine vuoto...). Gli ordini che puoi formare in questo modo sono tanti quante sono le successioni di numeri naturali $n_1,n_2, ...$ cioè sono $\omega^\omega \cong 2^\omega$ che è la cardinalità del continuo. E questo dovrebbe rispondere alla tua domanda (sempre se non ho detto qualche fesseria xD )

[40rob]

"perplesso":Ciao, in realtà la domanda che stai facendo (se l'ho interpretata bene) è quanti tipi di ordine posso formare rimanendo sotto la cardinalità del numerabile?

non so se in $(Q, <)$ si possono formare tutti i tipi di ordine che si possono creare ridisponendo liberamente elementi numerabili (intendendo che la relazione che si può prendere in considerazione è una relazione d'ordine totale).
$<$ è la relazione d'ordine usuale in $Q$, non è una variabile!
Io mi sono chiesto solo se l'insieme di queste sottostrutture (a meno di isomorfismi) si può mettere in corrispondenza biunivoca con i reali. Pure è una domanda interessante la tua comunque.

Embè la prima cosa che mi viene in mente è questo: detto $\omega$ l'ordine dei naturali, allora il secondo ordine che hai descritto è $\omega + 1$. In generale tutti gli ordini che puoi formare sono della forma

$\omega + n_1 + \omega + n_2 + \omega + n_3 + ....$

In $(Q, <)$ si può formare, prendendo come sostegno ${1, 1 - 1/2, 1- 1/2 - 1/4, 1 - 1/2 - 1/4 - 1/8...}$, pure la struttura ordinata $({..., 1- 1/2 - 1/4 - 1/8, 1 - 1/2 - 1/4, 1 - 1/2, 1}, <)$ non isomorfa ai miei esempi precedenti perché non c'è minimo. $(Q, <)$ non contiene come sottostrutture solo buon ordini.
La struttura che ho esemplificato (isomorfa a $({...,-4, -3, -2 ,-1 ,0}, <)$ e a molte altre contenute in $(Q, <)$) non ricade nella tua forma perché non è dotata di minimo. Io ho fatto solo degli esempi di alcune sottostrutture di $(Q, <)$.

In pratica si può prendere un qualsiasi sottoinsieme numerabile incluso o uguale a $Q$ e lo si ordina con la relazione d'ordine stretto usuale $<$ che ordina gli elementi di $Q$, così resta definita una struttura ordinata, quel che mi chiedo è "quante strutture diverse si possono ottenere così facendo?" (intendendo che sono diverse solo le strutture non isomorfe mentre sono uguali quelle isomorfe).
Di sicuro comunque non sono finite perché $(Q, <)$. Intuitivamente penso che debbano essere della potenza del continuo, ma non mi viene un'idea per dimostrarlo, o per convincermene .

Non riesco a spiegarmi ancora?

[40rob]

"perplesso":Ciao, in realtà la domanda che stai facendo (se l'ho interpretata bene) è quanti tipi di ordine posso formare rimanendo sotto la cardinalità del numerabile? Embè la prima cosa che mi viene in mente è questo: detto $\omega$ l'ordine dei naturali, allora il secondo ordine che hai descritto è $\omega + 1$. In generale tutti gli ordini che puoi formare sono della forma

$\omega + n_1 + \omega + n_2 + \omega + n_3 + ....$

essendo gli $n_i$ ordinali finiti (o eventualmente l'ordine vuoto...). Gli ordini che puoi formare in questo modo sono tanti quante sono le successioni di numeri naturali $n_1,n_2, ...$ cioè sono $\omega^\omega \cong 2^\omega$ che è la cardinalità del continuo. E questo dovrebbe rispondere alla tua domanda (sempre se non ho detto qualche fesseria xD )

Scusami forse non avevo capito prima , ora forse ho afferrato meglio cosa volevi fare. La tua è una sommatoria infinita.
La tua dimostrazione secondo me è scorretta perché qualsiasi sequenza di ordinali finiti piazziamo nella tua formula otteniamo sempre lo stesso ordinale. Siccome per ogni ordinale finito $n$ si ha che $n + \omega = \omega$ abbiamo che nella sommatoria infinita possiamo sostituire $\omega$ al posto di $n_1 + \omega$, $\omega$ al posto di $n_2 + \omega$ e così via indipendentemente da quali ordinali finiti piazzi al posto degli $n$. Così facendo si ottiene sempre

$\omega + \omega + \omega + ...$

Insomma se scegli una sequenza a caso di ordinali finiti e li sostituisci in quella formula al posto degli $n$ ottieni sempre lo stesso ordinale (o se vuoi lo stesso tipo di buon ordine) e cioé $omega^2$. Comunque $\omega^\omega$ non rappresenta la cardinalità del continuo (in realtà questa non la si sa ancora posizionare in mezzo agli ordinali) è un ordinale abbastanza piccolo, mentre $2^\omega = \omega$. Poi l'elevamento a potenza tra ordinali è un'operazione ben diversa dall'elevamento a potenza tra cardinali, quando si usa la notazione con $\omega$ la si usa per indicare operazioni tra ordinali.

La tua funzione comunque mette in corrispondenza le sequenze di naturali (equipotenti al continuo) con un solo tipo di ordine e cioé $omega^2$, a sequenze diverse non corrispondono tipi di ordine diversi, ma sempre lo stesso tipo.

[perplesso1]

Aspetta ora mi spiego meglio... quando dico "tipo di ordine" io mi riferisco a questo http://en.wikipedia.org/wiki/Order_type e questo http://mathworld.wolfram.com/OrderType.html mentre col segno $+$ intendo l'ordine che si ottiene concatenando due ordini. Prima di tutto io individuo in $QQ$ alcuni tipi di ordine che considero fondamentali

$\omega$ è il tipo di ordine di $NN$ e dei sottoinsiemi ad esso isomorfi

$\omega^d$ è il "duale" di $\omega$, cioè è l'ordine degli interi negativi ${... -3, -2, -1}$ o equivalentemente di ${1/n : n \in NN }$

$\rho$ è l'ordine di un qualsiasi intervallo aperto $(a,b) \subseteq QQ$ di numeri razionali

$n$ è l'ordine del sottoinsieme ${1,2,3,...,n}$

Per ottenere un tipo di ordine complesso come ad esempio $\omega^d + 3 + \rho + 2$ basta prendere un sottoinsieme di $QQ$ come questo

${1/n : n \in NN } \cup {2,3,4} \cup (4,5) \cup {6,7}$

con la relazione d'ordine usuale (non sto cambiando relazione eh xD). La mia idea (tutta da dimostrare) è che l'ordine di un qualsiasi sottoinsieme di $QQ$ si possa ottenere concatenado fra loro i tipi $\omega, \omega^d, \rho$ ed $n$ con $n < \omega$ cioè creando sequenze (anche infinite) del tipo

$... + \omega +5 + \rho + \omega^d +2 + ....$

etc etc. Chiamiamo $ T = {\omega, \omega^d, \rho} \cup {n: n < \omega}$ l'insieme dei "tipi fondamentali". Allora è sufficiente contare le applicazioni $ZZ -> T $ che sono $\aleph_0^{\aleph_0}$ perchè $T$ e $ZZ$ sono entrambi numerabili.

Questo è quello che ho pensato io, ma magari la questione è più facile... non so.. boh xD

[40rob]

perplesso:Chiamiamo $ T = {\omega, \omega^d, \rho} \cup {n: n < \omega}$ l'insieme dei "tipi fondamentali". Allora è sufficiente contare le applicazioni $ZZ -> T $ che sono $\aleph_0^{\aleph_0}$ perchè $T$ e $ZZ$ sono entrambi numerabili.

Questo è quello che ho pensato io, ma magari la questione è più facile... non so.. boh xD

Il problema in questo tipo di dimostrazione si pone sempre allo stesso livello. Ad applicazioni diverse $\mathbb{Z} \to T $ non è detto che corrispondano risultati (delle rispettive concatenazioni) diversi...
Ad esempio consideriamo le due applicazioni $f:\mathbb{Z} \to T$ e $g:\mathbb{Z} \to T$ tali che

$f(-1) = \omega$
$f(x) = 1$ (con questo $1$ voglio intendere il tipo di ordine) se $x$ è diverso da $- 1$

$g(0) = \omega$
$g(x) = 1$ se $x$ è diverso da $0$

ecco le due applicazioni sono distinte perché $g(0) = \omega$ è distinto da $f(0) = 1$, ma concatenando le loro immagini con l'operazione di concatenazione $+$ produciamo lo stesso tipo di ordine. Così facendo conti due applicazioni (e molte altre come queste) che dovresti contare una volta sola.
Noi dobbiamo contare i risultati distinti delle concatenazioni che si ottengono usando l'operazione $+$ e non le applicazioni (o le concatenazioni) che abbiamo usato per ottenerle. Insomma dobbiamo "contare" i tipi di ordine che si ottengono a valle e non le applicazioni che abbiamo usato per produrli a monte, non è detto che questi due numeri cardinali coincidano se capita che applicazioni distinte possono produrre lo stesso tipo di ordine.
Per fare un esempio finito più banale puoi contare le applicazioni da $\{0, 1\} \to \{2, 3\}$ che sono $2^2 = 4$ ma se vuoi contare i risultati delle "concatenazioni" con l'operazion $+$ (che in questo caso è la somma usuale).

$f_1(0) + f_1(1) = 2 + 2 = 4$
$f_2(0) + f_2(1) = 2 + 3 = 5$
$f_3(0) + f_3(1) = 3 + 2 = 5$
$f_4(0) + f_4(1) = 3 + 3 = 6$

ottieni che l'insieme dei risultati è ${4, 5, 6}$ che contiene solo $3$ elementi e non $4$. Perché sorge questa sorta di incongruenza? Perché concatenando rispettivamente i valori delle applicazioni $f_2$ e $f_3$ otteniamo lo stesso elemento (lo stesso tipo di ordine).

Come nel mio esempio può darsi che ad applicazioni diverse corrispondano tipi di ordine uguali, e se contiamo le applicazioni senza assicurarci che ad applicazioni diverse corrispondono ordini diversi sbagliamo ad effettuare il conteggio. Spero di essermi riuscito a spiegare.

[40rob]

Mi è venuta un'idea simile alla tua (che hai usato prima) che forse risolve il problema.
Usando il tuo tipo di notazione se consideriamo la concatenazione costituita da un numero di elementi numerabili

$\omega + n_0 + \omega^d + \omega + n_1 + \omega^d + \omega + n_2 + \omega^d +...$

e sostituiamo a piacere al posto degli $n_0, n_1, n_2...$ ordini di tipo $0$ e tipo $1$ otteniamo tipi di ordine diversi di sicuro; insomma a sequenze di $0$ e $1$ diverse corrispondono risultati delle rispettive concatenazioni diversi (questo punto però andrebbe dimostrato meglio perché lo afferro solo intuitivamente, dacci un'occhiata anche tu per vedere se è corretto). Siccome $(\mathbb{Q}, <)$ contiene tutti questi tipi di sottostrutture e siccome le le applicazioni $\mathbb{N} \to \{0, 1\}$ sono della potenza del continuo e quindi anche gli ordini ottenuti sono della potenza del continuo (perché ad applicazioni distinte, usando la concatenazione di sopra, corrispondono ordini distinti) abbiamo che il numero di sottostrutture divise per tipo di $(\mathbb{Q},<)$ è maggiore o uguale alla potenza del continuo (dato che contiene almeno tutte quelle che vengono fuori dalla concatenazione di sopra che sono della potenza del continuo). Siccome già sapevamo che le strutture distinte per tipo dovevano essere minori o uguali alla potenza del continuo, dalle due disuguaglianze deduciamo che devono coincidere a questa .

P. S. Citando quel che hai scritto prima

perplesso:La mia idea (tutta da dimostrare) è che l'ordine di un qualsiasi sottoinsieme di $QQ$ si possa ottenere concatenado fra loro i tipi $\omega, \omega^d, \rho$ ed $n$ con $n < \omega$ cioè creando sequenze (anche infinite) del tipo

$... + \omega +5 + \rho + \omega^d +2 + ....$

secondo me comunque nemmeno li riesci a rappresentare tutti i tipi di ordini dei sottoinsiemi di $\mathbb{Q}$ con questo stratagemma. Ad esempio con queste concatenazioni (ordinate come $(\mathbb{Z}, <)$) dei tipi fondamentali ($\{\omega, \omega^d, \rho\} \cup \{n: n < \omega\}$) non riesco a capire come potresti mai ottenere $\omega^2 + 1$

Cioé

$\omega,\omega,\omega,\omega,\omega...;1.$

Questo è un tipo di ordine contenuto tra le sottostrutture di $(\mathbb{Q}, <)$ ma che non credo possa venir fuori dalla tua costruzione.