Mostre que as seguintes funções definem distâncias em \mathbb{R}^{n} (onde x=\left(x_{1}, \ldots, x_{n}\right) e y=\left(y_{1}, \ldots, y_{n}\right) ):
(c) (Distância de Hamming)
d(x, y):=\left|\left\{i \mid x_{i} \neq y_{i}\right\}\right|

Passo 1

O enunciado pede para mostrar que a função
d(x,y):=\left|\left\{i \mid x_{i}\neq y_{i}\right\}\right|
define uma distância em \mathbb{R}^{n}, onde x=(x_{1},\dots,x_{n}) e y=(y_{1},\dots,y_{n}).\n
Informações dadas importantes:
d(x,y)
é o número de coordenadas em que x e y diferem (ou seja, a cardinalidade do conjunto \{i\mid x_i\neq y_i\}).\n
O que é preciso provar (as propriedades que caracterizam uma distância):\n
  1. Não negatividade: para todo x,y, d(x,y)\ge 0.\n
  2. Identidade dos indiscerníveis: d(x,y)=0 se, e somente se, x=y.\n
  3. Simetria: para todo x,y, d(x,y)=d(y,x).\n
  4. Desigualdade triangular: para todo x,y,z, d(x,z)\le d(x,y)+d(y,z).\n

Passo 2

Prova da não negatividade e explicação da definição usada.\n
A função d(x,y) é a cardinalidade de um conjunto de índices. Vou explicar isso com calma.\n
O conjunto \{i\mid x_i\neq y_i\} é formado por alguns índices entre 1 e n. A cardinalidade \left|\{i\mid x_i\neq y_i\}\right| é o número desses índices. Por definição, cardinalidade é um número inteiro maior ou igual a 0 (pois um conjunto não pode ter um número negativo de elementos). Portanto, para quaisquer x,y,
d(x,y)=\left|\{i\mid x_i\neq y_i\}\right|\ge 0.
Isto prova a não negatividade. Além disso, note que d(x,y) é sempre um inteiro entre 0 e n, isto é,
0\le d(x,y)\le n,
mas isso é só uma observação adicional útil.

Passo 3

Prova da identidade dos indiscerníveis: d(x,y)=0 se e somente se x=y.\n
  • Se x=y, então para todo i temos x_i=y_i. Assim o conjunto \{i\mid x_i\neq y_i\} é o conjunto vazio \varnothing, cuja cardinalidade é 0. Logo d(x,y)=0.\n
  • Reciprocamente, se d(x,y)=0, então \left|\{i\mid x_i\neq y_i\}\right|=0. A única forma de um conjunto ter cardinalidade zero é ser o conjunto vazio, então \{i\mid x_i\neq y_i\}=\varnothing. Isso significa que não existe índice i tal que x_i\neq y_i; em outras palavras, para todo i temos x_i=y_i. Assim x=y.\n
    Portanto d(x,y)=0 acontece exatamente quando x=y.

Passo 4

Prova da simetria: d(x,y)=d(y,x).\n
Observe que a propriedade “ x_i\neq y_i” é simétrica em x e y: x_i\neq y_i se, e somente se, y_i\neq x_i. Logo os conjuntos
\{i\mid x_i\neq y_i\}\quad\text{e}\quad\{i\mid y_i\neq x_i\}
são iguais, e portanto têm a mesma cardinalidade. Isso dá
d(x,y)=\left|\{i\mid x_i\neq y_i\}\right|=\left|\{i\mid y_i\neq x_i\}\right|=d(y,x).

Passo 5

Prova da desigualdade triangular: para todo x,y,z vale
d(x,z)\le d(x,y)+d(y,z).\n
Ideia intuitiva: se em uma coordenada i temos x_i\neq z_i, então ao passar de x para z necessariamente houve mudança em i em pelo menos um dos passos x\to y ou y\to z. Formalizo isso usando inclusão de conjuntos.\n
Considere os conjuntos
A:=\{i\mid x_i\neq z_i\},
B:=\{i\mid x_i\neq y_i\},
C:=\{i\mid y_i\neq z_i\}.
Vou mostrar que A\subseteq B\cup C. Tomemos um índice i\in A. Então x_i\neq z_i. Se, por absurdo, i\notin B\cup C, isso significa que i\notin B e i\notin C, isto é, x_i=y_i e y_i=z_i. Mas se x_i=y_i e y_i=z_i então x_i=z_i, o que contradiz i\in A. Logo não é possível i\notin B\cup C; portanto i\in B\cup C. Como i em A era arbitrário, deduzimos A\subseteq B\cup C.\n
Da inclusão de conjuntos segue a desigualdade entre cardinalidades:
|A|\le |B\cup C|\le |B|+|C|.
A última desigualdade é a propriedade elementar de cardinalidade de união (a cardinalidade da união é no máximo a soma das cardinalidades; aqui podemos usar isso sem complicar). Substituindo os nomes originais,
d(x,z)=|A|\le |B|+|C|=d(x,y)+d(y,z).
Isso prova a desigualdade triangular.

Passo 6

Resumo final e pequena ilustração prática.\n
Mostramos as quatro propriedades exigidas: não negatividade, identidade dos indiscerníveis, simetria e desigualdade triangular. Portanto d definida por
d(x,y):=\left|\{i\mid x_i\neq y_i\}\right|
é uma distância em \mathbb{R}^n.\n
Exemplo rápido para fixar: em \mathbb{R}^3, se x=(1,2,3), y=(1,5,3) e z=(7,5,0), então
d(x,y)=1,\quad d(y,z)=2,\quad d(x,z)=3,
e de fato 3=d(x,z)\le d(x,y)+d(y,z)=1+2=3.

Resposta

d é uma distância em \mathbb{R}^{n}.

Exercícios relacionados