Una funzione f da Z in S

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Una funzione f da Z in S

Messaggio da jordan » 13 nov 2009, 05:28

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)
The only goal of science is the honor of the human spirit.

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 14 nov 2009, 11:56

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 :oops:
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

fph
Site Admin
Messaggi: 3693
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 14 nov 2009, 13:27

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:)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

fede90
Messaggi: 287
Iscritto il: 04 apr 2007, 21:36
Località: Udine

Messaggio da fede90 » 14 nov 2009, 17:19

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
Bene, prendiamo un pentagono di [tex]$n$[/tex] lati...

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 14 nov 2009, 18:05

fph ha scritto:@Jordan: ma mi sfugge qualcosa o ci stai semplicemente chiedendo di dimostrare che un sottoinsieme dei razionali è numerabile?:shock:
Infatti il problema è molto semplice :lol:

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) $. :o
The only goal of science is the honor of the human spirit.

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 14 nov 2009, 19:35

jordan ha scritto: Infatti il problema è molto semplice :lol:
Questo dipende dalle nozioni che si hanno su questo argomento...e le mie sono nulle quindi per me è moolto difficile :lol:

@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 :roll:

@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 8)
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

fph
Site Admin
Messaggi: 3693
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 16 nov 2009, 18:24

Maioc92 ha scritto:
jordan ha scritto: Infatti il problema è molto semplice :lol:
Questo dipende dalle nozioni che si hanno su questo argomento...e le mie sono nulle quindi per me è moolto difficile :lol:
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.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 16 nov 2009, 18:49

questo teorema è una figata :shock:
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!!!
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

Avatar utente
Ani-sama
Messaggi: 418
Iscritto il: 19 feb 2006, 21:38
Località: Antwerpen (BE)
Contatta:

Messaggio da Ani-sama » 16 nov 2009, 18:59

jordan ha scritto:[...] ma comunque è sufficiente (senonchè banale) notare che $ S \subseteq \mathbb{Q} \cap (0,1) $. :o
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!
...

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 16 nov 2009, 19:36

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.. :o (quella citata da te infatti non era una dimostrazione :wink: )
The only goal of science is the honor of the human spirit.

Rispondi