Notação set-builder - Set-builder notation

Na teoria dos conjuntos e em suas aplicações à lógica , matemática e ciência da computação , a notação de construtor de conjuntos é uma notação matemática para descrever um conjunto enumerando seus elementos ou declarando as propriedades que seus membros devem satisfazer.

Definir conjuntos por propriedades também é conhecido como compreensão de conjunto , abstração de conjunto ou como definir a intenção de um conjunto .

Conjuntos definidos por enumeração

Um conjunto pode ser descrito diretamente enumerando todos os seus elementos entre chaves, como nos dois exemplos a seguir:

• ${\ displaystyle \ {7,3,15,31 \}}$ é o conjunto contendo os quatro números 3, 7, 15 e 31 e nada mais.
• ${\ displaystyle \ {a, c, b \} = \ {a, b, c \}}$é o conjunto que contém um , b , e c , e nada mais (não há nenhuma ordem entre os elementos de um conjunto).

Isso às vezes é chamado de "método de lista" para especificar um conjunto.

Quando se deseja denotar um conjunto que contém elementos de uma sequência regular, uma notação de elipses pode ser empregada, conforme mostrado nos próximos exemplos:

• ${\ displaystyle \ {1,2,3, \ ldots, 100 \}}$ é o conjunto de inteiros entre 1 e 100 inclusive.
• ${\ displaystyle \ {1,2,3, \ ldots \}}$é o conjunto de números naturais .
• ${\ displaystyle \ {\ ldots, -2, -1,0,1,2, \ ldots \} = \ {0,1, -1,2, -2, \ ldots \}}$ é o conjunto de todos os inteiros.

Não há ordem entre os elementos de um conjunto (isso explica e valida a igualdade do último exemplo), mas com a notação de elipses, usamos uma sequência ordenada antes (ou depois) da elipse como um veículo notacional conveniente para explicar quais elementos estão em um conjunto. Os primeiros elementos da sequência são mostrados, então as elipses indicam que a interpretação mais simples deve ser aplicada para continuar a sequência. Caso nenhum valor final apareça à direita das reticências, a sequência é considerada ilimitada.

Em geral, denota o conjunto de todos os números naturais de tal forma que . Outra notação para é a notação de colchetes . Um caso especial sutil é , em que é igual ao conjunto vazio . Da mesma forma, denota o conjunto de todos para . ${\ displaystyle \ {1, \ dots, n \}}$${\ displaystyle i}$${\ displaystyle 1 \ leq i \ leq n}$${\ displaystyle \ {1, \ dots, n \}}$${\ displaystyle [n]}$${\ displaystyle n = 0}$${\ displaystyle [0] = \ {1, \ dots, 0 \}}$ ${\ displaystyle \ emptyset}$${\ displaystyle \ {a_ {1}, \ dots, a_ {n} \}}$${\ displaystyle a_ {i}}$${\ displaystyle 1 \ leq i \ leq n}$

Em cada exemplo anterior, cada conjunto é descrito enumerando seus elementos. Nem todos os conjuntos podem ser descritos dessa maneira ou, se puderem, sua enumeração pode ser muito longa ou complicada para ser útil. Portanto, muitos conjuntos são definidos por uma propriedade que caracteriza seus elementos. Esta caracterização pode ser feita informalmente usando prosa geral, como no exemplo a seguir.

• ${\ displaystyle \ {}$endereços na Pine Street é o conjunto de todos os endereços na Pine Street.${\ displaystyle \}}$

No entanto, a abordagem da prosa pode carecer de precisão ou ser ambígua. Assim, a notação de construtor de conjunto é frequentemente usada com um predicado que caracteriza os elementos do conjunto que está sendo definido, conforme descrito na seção a seguir.

Conjuntos definidos por um predicado

A notação de construtor de conjunto pode ser usada para descrever um conjunto que é definido por um predicado , ou seja, uma fórmula lógica que avalia como verdadeiro para um elemento do conjunto e como falso caso contrário. Nessa forma, a notação set-builder tem três partes: uma variável, dois pontos ou separador de barra vertical e um predicado. Portanto, há uma variável à esquerda do separador e uma regra à direita dele. Essas três partes estão contidas em chaves:

