Konečný vztah - Finitary relation

v matematika, a konečný vztah přes sady X1, …, Xn je podmnožinou souboru kartézský součin X1 × … × Xn; to znamená, že je to soubor n- n-tice (X1, …, Xn) skládající se z prvků Xi v Xi.[1][2][3][4] Relace obvykle popisuje možné spojení mezi prvky an n-tuple. Například vztah „X je dělitelné y a z"sestává ze sady 3 n-tic, které při nahrazení X, y a z, respektive, aby věta byla pravdivá.

Nezáporné celé číslo n udání počtu "míst" ve vztahu se nazývá arity, adicita nebo stupeň vztahu. Vztah s n "místa" se různě nazývá n-ary vztah, an n-adický vztah nebo a vztah stupně n. Vztahy s konečným počtem míst se nazývají konečné vztahy (nebo jednoduše vztahy pokud je kontext jasný). Je také možné koncept zobecnit na nekonečné vztahy s nekonečné sekvence.[5]

An n-aryární vztah přes množiny X1, …, Xn je prvkem napájecí sada z X1 × … × Xn.

0-ary vztahy počítají pouze dva členy: ten, který vždy drží, a ten, který nikdy nemá. Je to proto, že existuje pouze jedna n-tice, prázdná n-tice (). Někdy jsou užitečné pro konstrukci základního případu indukce argument.

Unární vztahy lze považovat za sbírku členů (například sbírku Nositelé Nobelovy ceny ) mít nějaký majetek (například ten, že mu byl udělen Nobelova cena ).

Binární vztahy jsou nejčastěji studovanou formou finitárních vztahů. Když X1 = X2 jmenuje se a homogenní vztah, například:

Jinak je to heterogenní vztah, například:

Příklad

Zvažte ternární vztah R "X myslí si to y má rád z„přes skupinu lidí P = {Alice, Bob, Charles, Denise}, definován:

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

R lze ekvivalentně znázornit v následující tabulce:

Vztah R "X myslí si to y má rád z"
PPP
AliceBobDenise
CharlesiAliceBob
CharlesiCharlesiAlice
DeniseDeniseDenise

Zde každý řádek představuje trojnásobek R, to znamená, že učiní prohlášení o formuláři "X myslí si to y má rád zNapříklad. První řádek uvádí, že „Alice si myslí, že Bob má Denise ráda.“ Všechny řádky jsou odlišné. Řazení řádků je nevýznamné, ale pořadí sloupců je významné.[1]

Výše uvedená tabulka je také jednoduchým příkladem a relační databáze, pole s teoretickým základem relační algebra a aplikace ve správě dat.[6] Počítačoví vědci, logici a matematici však mají tendenci mít různé koncepce, co je obecný vztah a z čeho se skládá. Například databáze jsou navrženy tak, aby se zabývaly empirickými daty, která jsou ze své podstaty konečná, zatímco v matematice jsou zohledňovány také vztahy s nekonečnou aritou (tj. Nekonečný vztah).

Definice

Když jsou dva objekty, vlastnosti, třídy nebo atributy, viděné společně myslí, viděny pod nějakým spojením, toto spojení se nazývá relace.

— Augustus De Morgan[7]

První definice vztahů, s nimiž se v matematice setkáváme, je:

Definice 1. - An n-ary vztah R přes sady X1, …, Xn je podmnožinou kartézského součinu X1 × … × Xn.[1]

Druhá definice vztahů využívá idiom, který je v matematice běžný, a stanoví, že „takový a takový je n-tuple “, aby bylo zajištěno, že takový a takový matematický objekt je určen specifikací matematických objektů s n elementy. V případě vztahu R přes n sady, tam jsou n + 1 věci k upřesnění, jmenovitě n sady plus podmnožina jejich kartézského součinu. V idiomu je to vyjádřeno tím, že to říkáme R je (n + 1) -tuple.

Definice 2. - An n-ary vztah R přes sady X1, …, Xn je (n + 1) -tuple (X1, …, Xn, G) kde G je podmnožinou kartézského součinu X1 × … × Xn volal graf z R.

Zpravidla bude pro tento účel vybrána jakákoli definice, která nejlépe odpovídá dané aplikaci, a pokud bude někdy nutné rozlišovat mezi těmito dvěma definicemi, pak entita splňující druhou definici může být nazývána vložený nebo zahrnutý vztah.

