A ordem através da diferença simétrica

Deniel Correa de AlmeidaUniversidade Federal do Amapá

E-mail: dn-el@hotmail.com, dn-el@msn.com

Palavras-chave: Matemática discreta, ordenação, diferença simétrica.

Resumo: Este trabalho objetiva apresentar uma nova relação de ordem no conjunto das partes deconjuntos discretos limitados inferiormente e totalmente ordenado, esta ordenação é construída atravésda Diferença Simétrica entre conjuntos, e pode ser usadas em algoritimos de ordenação.

1 Introdução

Em todo o trabalho usaremos a definição de diferença simétrica como segue abaixo:

Definição 1.1 (Diferença Simétrica) Dados dois conjuntos X e Y chama-se diferença simétrica dosconjuntos X e Y ao conjunto de todos os elementos que pertencem a um e somente um dos conjuntos Xe Y , o qual denotamos por X 4 Y , em símbolos temos:

X 4 Y = (X − Y ) ∪ (Y −X). (1)

O conjunto dos números naturais N é totalmente ordenado com a relação de ordem usual “≥”, usaremosestá relação juntamente com a definição (1.1) para ordenar todos os subconjunto de N, isto é, criar umaordem linear no conjunto das partes de N, o qual denotaremos por P(N).Dados dois subconjuntos distintos X e Y de N com pelo menos um dos conjuntos sendo não vazio,tem-se que X 4 Y 6= ∅, com isto, corroborado por pelo princípio da boa ordenação visto em [4] fazsentido tomar o ínfimo1 de X4Y , e tal número natural pertence exclusivamente a X ou Y , deste modo,podemos então definir a seguinte relação binária em P(N):

X ∼1 Y ⇔ inf(X 4 Y ) ∈ X. (2)

segue que a relação (2) é irreflexiva, pois X4X = ∅ para todo X ∈ P(N), isto é, X 6∼1 X , diante distodefinamos outra relação binária

X ∼2 Y ⇔

X ∼1 Y se X 4 Y 6= ∅

ouX = Y.

(3)

Agora obtemos que (3) é uma relação reflexiva em P(N), como o conjunto vazio não possui ínfimo,certamente não existe inf(X 4 Y ) se X = Y , com isto, logicamente podemos denotar a relação (3) daseguinte forma:

Definição 1.2 Dados X e Y em P(N), definamos a seguinte relação

X < Y ⇔ inf(X 4 Y ) /∈ Y, (4)

neste caso dizemos que X é maior ou igual que Y .1Podemos tomar o mínimo em vez de ínfimo, pois em conjuntos discretos são equivalentes ínfimo e mínimo

ISSN 2317-3289

66

Vamos denotar (2) assim como fizemos com (3), isto é;

Definição 1.3 Dados X e Y em P(N), definamos a seguinte relação:

X � Y ⇔ inf(X 4 Y ) ∈ X, (5)

neste caso dizemos que X é maior que Y .

As relações (3) e (5) tem apenas a mudança de notação, muda-se o símbolo “∼1” por “�”, enquanto que(2) e (4) essa mudança de notação não é apenas uma troca do símbolo “∼2” por “<”, e sim um reajustenos argumentos lógicos da sentença, o que resulta na equivalência das relações (2) e (4), de fato, X < Yse, e somente se, inf(X 4 Y ) /∈ X , isto é, inf(X 4 Y ) ∈ Y ou X 4 Y = ∅ o que é equivalente aX ∼1 Y ou X = Y .

Temos da relação (4) que X < Y se, e somente se, X � Y ou X = Y , ou seja, quaisquer doiselementos de P(N) podem ser comparados com a relação (4).

2 Propriedades

Agora segue as propriedades da relação (4), justamente o que caracteriza o conjunto P(N) como umconjunto totalmente ordenado, primeiramente o resultado que prova que a relação (4) é uma relação deordem.