${\ displaystyle \ {x \ mid \ Phi (x) \}}$

ou

${\ displaystyle \ {x: \ Phi (x) \}.}$

A barra vertical (ou dois pontos) é um separador que pode ser lido como " tal que ", "para qual" ou "com a propriedade que". A fórmula Φ ( x ) é considerada a regra ou o predicado . Todos os valores de x para os quais o predicado é válido (é verdadeiro) pertencem ao conjunto que está sendo definido. Todos os valores de x para os quais o predicado não é válido não pertencem ao conjunto. Portanto, é o conjunto de todos os valores de x que satisfazem a fórmula Φ . Pode ser o conjunto vazio , se nenhum valor de x satisfizer a fórmula. ${\ displaystyle \ {x \ mid \ Phi (x) \}}$

Especificando o domínio

Um domínio E pode aparecer à esquerda da barra vertical:

${\ displaystyle \ {x \ in E \ mid \ Phi (x) \},}$

ou anexando-o ao predicado:

${\ displaystyle \ {x \ mid x \ in E {\ text {e}} \ Phi (x) \} \ quad {\ text {ou}} \ quad \ {x \ mid x \ in E \ land \ Phi (x) \}.}$

O símbolo ∈ aqui denota associação ao conjunto , enquanto o símbolo denota o operador lógico "e", conhecido como conjunção lógica . Essa notação representa o conjunto de todos os valores de x que pertencem a algum determinado conjunto E para o qual o predicado é verdadeiro (consulte " Axioma de existência de conjunto " abaixo). Se for uma conjunção , às vezes é escrito usando uma vírgula em vez do símbolo . ${\ displaystyle \ land}$${\ displaystyle \ Phi (x)}$${\ displaystyle \ Phi _ {1} (x) \ land \ Phi _ {2} (x)}$${\ displaystyle \ {x \ in E \ mid \ Phi (x) \}}$${\ displaystyle \ {x \ in E \ mid \ Phi _ {1} (x), \ Phi _ {2} (x) \}}$${\ displaystyle \ land}$

Em geral, não é uma boa ideia considerar conjuntos sem definir um domínio, pois isso representaria o subconjunto de todas as coisas possíveis que podem existir para as quais o predicado é verdadeiro. Isso pode facilmente levar a contradições e paradoxos. Por exemplo, o paradoxo de Russell mostra que a expressão, embora aparentemente bem formada como uma expressão construtora de conjuntos, não pode definir um conjunto sem produzir uma contradição. ${\ displaystyle \ {x ~ | ~ x \ não \ em x \},}$

Nos casos em que o conjunto E é claro do contexto, ele pode não ser especificado explicitamente. É comum na literatura um autor declarar o domínio com antecedência e não especificá-lo na notação de construtor de conjuntos. Por exemplo, um autor pode dizer algo como, "A menos que seja declarado de outra forma, as variáveis ​​devem ser consideradas números naturais.". Embora em contextos menos formais em que o domínio pode ser assumido, uma menção por escrito é freqüentemente desnecessária.

Exemplos

Os exemplos a seguir ilustram conjuntos específicos definidos pela notação set-builder por meio de predicados. Em cada caso, o domínio é especificado no lado esquerdo da barra vertical, enquanto a regra é especificada no lado direito.

