Sec. 2.1 Conjuntos e relações27Uma sequência é uma coleção de elementos com uma ordem e que podeelementos com valor duplicado. Uma sequência também é às vezes chamada de tupla ou vec-tor. Em uma sequência, há um 0º elemento, um 1º elemento, um 2º elemento e assimsobre. Indico uma sequência usando colchetes angulares 〈〉 para incluir seus elementos. Páraexemplo, 〈3,4,5,4〉 é uma sequência. Observe que a sequência 〈3,5,4,4〉 é distinta deseqüência 〈3,4,5,4〉, e ambas são distintas da seqüência 〈3,4,5〉.Uma relação R sobre o conjunto S é um conjunto de pares ordenados de S. Como um exemplo de umrelação, se S é {a, b, c}, então{〈A, c〉, 〈b, c〉, 〈c, b〉}é uma relação, e{〈A, a〉, 〈a, c〉, 〈b, b〉, 〈b, c〉, 〈c, c〉}é uma relação diferente. Se tupla 〈x, y〉 está em relação a R, podemos usar uma notação infixaxRy. Freqüentemente relações como o operador menor que (<) no naturalnúmeros, que inclui pares ordenados como 〈1,3〉 e 〈2,23〉, mas não 〈3,2〉 ou〈2,2〉. Em vez de escrever o relacionamento em termos de pares ordenados, normalmenteuse uma notação infixa para tais relações, escrevendo 1 <3.Defina como propriedades das relações como segue, com R uma relação binária sobre o conjunto S.• R é reflexivo se aRa para todo a ∈ S.• R é simétrico se sempre que aRb, então bRa, para todo a, b ∈ S.• R é antissimétrico se sempre que aRb e bRa, então a = b, para todo a, b ∈ S.• R é transitivo se sempre que aRb e bRc, então aRc, para todo a, b, c ∈ S.Como exemplos, para os números naturais, <é anti-simétrico (porque hánenhum caso onde aRb e bRa) e transitivo; ≤ é reflexivo, anti-simétrico etransitivo e = é reflexivo, simétrico (e antissimétrico!) e transitivo. Párapessoas, a relação “é irmão de” é simétrica e transitiva. Se definirmos umpessoa a ser irmão de si mesma, então é reflexivo; se definir uma pessoa para não serum irmão de si mesmo, então não é reflexivo.R é uma relação de equivalência no conjunto S se for reflexiva, simétrica e transitiva.Uma relação de equivalência pode ser usada para particionar um conjunto em classes de equivalência. Sedois elementos aeb são equivalentes um ao outro, escrevemos a ≡ b. Uma partição deum conjunto S é uma coleção de subconjuntos que são separados uns dos outros e cuja uniãoé S. Uma relação de equivalência no conjunto S divide o conjunto em subconjuntos elementos elementossão equivalentes. Consulte a Seção 6.2 para uma discussão sobre como representar uma equivalênciaclasses em um conjunto. Uma aplicação para conjuntos disjuntos aparece na Seção 11.5.2.Exemplo 2.1 Para os inteiros, = é uma relação de equivalência que particionacada elemento em um subconjunto distinto. Em outras palavras, para qualquer inteiro a, trêsas coisas são verdadeiras.1. a = a,