Relação Finitária - Finitary relation

Em matemática , uma relação finitária sobre conjuntos X 1 ,…, X n é um subconjunto do produto cartesiano X 1 × ⋯ × X n ; ou seja, é um conjunto de n -tuplas ( x 1 ,…, x n ) consistindo em elementos x i em X i . Normalmente, a relação descreve uma possível conexão entre os elementos de uma n- dupla. Por exemplo, a relação " x é divisível por y e z " consiste no conjunto de três tuplas tais que, quando substituídas por x , y e z , respectivamente, tornam a frase verdadeira.

O número inteiro não negativo n que fornece o número de "lugares" na relação é chamado de aridade , adicidade ou grau da relação. Uma relação com n "lugares" é denominada de várias maneiras uma relação n -ary , uma relação n -adica ou uma relação de grau n . As relações com um número finito de lugares são chamadas de relações finitárias (ou simplesmente relações se o contexto for claro). Também é possível generalizar o conceito para relações infinitarias com sequências infinitas .

Uma relação n -ary sobre os conjuntos X 1 ,…, X n é um elemento do conjunto de potência de X 1 × ⋯ × X n .

As relações 0-árias contam apenas dois membros: o que sempre é válido e o que nunca é válido. Isso ocorre porque há apenas uma tupla 0, a tupla vazia (). Às vezes, eles são úteis para construir o caso base de um argumento de indução .

As relações unárias podem ser vistas como uma coleção de membros (como a coleção de ganhadores do Nobel ) com alguma propriedade (como a de ter recebido o prêmio Nobel ).

As relações binárias são a forma mais comumente estudada de relações finitárias. Quando X 1 = X 2 é chamada de relação homogênea , por exemplo:

Caso contrário, é uma relação heterogênea , por exemplo:

Exemplo

Considere a relação ternária R " x pensa que y gosta de z " sobre o conjunto de pessoas P = {Alice, Bob, Charles, Denise }, definida por:

R = {(Alice, Bob, Denise), (Charles, Alice, Bob), (Charles, Charles, Alice), (Denise, Denise, Denise) }.

R pode ser representado de forma equivalente pela seguinte tabela:

Relação R " x pensa que y gosta de z "
P P P
Alice Prumo Denise
Charles Alice Prumo
Charles Charles Alice
Denise Denise Denise

Aqui, cada linha representa um triplo de R , ou seja, faz uma declaração da forma " x pensa que y gosta de z ". Por exemplo, a primeira linha afirma que "Alice acha que Bob gosta de Denise". Todas as linhas são distintas. A ordem das linhas é insignificante, mas a ordem das colunas é significativa.

A tabela acima também é um exemplo simples de banco de dados relacional , um campo com teoria enraizada na álgebra relacional e aplicações em gerenciamento de dados. Cientistas da computação, lógicos e matemáticos, entretanto, tendem a ter diferentes concepções do que é uma relação geral e do que ela consiste. Por exemplo, bancos de dados são projetados para lidar com dados empíricos, que são por definição finitos, enquanto na matemática, relações com aridade infinita (isto é, relação infinitária) também são consideradas.

Definições

Quando dois objetos, qualidades, classes ou atributos, vistos juntos pela mente, são vistos sob alguma conexão, essa conexão é chamada de relação.

-  Augustus De Morgan

A primeira definição de relações encontradas na matemática é:

Definição 1
Uma relação n -ary R sobre conjuntos X 1 ,…, X n é um subconjunto do produto cartesiano X 1 × ⋯ × X n .

A segunda definição de relações faz uso de um idioma comum na matemática, estipulando que "tal e tal é um n- duplo" para garantir que tal e tal objeto matemático seja determinado pela especificação de objetos matemáticos com n elementos . No caso de uma relação R sobre n conjuntos, há n + 1 coisas a especificar, a saber, os n conjuntos mais um subconjunto de seu produto cartesiano. No idioma, isso é expresso dizendo que R é a ( n + 1 ) -tuplo.

Definição 2
Uma relação n -ary R sobre conjuntos X 1 ,…, X n é um ( n + 1 ) -tuplo ( X 1 ,…, X n , G ) onde G é um subconjunto do produto cartesiano X 1 × ⋯ × X n chamado o gráfico de R .

Como regra, qualquer definição que melhor se adapte ao aplicativo em questão será escolhida para esse propósito, e se alguma vez for necessário distinguir entre as duas definições, então uma entidade que satisfaça a segunda definição pode ser chamada de relação embutida ou incluída .