Teorema 2.1 A relação binária (4) é uma relação de ordem total em P(N).

Prova: Para mostrar que (4) é uma relação de ordem total, devemos provar primeiramente que é umarelação de ordem parcial, isto é, deve ser antissimétrica, reflexiva e transitiva:

Reflexiva: Considere X ∈ P(N) vamos mostrar que X < X , de fato, como X 4 X = ∅ , logo nãoexiste inf(X 4X) , em particular inf(X 4X) /∈ X , ou seja, X < X;

Antissimétrica: Considere X e Y em P(N) tal que X < Y e Y < X , devemos mostrar que X = Y ,segue da definição de (4) que

X < Y ⇔ inf(X 4 Y ) /∈ Y

Y < X ⇔ inf(Y 4X) /∈ X

daí concluimos que não existe inf(X4Y ) /∈ X ∪Y , ou seja, inf(Y 4X) /∈ X4Y , resultandoque X 4 Y = ∅, de onde segue que X = Y ;

Transitividade : Considere os subconjuntos X , Y e Z pertencentes a P(N), tal que X < Y e Y < Zdevemos mostrar que X < Z.Por hipótese X < Y e Y < Z, isto é, X é maior ou igual que Y e Y é maior ou igual que Z,se tivermos algumas das igualdades, X = Y ou Y = Z então o resultado seria óbvio, de fato, seX = Y então X = Y < Z, e análogo se Y = Z, teriamos X < Z = Y , suponha então que nãoocorre as igualdades anteriores, isto é, X � Y e Z � Y , então existem x0, y0 ∈ N tal que

x0 = inf(X 4 Y ) ∈ X (6)

y0 = inf(Y 4 Z) ∈ Y (7)

pela tricotomia dos números naturais vamos dividir em três casos para terminar a prova da transi-tividade:

caso x0 = y0: Por (6) e (7) temos que

x0 ≤ x, ∀x ∈ X 4 Y (8)

y0 ≤ x, ∀x ∈ Y 4 Z (9)

ISSN 2317-3289

67

pelo fato de x0 = y0, segue que

x0 = y0 < x, ∀x ∈ (X 4 Y ) ∪ (Y 4 Z) (10)

em particular

x0 = y0 ≤ x, ∀x ∈ (X 4 Z) ⊂ (X 4 Y ) ∪ (Y 4 Z), (11)

como y0 /∈ Z e seguindo de (6), temos que x0 ∈ X , portanto segue que y0 = x0 ∈ X 4 Z, daítemos que x0 = inf(X 4 Z) ∈ X, ou seja, x0 = inf(X 4 Z) /∈ Z, isto é, X < Z

caso x0 < y0: Usando a hipótese do caso, juntamente com (6) e (7) resulta que

x0 ≤ x, ∀x ∈ (X 4 Y ) ∪ (Y 4 Z)

particulamente temos

x0 ≤ x, ∀x ∈ (X 4 Z) ⊂ (X 4 Y ) ∪ (Y 4 Z) (12)

como x0 ∈ X , então x0 /∈ Z, com efeito, se x0 ∈ Z, segue do fato de x0 /∈ Y que x0 ∈ Y 4 Z,mas x0 < y0 = inf(Y 4 Z), o que é uma contradição, logo x0 /∈ Z e daí x0 ∈ X 4 Z, e (12)resulta que x0 = inf(X 4 Z) ∈ X , ou seja, x0 = inf(X 4 Z) /∈ Z, isto é, X < Z

caso x0 > y0: Segue de (6) e (7) e da hipótese do caso que

y0 ≤ x, ∀x ∈ (X 4 Z) ⊂ (X 4 Y ) ∪ (Y 4 Z), (13)

