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 <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: <[EMAIL PROTECTED]> >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" <[EMAIL PROTECTED]> >To: <[EMAIL PROTECTED]> >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 <[EMAIL PROTECTED]> > > >Reply-To: [EMAIL PROTECTED] > > >To: <[EMAIL PROTECTED]> > > >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" <[EMAIL PROTECTED]> > > >To: <[EMAIL PROTECTED]> > > >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 <[EMAIL PROTECTED]> > > > > >Reply-To: [EMAIL PROTECTED] > > > > >To: <[EMAIL PROTECTED]> > > > > >Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300 > > > > > > > > > >----- Original Message ----- > > > > >From: "Fernanda Medeiros" <[EMAIL PROTECTED]> > > > > >To: <[EMAIL PROTECTED]> > > > > >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 � <[EMAIL PROTECTED]> >========================================================================= _________________________________________________________________ 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 � <[EMAIL PROTECTED]> =========================================================================