• ${\ displaystyle \ {x \ in \ mathbb {R} \ mid x> 0 \}}$é o conjunto de todos os números reais estritamente positivos , que podem ser escritos em notação de intervalo como .${\ displaystyle (0, \ infty)}$
• ${\ displaystyle \ {x \ in \ mathbb {R} \ mid | x | = 1 \}}$é o conjunto . Este conjunto também pode ser definido como ; ver predicados equivalentes produzem conjuntos iguais abaixo.${\ displaystyle \ {- 1,1 \}}$${\ displaystyle \ {x \ in \ mathbb {R} \ mid x ^ {2} = 1 \}}$
• Para cada inteiro m , podemos definir . Por exemplo, e .${\ displaystyle G_ {m} = \ {x \ in \ mathbb {Z} \ mid x \ geq m \} = \ {m, m + 1, m + 2, \ ldots \}}$${\ displaystyle G_ {3} = \ {x \ in \ mathbb {Z} \ mid x \ geq 3 \} = \ {3,4,5, \ ldots \}}$${\ displaystyle G _ {- 2} = \ {- 2, -1,0, \ ldots \}}$
• ${\ displaystyle \ {(x, y) \ in \ mathbb {R} \ times \ mathbb {R} \ mid 0 <y <f (x) \}}$ é o conjunto de pares de números reais tais que y é maior que 0 e menor que f ( x ), para uma dada função f . Aqui, o produto cartesiano denota o conjunto de pares ordenados de números reais.${\ displaystyle \ mathbb {R} \ times \ mathbb {R}}$
• ${\ displaystyle \ {n \ in \ mathbb {N} \ mid (\ existe k) [k \ in \ mathbb {N} \ land n = 2k] \}}$é o conjunto de todos os números naturais pares . O sinal significa "e", que é conhecido como conjunção lógica . O sinal ∃ significa "existe", o que é conhecido como quantificação existencial . Portanto, por exemplo, é lido como 'existe um x tal que P ( x ) ".${\ displaystyle \ land}$${\ displaystyle (\ exists x) P (x)}$
• ${\ displaystyle \ {n \ mid (\ existe k \ in \ mathbb {N}) [n = 2k] \}}$é uma variante de notação para o mesmo conjunto de números naturais pares. Não é necessário especificar que n é um número natural, pois isso está implícito na fórmula à direita.
• ${\ displaystyle \ {a \ in \ mathbb {R} \ mid (\ existe p \ in \ mathbb {Z}) (\ existe q \ in \ mathbb {Z}) [q \ not = 0 \ land aq = p ] \}}$é o conjunto de números racionais ; ou seja, números reais que podem ser escritos como a proporção de dois inteiros .

Expressões mais complexas no lado esquerdo da notação

Uma extensão da notação set-builder substitui a única variável x por uma expressão . Então, em vez de , podemos ter o que deve ser lido ${\ displaystyle \ {x \ mid \ Phi (x) \}}$${\ displaystyle \ {\ Psi (x) \ mid \ Phi (x) \},}$

${\ displaystyle \ {\ Psi (x) \ mid \ Phi (x) \} = \ {y \ mid \ exists (x), y = \ Psi (x) {\ text {and}} \ Phi (x) \}}$.

Por exemplo:

• ${\ displaystyle \ {2n \ mid n \ in \ mathbb {N} \}}$, onde está o conjunto de todos os números naturais, é o conjunto de todos os números naturais pares.${\ displaystyle \ mathbb {N}}$
• ${\ displaystyle \ {p / q \ mid p, q \ in \ mathbb {Z}, q \ not = 0 \}}$, onde é o conjunto de todos os inteiros, é o conjunto de todos os números racionais.${\ displaystyle \ mathbb {Z}}$${\ displaystyle \ mathbb {Q},}$
• ${\ displaystyle \ {2t + 1 \ mid t \ in \ mathbb {Z} \}}$ é o conjunto de inteiros ímpares.
• ${\ displaystyle \ {(t, 2t + 1) \ mid t \ in \ mathbb {Z} \}}$ cria um conjunto de pares, onde cada par coloca um inteiro em correspondência com um inteiro ímpar.

Quando as funções inversas podem ser declaradas explicitamente, a expressão à esquerda pode ser eliminada por meio de substituição simples. Considere o exemplo definido . Faça a substituição , ou seja , substitua t na notação do construtor de conjunto para encontrar ${\ displaystyle \ {2t + 1 \ mid t \ in \ mathbb {Z} \}}$${\ displaystyle u = 2t + 1}$${\ displaystyle t = (u-1) / 2}$

${\ displaystyle \ {2t + 1 \ mid t \ in \ mathbb {Z} \} = \ {u \ mid (u-1) / 2 \ in \ mathbb {Z} \}.}$

Predicados equivalentes geram conjuntos iguais