Obě prohlášení (X1, …, Xn) v R (podle první definice) a (X1, …, Xn) v G (podle druhé definice) číst „X1, …, Xn jsou R-related “a jsou označeny pomocí prefixový zápis podle Rx1…Xn a pomocí postfixová notace podle X1…XnR. V případě, že R je binární relace, tyto příkazy jsou také označeny pomocí infixová notace podle X1Rx2.

U každé definice platí následující úvahy:

  • Sada Xi se nazývá ith doména z R.[1] Podle první definice relace jednoznačně neurčuje danou sekvenci domén. V případě, že R je binární relace, X1 se také nazývá jednoduše doména nebo sada odletu z R, a X2 se také nazývá codomain nebo soubor cíle z R.
  • Když prvky Xi jsou vztahy, Xi se nazývá a jednoduchá doména z R.[1]
  • Sada všech Xi v Xi pro které existuje (X1, …, Xi − 1, Xi + 1, …, Xn) v X1 × … × Xi − 1 × Xi + 1 × … × Xn takhle Rx1…Xi − 1XiXi + 1…Xn se nazývá ith doména definice nebo aktivní doména z R.[1] V případě, že R je binární relace, jeho první definiční doména se také nazývá jednoduše doména definice nebo aktivní doména z Ra jeho druhá definiční doména se také nazývá doména definice nebo aktivní codomain z R.
  • Když idoména definice R je rovný Xi, R se říká, že je celkový na Xi. V případě, že R je binární relace, když R je celkem na X1, také se říká, že je celkem vlevo nebo seriál, a kdy R je celkem na X2, také se říká, že je celkem správně nebo surjektivní.
  • Když pro všechny X a y v πi ∈ Já Xi a pro všechny z v πi ∈ J Xi kde {Já, J} je rozdělit z {1, …, n}, pokud komponenty X a z jsou R- související a komponenty y a z jsou R- související X = y, R se říká, že je unikátní na {Xi}i ∈ Já, a {Xi}i ∈ J je nazýván A primární klíč[1] z R. V případě, že R je binární relace, když R je jedinečný na {X1}, také se říká, že je levý-jedinečný nebo injekční, a kdy R je jedinečný na {X2}, také se říká, že je pravý-jedinečný nebo funkční.
  • Když všichni Xi jsou stejná sada X, je jednodušší na něj odkazovat R jako n- opakovaný vztah X, nazvaný a homogenní vztah. v opačném případě R se nazývá a heterogenní vztah.
  • Když některý z Xi je prázdný, definující kartézský součin je prázdný a jediný vztah přes takovou posloupnost domén je prázdný vztah R = ∅. Proto se běžně stanoví, že všechny domény jsou neprázdné.

Nechť Booleovská doména B být dvouprvková množina, řekněme, B = {0, 1}, jehož prvky lze obvykle interpretovat jako logické hodnoty 0 = nepravda a 1 = pravda. The charakteristická funkce z R, označený χR, je Funkce s booleovskou hodnotou χR: X1 × … × Xn → B, definován χR((X1, …, Xn)) = 1 -li Rx1…Xn a χR((X1, …, Xn)) = 0 v opačném případě.

V aplikované matematice počítačová věda a statistiky je běžné označovat booleovskou funkci jako n-ary predikát. Z abstraktnějšího pohledu formální logika a teorie modelů vztah R představuje a logický model nebo a relační struktura, který slouží jako jeden z mnoha možných interpretace některých n-ary symbol predikátu.

Protože vztahy vznikají v mnoha vědních oborech i v mnoha oborech matematika a logika, existují značné rozdíly v terminologii. Kromě set-teoretický rozšíření relačního konceptu nebo termínu, termín "relace" může být také použit k označení odpovídající logické entity, buď logické porozumění, což je souhrn záměry nebo abstraktní vlastnosti sdílené všemi prvky v relaci, nebo symboly označující tyto prvky a rozšíření. Někteří autoři posledního přesvědčování dále zavádějí pojmy s konkrétnějšími konotacemi (například „relační struktura“ pro množinově-teoretické rozšíření daného relačního konceptu).

Dějiny

Viz také: Algebraická logika # Historie

Logik Augustus De Morgan, v práci publikované kolem roku 1860, byl první, kdo vyjádřil pojem vztahu v něčem, jako je jeho současný význam. Uvedl také první formální výsledky v teorii vztahů (k De Morganovi a relacím, viz Merrill 1990).

