[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] violencia e axioma da escolha
O axioma da escolha pode ser enunciado com ou sem a hip�tese dos conjuntos
serem disjuntos. As duas formas s�o equivalentes, pois, se n�o forem
disjuntos, voce pode disjunt�-los (usando produto cartesiano).
Para usar a fun��o escolha que voce falou, precisa que o conjunto de
bandidos seja enumer�vel. De fato, basta que esse conjunto possa ser bem
ordenado (todo subconjunto tem menor elemento) para voce usar essa fun��o
escolha. Mas o axioma da boa ordem, que diz que todo conjunto pode ser bem
ordenado, � equivalente ao axioma da escolha (uma das implica��es �
exatamente o que voce fez).
>From: Vinicius Jos� Fortuna <vinicius.fortuna@ic.unicamp.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: <obm-l@mat.puc-rio.br>
>Subject: Re: [obm-l] violencia e axioma da escolha
>Date: Mon, 9 Sep 2002 17:16:26 -0300
>
>N�o sei se entendi direito, mas, ao meu ver, n�o ter�amos conjuntos dois a
>dois disjuntos e tal propriedade � necess�ria para aplicar o axioma da
>escolha (ou n�o?).
>
>De qualquer forma, n�o poder�amos mapear os bandidos nos n�meros inteiros?
>Assim ter�amos uma fun��o de escolha que pegaria em C o bandido mapeado no
>menor inteiro tal que satisfa�a aquelas condi��es para entrar em R. Se
>temos
>uma fun��o de escolha ent�o podemos escolh�-los independentemente do axioma
>da escolha.
>
>Agrade�o esclarecimentos
>
>Vinicius Fortuna
>
>----- Original Message -----
>From: "Rogerio Fajardo" <rogeriofajardo@hotmail.com>
>To: <obm-l@mat.puc-rio.br>
>Sent: Monday, September 09, 2002 12:08 PM
>Subject: Re: [obm-l] violencia
>
>
> > Ol�, Vinicius
> >
> > Cada vez que voce "retira um elemento de C" e coloca em R, na verdade
>voce
> > mudou o conjunto C. Ou seja, cada escolha que voce fez, no processo
> > indutivo, foi sobre um conjunto diferente. � semelhante a demonstra��o
>de
> > que todo conjunto infinto possui um subconjunto enumer�vel, em que, dado
>um
> > conjunto V, constru�mos indutivamente um conjunto S colocando nele, a
>cada
> > passo, um elemento de V que n�o est� em S, usando o Axioma da Escolha
> >
> >
> > >From: Vinicius Jos� Fortuna <vinicius.fortuna@ic.unicamp.br>
> > >Reply-To: obm-l@mat.puc-rio.br
> > >To: <obm-l@mat.puc-rio.br>
> > >Subject: Re: [obm-l] violencia
> > >Date: Sun, 8 Sep 2002 18:41:45 -0300
> > >
> > >Oi Rog�rio
> > >Acho que n�o saquei. Em que momento foi utilizado o axioma da escolha?
>Eu
> > >nem tinha infinitos conjuntos! Apenas conjuntos infinitos.
> > >
> > >At� mais
> > >
> > >Vinicius
> > >
> > >----- Original Message -----
> > >From: "Rogerio Fajardo" <rogeriofajardo@hotmail.com>
> > >To: <obm-l@mat.puc-rio.br>
> > >Sent: Sunday, September 08, 2002 2:17 PM
> > >Subject: Re: [obm-l] violencia
> > >
> > >
> > > > � bom notar que essa solu��o usa o axioma da escolha (de infinitos
> > >conjuntos
> > > > n�o-vazios, escolhemos um elemento de cada). � essencial o axioma da
> > >escolha
> > > > para resolv�-lo?
> > > >
> > > >
> > > > >From: Vinicius Jos� Fortuna <vinicius.fortuna@ic.unicamp.br>
> > > > >Reply-To: obm-l@mat.puc-rio.br
> > > > >To: <obm-l@mat.puc-rio.br>
> > > > >Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300
> > > > >
> > > > >----- Original Message -----
> > > > >From: "Fernanda Medeiros" <femedeiros2001@hotmail.com>
> > > > >To: <obm-l@mat.puc-rio.br>
> > > > >Sent: Saturday, September 07, 2002 8:45 PM
> > > > >Subject: [obm-l] violencia
> > > > >
> > > > >
> > > > > > Ol�,
> > > > > > algu�m pode dar uma ajuda nestas quest�es?
> > > > > > 1.a)uma "gang" tem infinitos bandidos e cada um dos meliantes
>tem
>um
> > > > >�nico
> > > > > > inimigo no interior da "gang",que ele quer matar.Prove q �
>possivel
> > > > >reunir
> > > > > > uma quantidade infinita de bandidos desta "gang", semq haja o
> > >risco
> > >de
> > > > >q
> > > > > > um bandido mate outro durante a reuni�o.
> > > > >
> > > > >Pense no seguinte algoritmo:
> > > > >Temos o conjunto C de candidatos � reuni�o que inicialmente cont�m
> > >todos
> > >os
> > > > >infinitos bandidos da gangue.
> > > > >Temos o conjunto R de bandidos selecionados para a reuni�o que
> > >inicialmente
> > > > >est� vazio.
> > > > >
> > > > >A cada passo do algoritmo procuramos em C algu�m que n�o que matar
> > >ningu�m
> > > > >de R e ningu�m em R quer mat�-lo.
> > > > >Seja M o subconjunto de C de bandidos que pelo menos um de R quer
> > >matar.
> > > > >Como cada bandido de R s� quer matar um, |M|<=|R|
> > > > >Ent�o, como R � finito, M ser� finito e V=C-M ser� infinito, pois C
>�
> > > > >infinito.
> > > > >V ser� o subconjunto de C dos bandidos que ningu�m de R quer matar.
> > > > >Em V procuramos um bandido que n�o quer matar ningu�m de R,
>retiramos
> > >ele
> > > > >de
> > > > >C, o inserimos em R e repete-se o processo.
> > > > >
> > > > >Se sempre for poss�vel encontrar tal bandido, o processo se
>repetir�
> > > > >indefinidamente e com R sempre crescendo. Assim teremos infnitos
> > >bandidos
> > > > >na
> > > > >reuni�o sem derramamento de sangue.
> > > > >
> > > > >Se em algum momento n�o for poss�vel encontrar um bandido em V, �
> > >porque
> > > > >todos os bandidos de V querem matar algu�m de R. Ou seja, ningu�m
>de
>V
> > >quer
> > > > >matar outro de V. Pegamos, ent�o, V como o conjunto de bandidos
>para
>a
> > > > >reuni�o. Como V � infinito, teremos infinitos participantes na
>reuni�o.
> > > > >
> > > > > > b)Se cada bandido tiver um n� finito mas indefinido de
>inimigos(um
> > > > >bandido
> > > > > > pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e
> > >assim
> > > > >por
> > > > > > diante).Ser� sempre possivel promover uma reuni�o com infinitos
> > >bandidos
> > > > >sem
> > > > > > risco de derramamento de sangue?
> > > > >N�o � poss�vel. Existe um contra-exemplo:
> > > > >Ordene os bandidos formando uma sequ�ncia. Imagine que cada bandido
> > >quer
> > > > >matar todos que v�m antes dele na sequ�ncia. Nunca poderemos ter
>dois
> > > > >bandidos 'a' e 'b' na reuni�o, pois ou a vem antes de b, ou b vem
>antes
> > >de,
> > > > >assim haver� um que vai querer matar o outro. Ent�o s� poderemos
>ter
>um
> > > > >bandido na reuni�o.
> > > > >
> > > > >At� mais
> > > > >
> > > > >Vinicius Fortuna
> > > > >IC-Unicamp
>
>
>=========================================================================
>Instru��es para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>O administrador desta lista � <nicolau@mat.puc-rio.br>
>=========================================================================
_________________________________________________________________
Chat with friends online, try MSN Messenger: http://messenger.msn.com
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista � <nicolau@mat.puc-rio.br>
=========================================================================