Suponha que A_{1}, A_{2}, \ldots, A_{n} seja um grupo de conjuntos. Suponha que R_{2}=A_{1} \oplus A_{2} e R_{k}=R_{k-1} \oplus A_{k} para k=3,4, \ldots, n. Use a indução matemática para demonstrar que x \in R_{n} se e somente se x pertencer a um número impar de conjuntos A_{1}, A_{2}, \ldots, A_{n}. (Lembre-se de que S \oplus T é a diferença simétrica dos conjuntos S e T definida na Seção 2.2.)

Passo 1

O enunciado define recursivamente
R_{2} = A_{1} \oplus A_{2}, \quad R_{k} = R_{k-1} \oplus A_{k}\quad (3\le k\le n),
onde S\oplus T é a diferença simétrica de S e T, isto é,
x\in S\oplus T \quad\Longleftrightarrow\quad \bigl[x\in S\text{ e }x\notin T\bigr]\;\text{ou}\;\bigl[x\notin S\text{ e }x\in T\bigr].
Queremos provar por indução em n que
x\in R_{n} \quad\Longleftrightarrow\quad x\text{ pertence a um número ímpar de conjuntos }A_{1},\dots,A_{n}.úí

Passo 2

(Base da indução: n=2.)
Por definição
R_{2}=A_{1}\oplus A_{2},
logo
x\in R_{2} \quad\Longleftrightarrow\quad \bigl[x\in A_{1},\,x\notin A_{2}\bigr]\;\text{ou}\;\bigl[x\notin A_{1},\,x\in A_{2}\bigr].
Isso significa exatamente que x está em exatamente um dos dois conjuntos A_{1},A_{2}, isto é, em um número ímpar (no caso, “um”) de conjuntos. Assim, a propriedade vale para n=2.

Passo 3

(Passo indutivo: hipótese.)
Suponha que, para algum k\ge3, valha
x\in R_{k-1} \quad\Longleftrightarrow\quad x\text{ pertence a um número ímpar de }A_{1},\dots,A_{k-1}.úí
Queremos mostrar que então
x\in R_{k} \quad\Longleftrightarrow\quad x\text{ pertence a um número ímpar de }A_{1},\dots,A_{k}.úí

Passo 4

(Indução propriamente dita.)
Pelo enunciado,
R_{k}=R_{k-1}\oplus A_{k},
logo, pela definição de \oplus,
x\in R_{k} \quad\Longleftrightarrow\quad \bigl[x\in R_{k-1},\,x\notin A_{k}\bigr] \;\text{ou}\; \bigl[x\notin R_{k-1},\,x\in A_{k}\bigr].
  • Se x\in R_{k-1} e x\notin A_{k}, pela hipótese indutiva x está em um número ímpar de A_{1},\dots,A_{k-1} e não conta em A_{k}, ficando assim em um número ímpar de conjuntos entre A_{1},\dots,A_{k}.
  • Se x\notin R_{k-1} e x\in A_{k}, então pela hipótese x está em um número par de A_{1},\dots,A_{k-1} e conta em A_{k}, somando um para dar um total ímpar em A_{1},\dots,A_{k}.
Assim, em ambos os casos x\in R_{k} ocorre exatamente quando o total de inclusões em A_{1},\dots,A_{k} é ímpar. Isso conclui o passo indutivo.

Resposta

Portanto, por indução matemática, para todo n\ge2 vale
x\in R_{n} \quad\Longleftrightarrow\quad x\text{ pertence a um número ímpar de conjuntos }A_{1},A_{2},\dots,A_{n}.úí

Exercícios de Livros Relacionados