Una funzione f da Z in S

[jordan]

Sia definita il (minimo) insieme S tale che $ \frac{1}{2} \in S $ e se $ x \in S $ allora $ \frac{1}{1+x} \in S $ e $ \frac{x}{x+1} \in S $.

Mostrare che esiste una funzione bigettiva $ f(\cdot):\mathbb{Z} \to S $.

(Indonesia TST)

[Maioc92]

allora, se non ho sbagliato qualcosa si dimostra per induzione estesa che $ S:={x\in\mathbb Q|0<x<1} $.
Ora purtroppo viene la parte difficile, ovvero trovare una funzione bigettiva da Z a S, e poichè io non conosco praticamente nulla sull'argomento cardinalità degli insiemi, non sono sicuro che questa parte sia corretta, comunque la scrivo lo stesso.
Innanzitutto trovo una funzione bigettiva da N a S: per farlo definisco una permutazione $ a_n $ degli elementi di S che rispetti le seguenti 3 proprietà:
-$ a_n\in S $ per ogni n
-Dati $ a_k=\frac m n $ e $ a_i=\frac p q $ (ovviamente m,n coprimi e p,q coprimi), se $ n>q $, allora $ k>i $
-Dati $ a_k=\frac m p $ e $ a_i=\frac n p $ (come prima m,p coprimi e n,p coprimi), se $ m>n $ allora $ k>i $

Ora definisco una funzione $ f:\mathbb N\rightarrow S $ tale che $ f(n)=a_n $,che è chiaramente bigettiva per come ho definito $ a_n $.
A questo punto mi rimane da trovare una funzione bigettiva $ g:\mathbb Z\rightarrow \mathbb N $, che definisco nel modo seguente:
-$ g(0)=1 $
-$ g(x)=2x $ se $ x>0 $
-$ g(x)=-2x+1 $ se $ x<0 $
A questo punto la funzione $ f(g(x)) $ è bigettiva da Z a S, e quindi ho concluso.

Forse ho scritto cose del tutto errate, però come ho detto all'inizio conosco poco e niente dell'argomento cardinalità, per cui scusate in anticipo se ho scritto fesserie

[fph]

Nice try, ma la tua permutazione a_n è definita male. Perché... beh, perché quella non è una definizione. Tu hai definito un /ordinamento/, non una permutazione. Poi hai detto che prendendo tutti gli elementi dell'ordinamento dal primo all'ultimo si fa una permutazione. Questo non funziona: l'esempio più semplice in cui va male qualcosa è il seguente: considera il seguente ordinamento "$ \curlyeqsucc $" dei numeri naturali:
-se a pari e b dispari, $ a\curlyeqsucc b $,
-se a e b entrambi pari o dispari, $ a \curlyeqsucc b $ sse $ a>b $.
O anche, informalmente parlando: "prima metti i dispari, in ordine crescente, poi quando hai finito (?!?!) metti i pari, sempre in ordine crescente".
Come fai ora a "estrarre una permutazione" mettendoli tutti in fila?

(@Jordan: ma mi sfugge qualcosa o ci stai semplicemente chiedendo di dimostrare che un sottoinsieme dei razionali è numerabile?:shock:)

[fede90]

Giusto per curiosità:

British Mathematical Olympiad, 2004/2005, Round 1, Problem 5:

Let $ $S$ $ be a set of rational numbers with the following properties:
i) $ $1\in S$ $;
ii) If $ $x \in S$ $, then both $ $\frac{1}{x+1} \in S $ $ and $ $\frac{x}{x+1} \in S$ $.
Prove that $ $S$ $ contains all rational numbers in the interval $ $ 0 < x < 1$ $.

Link

[jordan]

@Jordan: ma mi sfugge qualcosa o ci stai semplicemente chiedendo di dimostrare che un sottoinsieme dei razionali è numerabile?:shock:

Infatti il problema è molto semplice

Non sapevo che un problema simile fosse stato dato anche alle nazionali inglesi, ma comunque è sufficiente (senonchè banale) notare che $ S \subseteq \mathbb{Q} \cap (0,1) $.

[Maioc92]

Infatti il problema è molto semplice

Questo dipende dalle nozioni che si hanno su questo argomento...e le mie sono nulle quindi per me è moolto difficile

@fph:si, immaginavo ci fosse qualcosa che non andava. Quando c'è di mezzo l'infinito non puoi mai dare nulla per scontato purtroppo. Comunque ci ho provato

@fede90:quello invece è alla mia portata e infatti l'ho dimostrato per induzione estesa sui denominatori. Ora guardo il link che hai messo e se la soluzione che compare è diversa allora posto qui la mia, altrimenti è inutile scrivere 2 volte la stessa soluzione

EDIT:ho guardato le soluzioni nel link, e quella nel terzo messaggio praticamente riflette la mia....comunque se a qualcuno interessa quando ho tempo la riscrivo in italiano

[fph]

Infatti il problema è molto semplice

Questo dipende dalle nozioni che si hanno su questo argomento...e le mie sono nulle quindi per me è moolto difficile

Già. E' uno di quei problemi che non andrebbero mai dati in un'olimpiade perché sono banali per uno che sa la teoria e il teoremone di turno, ma difficili e time-consuming per tutti gli altri.

[Maioc92]

questo teorema è una figata
Quindi mi basta dire che esiste $ f:S\rightarrow \mathbb N $ iniettiva (ad esempio $ f(\frac m n)=n^2+m $ e $ f:\mathbb N\rightarrow S $ iniettiva (ad esempio $ f(n)=\frac 1 n $) e ho finito!!!

[Ani-sama]

[...] ma comunque è sufficiente (senonchè banale) notare che $ S \subseteq \mathbb{Q} \cap (0,1) $.

Uhm, detto così, direi di no. Cioè, magari hai che $ S $ è un insieme finito, e allora tanti saluti alla bigezione con $ \mathbb Z $... Certo, poi io credo che la cosa si sistemi senza troppa fatica, però va pur sempre sistemata!

[jordan]

Intendi dire che $ |S|=\infty $? Preso un elemento $ x \in (0,1) $ che sta in $ S $ allora $ x>\frac{x}{x+1} $, e puoi ripeterlo infinite volte.. (quella citata da te infatti non era una dimostrazione )