© Seja X um conjunto com |X|=n. Prove que se n é ímpar, então para todo A subset X,|A| e |A^c| tem paridades diferentes e que portanto, a aplicação Phi(A)=A^c é uma bijeção da coleção de subconjuntos de X de cardinalidade par para a coleção de subconjuntos de X de cardinalidade ímpar.

Passo 1

Beleza, vamos resolver esse exercício juntos! O problema fala sobre conjuntos e suas contagens. A gente tem um conjunto com , onde é ímpar. A gente precisa provar duas coisas:
  1. Para todo subconjunto de , os tamanhos de e de seu complementar têm paridades diferentes (ou seja, um tem tamanho par e o outro ímpar).
  2. A aplicação cria uma correspondência um a um (bijeção) entre todos os subconjuntos de com tamanho par e os com tamanho ímpar.
Vamos precisar entender conceitos básicos de conjuntos, complementos e paridade de números.

Passo 2

Primeiro, vamos entender o que significa o complementar de A^c = x in X mid x notin A , que é . O complementar contém todos os elementos de que não estão em . Matematicamente, isso é escrito como:
Isso nos ajuda a relacionar os tamanhos de e .

Passo 3

Sabemos que o total de elementos em |A| + |A^c| = |X| = n é , então:
Como é ímpar, queremos mostrar que e t��m paridades diferentes.

Passo 4

Vamos supor que |A^c| = n - |A| = n - 2k seja par. Então, podemos escrever |A^c| = n - |A| = n - (2k + 1) = (n - 1) - 2k para algum inteiro . Então:
Como é ímpar e é par, a diferença será ímpar.
Agora, se for ímpar, ou seja, , então:
Como é ímpar, é par, e subtraindo (que também é par) o resultado será par.

Passo 5

Portanto, mostramos que se é par, então é ímpar, e vice-versa. Isso significa que a aplicação troca subconjuntos de par cardinalidade para ímpar e de ímpar para par.

Passo 6

Para mostrar que é uma bijeção, precisamos mostrar que ela é injetora e sobrejetora.
  • Injetora: Se , então . Tomando o complementar de ambos os lados, temos . Então, é injetora.
  • Sobrejetora: Para qualquer subconjunto com cardinalidade ímpar, existe um subconjunto com cardinalidade par tal que . Então, é sobrejetora.
Assim, é uma bijeção.

Resposta

A aplicação é uma bijeção entre os subconjuntos de com cardinalidade par e os de cardinalidade ímpar quando é ímpar.

Exercícios relacionados