[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>
=========================================================================