Dois conjuntos são iguais se e somente se eles tiverem os mesmos elementos. Os conjuntos definidos pela notação do construtor de conjunto são iguais se e somente se suas regras do construtor de conjunto, incluindo os especificadores de domínio, forem equivalentes. Isso é

${\ displaystyle \ {x \ in A \ mid P (x) \} = \ {x \ in B \ mid Q (x) \}}$

se e apenas se

${\ displaystyle (\ forall t) [(t \ in A \ land P (t)) \ Leftrightarrow (t \ in B \ land Q (t))]}$.

Portanto, para provar a igualdade de dois conjuntos definidos pela notação do construtor de conjuntos, basta provar a equivalência de seus predicados, incluindo os qualificadores de domínio.

Por exemplo,

${\ displaystyle \ {x \ in \ mathbb {R} \ mid x ^ {2} = 1 \} = \ {x \ in \ mathbb {Q} \ mid | x | = 1 \}}$

porque os dois predicados de regra são logicamente equivalentes:

${\ displaystyle (x \ in \ mathbb {R} \ land x ^ {2} = 1) \ Leftrightarrow (x \ in \ mathbb {Q} \ land | x | = 1).}$

Essa equivalência é válida porque, para qualquer número real x , temos se e somente se x é um número racional com . Em particular, ambos os conjuntos são iguais ao conjunto . ${\ displaystyle x ^ {2} = 1}$${\ displaystyle | x | = 1}$${\ displaystyle \ {- 1,1 \}}$

Definir axioma de existência

Em muitas teorias de conjuntos formais, como a teoria de conjuntos de Zermelo-Fraenkel , a notação de construtor de conjuntos não faz parte da sintaxe formal da teoria. Em vez disso, existe um esquema de axioma de existência de conjunto , que afirma que se E é um conjunto e Φ ( x ) é uma fórmula na linguagem da teoria dos conjuntos, então existe um conjunto Y cujos membros são exatamente os elementos de E que satisfazem Φ :

${\ displaystyle (\ forall E) (\ exists Y) (\ forall x) [x \ in Y \ Leftrightarrow x \ in E \ land \ Phi (x)].}$

O conjunto Y obtido a partir deste axioma é exatamente o conjunto descrito na notação do construtor de conjuntos como . ${\ displaystyle \ {x \ in E \ mid \ Phi (x) \}}$

Paralelos em linguagens de programação

Uma notação semelhante disponível em várias linguagens de programação (notadamente Python e Haskell ) é a compreensão de lista , que combina operações de mapa e filtro em uma ou mais listas .

Em Python, as chaves do construtor de conjuntos são substituídas por colchetes, parênteses ou chaves, fornecendo objetos de lista, gerador e conjunto, respectivamente. Python usa uma sintaxe baseada em inglês. Haskell substitui os colchetes do construtor de conjuntos por colchetes e usa símbolos, incluindo a barra vertical do construtor de conjuntos padrão.

O mesmo pode ser alcançado em Scala usando Sequence Comprehensions, onde a palavra-chave "for" retorna uma lista das variáveis ​​geradas usando a palavra-chave "yield".

Considere estes exemplos de notação set-builder em algumas linguagens de programação:

	Exemplo 1	Exemplo 2
Construtor de conjuntos	${\ displaystyle \ {l \ | \ l \ in L \}}$	${\ displaystyle \ {(k, x) \ | \ k \ in K \ wedge x \ in X \ wedge P (x) \}}$
Pitão	{l for l in L}	{(k, x) for k in K for x in X if P(x)}
Haskell	[l | l <- ls]	[(k, x) | k <- ks, x <- xs, p x]
Scala	for (l <- L) yield l	for (k <- K; x <- X if P(x)) yield (k,x)
C #	from l in L select l	from k in K from x in X where P(x) select (k,x)
SQL	SELECT l FROM L_set	SELECT k, x FROM K_set, X_set WHERE P(x)

A notação de construtor de conjunto e a notação de compreensão de lista são ambas instâncias de uma notação mais geral conhecida como compreensões de mônadas , que permite operações do tipo mapa / filtro sobre qualquer mônada com um elemento zero .

Veja também

• Glossário de teoria dos conjuntos

Notas