Mostre que as seguintes funções definem distâncias em
(onde
e
):
(c) (Distância de Hamming)
(c) (Distância de Hamming)
Passo 1
O enunciado pede para mostrar que a função
define uma distância em
, onde
e
.\n
Informações dadas importantes:
Informações dadas importantes:
é o número de coordenadas em que
e
diferem (ou seja, a cardinalidade do conjunto
).\n
O que é preciso provar (as propriedades que caracterizam uma distância):\n
O que é preciso provar (as propriedades que caracterizam uma distância):\n
- Não negatividade: para todo
, .\n - Identidade dos indiscerníveis:
se, e somente se, .\n - Simetria: para todo
, .\n - Desigualdade triangular: para todo
, .\n
Passo 2
Prova da não negatividade e explicação da definição usada.\n
A função é a cardinalidade de um conjunto de índices. Vou explicar isso com calma.\n
O conjunto é formado por alguns índices entre
e
. A cardinalidade
é o número desses índices. Por definição, cardinalidade é um número inteiro maior ou igual a
(pois um conjunto não pode ter um número negativo de elementos). Portanto, para quaisquer
,
A função
O conjunto
Isto prova a não negatividade. Além disso, note que
é sempre um inteiro entre
e
, isto é,
mas isso é só uma observação adicional útil.
Passo 3
Prova da identidade dos indiscerníveis:
se e somente se
.\n
- Se
, então para todo temos . Assim o conjunto é o conjunto vazio , cuja cardinalidade é . Logo .\n - Reciprocamente, se
, então . A única forma de um conjunto ter cardinalidade zero é ser o conjunto vazio, então . Isso significa que não existe índice tal que ; em outras palavras, para todo temos . Assim .\n
Portantoacontece exatamente quando .
Passo 4
Prova da simetria:
.\n
Observe que a propriedade “ ” é simétrica em
e
:
se, e somente se,
. Logo os conjuntos
Observe que a propriedade “
são iguais, e portanto têm a mesma cardinalidade. Isso dá
Passo 5
Prova da desigualdade triangular: para todo
vale
Ideia intuitiva: se em uma coordenada
temos
, então ao passar de
para
necessariamente houve mudança em
em pelo menos um dos passos
ou
. Formalizo isso usando inclusão de conjuntos.\n
Considere os conjuntos
Considere os conjuntos
Vou mostrar que
. Tomemos um índice
. Então
. Se, por absurdo,
, isso significa que
e
, isto é,
e
. Mas se
e
então
, o que contradiz
. Logo não é possível
; portanto
. Como
em
era arbitrário, deduzimos
.\n
Da inclusão de conjuntos segue a desigualdade entre cardinalidades:
Da inclusão de conjuntos segue a desigualdade entre cardinalidades:
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,
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 definida por
Mostramos as quatro propriedades exigidas: não negatividade, identidade dos indiscerníveis, simetria e desigualdade triangular. Portanto
é uma distância em
.\n
Exemplo rápido para fixar: em , se
,
e
, então
Exemplo rápido para fixar: em
e de fato
.