Ambas as declarações ( x 1 , ..., x n ) em R (na primeira definição) e ( x 1 , ..., x n ) em G (na segunda definição) lêem " x 1 , ..., x n estão relacionados com R "e são indicadas usando a notação prefixo por Rx 1 ⋯ x n e usando a notação sufixo por x 1 ⋯ x N R . No caso em que R é uma relação binária, essas declarações também são denotadas usando a notação infixa por x 1 Rx 2 .

As seguintes considerações se aplicam em qualquer definição:

  • O conjunto X i é chamado o i th domínio de R . De acordo com a primeira definição, a relação não determina exclusivamente uma determinada sequência de domínios. No caso em que R é uma relação binária, X 1 é também chamado simplesmente o domínio ou conjunto de partida de R , e X 2 também é chamado de codomain ou conjunto de destino de R .
  • Quando os elementos de X i são relações, X i é chamado de domínio nonsimple de R .
  • O conjunto de todos os x i em X i para o qual existe ( x 1 ,…, x i - 1 , x i + 1 ,…, x n ) em X 1 × ⋯ × X i - 1 × X i + 1 × ⋯ × X n tal que Rx 1 ⋯ x i - 1 x i x i + 1 ⋯ x n é chamado o i th domínio de definição ou domínio activo de R . No caso em que R é uma relação binária, o seu primeiro domínio de definição também é chamado simplesmente o domínio de definição ou domínio activo de R , e o seu segundo domínio de definição também é chamado o codomain de definição ou codomain activo de R .
  • Quando o i ésimo domínio de definição de R é igual a X i , diz-se que R é total em X i . No caso em que R é uma relação binária, quando R é total em X 1 , também é dito total à esquerda ou serial , e quando R é total em X 2 , também é dito total à direita ou sobrejetora .
  • Quando para todo x e y em π i ∈ I X i e para todo z em π i ∈ J X i onde { I , J } é uma partição de {1,…, n }, se os componentes de x e z são R relacionados com os componentes e de y e z são R relacionados com, em seguida, x = y , R é dito ser único em { X i } i ∈ I , e { X i } i ∈ J é chamado uma chave primária de R . No caso em que R é uma relação binária, quando R é único em { X 1 }, também é dito único à esquerda ou injetivo , e quando R é único em { X 2 }, também é dito que está certo -unique ou funcional .
  • Quando todos os X i são o mesmo conjunto X , é mais simples referir-se a R como uma relação n -ária sobre X , chamada de relação homogênea . Caso contrário, R é chamado de relação heterogênea .
  • Quando qualquer um de X i está vazio, o produto cartesiano definidor está vazio, e a única relação sobre tal sequência de domínios é a relação vazia R = ∅ . Portanto, é comumente estipulado que todos os domínios não devem estar vazios.

Seja um domínio booleano B um conjunto de dois elementos, digamos, B = {0, 1 }, cujos elementos podem ser interpretados como valores lógicos, normalmente 0 = falso e 1 = verdadeiro . A função característica de R , denotada por χ R , é a função de valor booleano χ R : X 1 × ⋯ × X n → B , definida por χ R ( ( x 1 ,…, x n ) ) = 1 se Rx 1 ⋯ x n e χ R ( ( x 1 ,…, x n ) ) = 0 caso contrário.

Em matemática aplicada, ciência da computação e estatística, é comum referir-se a uma função de valor booleano como um predicado n -ary . Do ponto de vista mais abstrato da lógica formal e da teoria do modelo , a relação R constitui um modelo lógico ou uma estrutura relacional , que serve como uma das muitas interpretações possíveis de algum símbolo de predicado n -ary.

Como as relações surgem em muitas disciplinas científicas, bem como em muitos ramos da matemática e da lógica , existe uma variação considerável na terminologia. Além da extensão teórica de conjuntos de um conceito ou termo relacional, o termo "relação" também pode ser usado para se referir à entidade lógica correspondente, seja a compreensão lógica , que é a totalidade de intenções ou propriedades abstratas compartilhadas por todos os elementos em a relação, ou então os símbolos que denotam esses elementos e intenções. Além disso, alguns escritores da última convicção introduzem termos com conotações mais concretas (como "estrutura relacional" para a extensão teórica de conjuntos de um dado conceito relacional).

História

Veja também: Lógica algébrica § História

O lógico Augustus De Morgan , em trabalho publicado por volta de 1860, foi o primeiro a articular a noção de relação em algo parecido com seu sentido atual. Ele também declarou os primeiros resultados formais na teoria das relações (sobre De Morgan e relações, ver Merrill 1990).