Charles Peirce, Gottlob Frege, Georg Cantor, Richard Dedekind a další pokročili v teorii vztahů. Mnoho z jejich nápadů, zejména na vztahy volalo objednávky, byly shrnuty v Principy matematiky (1903) kde Bertrand Russell tyto výsledky bezplatně využili.

V roce 1970 Edgar Codd navrhl a relační model pro databáze, a tak předvídat vývoj systémy pro správu databází.[1]

Viz také

Reference

  1. ^ A b C d E F G h Codd, Edgar Frank (červen 1970). „Relační model dat pro velké sdílené datové banky“ (PDF). Komunikace ACM. 13 (6): 377–387. doi:10.1145/362384.362685. Citováno 2020-04-29.
  2. ^ „Definitivní glosář vyššího matematického žargonu - vztah“. Matematický trezor. 2019-08-01. Citováno 2019-12-12.
  3. ^ „Vztah - encyklopedie matematiky“. www.encyclopediaofmath.org. Citováno 2019-12-12.
  4. ^ „Definice n-ary relace“. cs.odu.edu. Citováno 2019-12-12.
  5. ^ Nivat, Maurice (1981). Astesiano, Egidio; Böhm, Corrado (eds.). „Infinitární vztahy“. CAAP '81. Přednášky z informatiky. Springer Berlin Heidelberg: 46–75. doi:10.1007/3-540-10828-9_54. ISBN  978-3-540-38716-9.
  6. ^ „Relations - CS441“ (PDF). www.pitt.edu. Citováno 2019-12-11.
  7. ^ De Morgan, A. (1858) „O sylogismu, část 3“ v Heath, P., ed. (1966) O sylogismu a dalších logických spisech. Routledge. 119,

Bibliografie

  • Codd, Edgar Frank (1990). Relační model pro správu databáze: verze 2 (PDF). Boston: Addison-Wesley. ISBN  978-0201141924.
  • Bourbaki, N. (1994) Základy dějin matematiky, John Meldrum, trans. Springer-Verlag.
  • Carnap, Rudolf (1958) Úvod do symbolické logiky s aplikacemi. Dover Publications.
  • Halmos, P.R. (1960) Naivní teorie množin. Princeton NJ: D. Van Nostrand Company.
  • Lawvere, F.W. a R. Rosebrugh (2003) Sady pro matematiku, Cambridge Univ. Lis.
  • Lewis, C.I. (1918) Průzkum symbolické logiky, Kapitola 3: Aplikace Boole - Schröder Algebra, via Internetový archiv
  • Lucas, J. R. (1999) Konceptuální kořeny matematiky. Routledge.
  • Maddux, R.D. (2006) Vztah Algebry, sv. 150 v části „Studium logiky a základy matematiky“. Elsevierova věda.
  • Merrill, Dan D. (1990) Augustus De Morgan a logika vztahů. Kluwer.
  • Peirce, C.S. (1870), „Popis notace pro logiku příbuzných, vyplývající ze zesílení koncepcí Booleova logického počtu“, Monografie Americké akademie umění a věd 9, 317–78, 1870. Přetištěno, Shromážděné dokumenty CP 3,45–149, Chronologické vydání CE 2, 359–429.
  • Peirce, C.S. (1984) Spisy Charlese S. Peirce: Chronologické vydání, svazek 2, 1867-1871. Projekt Peirce Edition, eds. Indiana University Press.
  • Russell, Bertrand (1903/1938) Principy matematiky, 2. vyd. Cambridge Univ. Lis.
  • Suppes, Patricku (1960/1972) Teorie axiomatických množin. Dover Publications.
  • Tarski, A. (1956/1983) Logika, sémantika, metamatematika, referáty od roku 1923 do roku 1938J.H. Woodger, trans. 1. vydání, Oxford University Press. 2. vydání, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.
  • Ulam, S.M. a Bednarek, A.R. (1990), „The Theory of Relational Structure and Schemata for Parallel Computation“, str. 477–508 v A.R. Bednarek a Françoise Ulam (eds.), Analogie mezi analogiemi: Matematické zprávy S.M. Ulam a jeho spolupracovníci z Los Alamos, University of California Press, Berkeley, CA.
  • Ulam, S.M. (1990) Analogie mezi analogiemi: Matematické zprávy S.M. Ulam a jeho spolupracovníci z Los Alamos v A.R. Bednarek a Françoise Ulam, eds., University of California Press.
  • Roland Fraïssé (2000) [1986] Teorie vztahů, Severní Holandsko