Suponha que
seja um grupo de conjuntos. Suponha que
e
para
,
. Use a indução matemática para demonstrar que
se e somente se
pertencer a um número impar de conjuntos
. (Lembre-se de que
é a diferença simétrica dos conjuntos
e
definida na Seção 2.2.)
Passo 1
O enunciado define recursivamente
onde
é a diferença simétrica de
e
, isto é,
Queremos provar por indução em
que
Passo 2
(Base da indução:
.)
Por definição
Por definição
logo
Isso significa exatamente que
está em exatamente um dos dois conjuntos
, isto é, em um número ímpar (no caso, “um”) de conjuntos. Assim, a propriedade vale para
.
Passo 3
(Passo indutivo: hipótese.)
Suponha que, para algum , valha
Suponha que, para algum
Queremos mostrar que então
Passo 4
(Indução propriamente dita.)
Pelo enunciado,
Pelo enunciado,
logo, pela definição de
,
- Se
e , pela hipótese indutiva está em um número ímpar de e não conta em , ficando assim em um número ímpar de conjuntos entre . - Se
e , então pela hipótese está em um número par de e conta em , somando um para dar um total ímpar em .
Assim, em ambos os casos
ocorre exatamente quando o total de inclusões em
é ímpar. Isso conclui o passo indutivo.
Resposta
Portanto, por indução matemática, para todo
vale