Charles Peirce , Gottlob Frege , Georg Cantor , Richard Dedekind e outros desenvolveram a teoria das relações. Muitas de suas idéias, especialmente sobre relações chamadas ordens , foram resumidas em The Principles of Mathematics (1903), onde Bertrand Russell fez uso livre desses resultados.

Em 1970, Edgar Codd propôs um modelo relacional para bancos de dados , antecipando o desenvolvimento de sistemas de gerenciamento de bancos de dados .

Veja também

Referências

  1. ^ a b c d e f g h Codd, Edgar Frank (junho de 1970). "Um modelo relacional de dados para grandes bancos de dados compartilhados" (PDF) . Comunicações da ACM . 13 (6): 377–387. doi : 10.1145 / 362384.362685 . Obtido em 2020-04-29 .
  2. ^ "O Glossário Definitivo do Jargão Matemático Superior - Relação" . Math Vault . 01/08/2019 . Página visitada em 12/12/2019 .
  3. ^ "Relation - Encyclopedia of Mathematics" . www.encyclopediaofmath.org . Página visitada em 12/12/2019 .
  4. ^ "Definição de relação n-ária" . cs.odu.edu . Página visitada em 12/12/2019 .
  5. ^ Nivat, Maurício (1981). Astesiano, Egidio; Böhm, Corrado (eds.). "Relações infinitárias" . Caap '81 . Notas de aula em Ciência da Computação. Springer Berlin Heidelberg. 112 : 46–75. doi : 10.1007 / 3-540-10828-9_54 . ISBN 978-3-540-38716-9.
  6. ^ "Relações - CS441" (PDF) . www.pitt.edu . Página visitada em 11/12/2019 .
  7. ^ De Morgan, A. (1858) "On the syllogism, part 3" in Heath, P., ed. (1966) Sobre o silogismo e outros escritos lógicos . Routledge. P. 119,

Bibliografia

  • Codd, Edgar Frank (1990). O modelo relacional para gerenciamento de banco de dados: Versão 2 (PDF) . Boston: Addison-Wesley . ISBN 978-0201141924.
  • Bourbaki, N. (1994) Elements of the History of Mathematics , John Meldrum, trad. Springer-Verlag.
  • Carnap, Rudolf (1958) Introduction to Symbolic Logic with Applications . Publicações de Dover.
  • Halmos, PR (1960) Naive Set Theory . Princeton NJ: D. Van Nostrand Company.
  • Lawvere, FW e R. Rosebrugh (2003) Sets for Mathematics , Cambridge Univ. Pressione.
  • Lewis, CI (1918) A Survey of Symbolic Logic , Capítulo 3: Applications of the Boole — Schröder Algebra, via Internet Archive
  • Lucas, JR (1999) Conceptual Roots of Mathematics . Routledge.
  • Maddux, RD (2006) Relation Algebras , vol. 150 em 'Estudos em lógica e os fundamentos da matemática'. Elsevier Science.
  • Merrill, Dan D. (1990) Augustus De Morgan e a lógica das relações . Kluwer.
  • Peirce, CS (1870), "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic", Memórias da Academia Americana de Artes e Ciências 9, 317-78, 1870. Reimpresso , Collected Papers CP 3.45–149, Chronological Edition CE 2, 359–429.
  • Peirce, CS (1984) Writings of Charles S. Peirce: A Chronological Edition, Volume 2, 1867-1871 . Peirce Edition Project, eds. Indiana University Press.
  • Russell, Bertrand (1903/1938) The Principles of Mathematics, 2ª ed. Cambridge Univ. Pressione.
  • Suppes, Patrick (1960/1972) Aximatic Set Theory . Publicações de Dover.
  • Tarski, A. (1956/1983) Logic, Semantics, Metamathematics, Papers de 1923 a 1938 , JH Woodger, trad. 1ª edição, Oxford University Press. 2ª edição, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.
  • Ulam, SM e Bednarek, AR (1990), "On the Theory of Relational Structures and Schemata for Parallel Computation", pp. 477–508 em AR Bednarek e Françoise Ulam (eds.), Analogies Between Analogies: The Mathematical Reports of SM Ulam and His Los Alamos Collaborators , University of California Press, Berkeley, CA.
  • Ulam, SM (1990) Analogies Between Analogies: The Mathematical Reports of SM Ulam and His Los Alamos Collaborators in AR Bednarek and Françoise Ulam, eds., University of California Press.
  • Roland Fraïssé (2000) [1986] Teoria das Relações , Holanda do Norte