devemos mostrar que y0 = inf(X 4 Z) ∈ X , para isto, basta notar que y0 ∈ X . De fato, sey0 /∈ X segue de (7) que y0 ∈ X 4 Y , mas como y0 < x0 = inf(X 4 Y ) tem-se um absurdo,portando y0 ∈ X , daí y0 ∈ X 4 Z, pois y0 /∈ Z, segue de (13) que y0 = inf(X 4 Z) ∈ X , ouseja, y0 = inf(X 4 Z) /∈ Z, isto é, X < Z. Vimos que em qualquer um dos três caso, sempretemos X < Z, o que mostra que a relação (4) é transitiva, e portanto uma relação de ordem parcial,como todos os elementos de P(N) são comparáveis, então (4) em uma relação ordem é total.

Q.E.D

Teorema 2.2 Dados X e Y em P(N), se min{X} < min{Y } então X � Y .

Teorema 2.3 Dados X e Y em P(N), se X < Y então min{X} ≤ min{Y }.

A recíproca dos teoremas 2.2 e 2.3 não é verdadeira, de fato, considere X = {1, 3, 2, 4} e Y = {1, 2, 3},daí temos

X � Y ; min{X} < min{Y },

min{X} = min{Y }; Y � X.

A relação de ordem (4) generaliza a relação de ordem parcial dada pela inclusão de conjuntos, comoveremos no seguinte resultado.

Teorema 2.4 Dados X e Y em P(N), se X ⊇ Y então X < Y .

Teorema 2.5 A ordem em P(N) é densa.

Teorema 2.6 A ordem em P(N) é Completa.

ISSN 2317-3289

68

Teorema 2.7 A função d : P(N)XP(N) −→ R+ definida por

d(X, Y ) =∑

n∈X4Y

an

é uma métrica, para toda sequencia {an}n∈N ⊂ R+, tal que

∞∑n=1

an <∞

Definição 2.1 Considere o conjunto X , dizemos que a classe de subconjuntos

〈X〉] = {A ⊂ X : card(X) = card(A)}

é a classe cardinalidade de X

Corolário 2.1 Se Y ∈ 〈X〉] então X < Y .

3 Considerações

A ordenação continua valendo se trocarmos N por outro conjunto discreto ordenado e limitado inferi-ormente(DOLI), mais ainda, pode-se ordenar com (4) a toda classe de subconjuntos (DOLI), atentandopara os teoremas (2.5) e (2.6) que em geral que não valem se o conjunto (DOLI) for finito. Considereo seguinte conjunto D = {X ⊂ Z : inf(X) ∈ Z}, temos que D é uma generalização do conjuntoondenado (P(N), <), visto que P(N) ⊂ D.

Em ciência da computação dada uma sequência de n dados <a1, a2, a3, · · · , an> podemos permutaresta sequência de dados como <a′1, a

′2, a

′3, · · · , a′n> tal que a′1 la′2 la′3 l · · ·la′n, para alguma relação

de ordem l. Com o presente trabalho é possível comparar não apenas ai com aj , mas sim, todos oselementos de P({a1, a2, a3, · · · , an}). Esta nova relação de ordem possibilita particulamente que seordene sequências de dados, e que os subconjuntos obtidos de forma randômica de um conjunto finitosejam todos ordenados com um mesmo algoritimo.

Referências

[1] ABRAMO, Hefez. Curso de Álgebra Vol.1, Coleção Matemática Universitária. IMPA. 2002.

[2] DOMINGUES. Higino H. Espaços Métricos e Introdução à Topologia. Atual, São Paulo, 1982.

[3] GARCIA, Arnaldo. Elementos de Álgebra. Projeto Euclides. IMPA. 2002

[4] LIMA, Elon lages. Curso de análise volume 1. Rio de Janeiro, 11a edição, 2004

[5] SILVA, S. G. Cem Anos do Axioma da Escolha. 2009. Texto disponível em<http://200.17.137.110:8080/semat/edicoes-anteriores/2008-vii-semat/material/samuel-gomes-da-silva-dmat-ufba>

ISSN 2317-3289

69