Relasi finiter


Dalam matematika, relasi finiter dari himpunan X1, …, Xn adalah bagian dari produk Kartesius X1 × … × Xn; yaitu satu himpunan tupel-n (x1, …, xn) terdiri dari elemen xi dalam Xi.[1][2][3][4] Biasanya, relasi mendeskripsikan kemungkinan koneksi antara elemen tupel-n. Sebagai contoh, relasi "x habis dibagi y dan z" terdiri dari himpunan tupel-3 sehingga ketika disubstitusikan ke x, y dan z, kalimat tersebut menjadi benar.

Bilangan bulat non-negatif n yang memberikan jumlah "tempat" dalam relasi disebut ariti, adiciti atau derajat dari relasi. Relasi dengan n "tempat" disebut dengan berbagai cara relasi ari-n, relasi adik-n atau relasi derajat n. Relasi dengan sejumlah tempat terbatas disebut relasi finiter (atau relasi jika konteksnya jelas). Mungkin juga untuk menggeneralisasi konsep menjadi relasi tak hingga dengan barisan tak hingga.[5]

Relasi ari-n atas himpunan X1, …, Xn adalah elemen dari himpunan daya dari X1 × … × Xn.

Relasi 0-ari hanya menghitung dua anggota. Karena hanya ada satu 0-tupel, tupel kosong (). Mereka terkadang berguna untuk membangun kasus dasar dari argumen induksi.

Relasi dapat dilihat sebagai kumpulan anggota (seperti kumpulan pemenang Nobel) memiliki beberapa sifat (seperti yang telah dianugerahi Hadiah Nobel).

Relasi biner adalah bentuk hubungan finiter yang paling umum dipelajari. Maka X1 = X2 disebut relasi homogen, misalnya:

  • Kesetaraan dan pertidaksamaan, dilambangkan dengan tanda = dan < dalam pernyataan "5 < 12", atau
  • Pembagian, dilambangkan dengan tanda ÷ dalam pernyataan seperti "13÷143".

Jika tidak, relasi heterogen, misalnya:

Contoh

Pertimbangkan relasi terner R "x bahwa y menyukai z" dengan anggota P = {Siti, Udin, Dika, Denis}, didefinisikan oleh:

R = {Siti, Udin, Denis), (Dika, Siti, Udin), (Dika, Dika, Siti), (Denis, Denis, Denis)}.

R dapat direpresentasikan secara ekuivalen dengan tabel berikut:

Relasi R "x bahwa y menyukai z"
P P P
Siti Udin Denis
Dika Siti Udin
Dika Dika Dika
Denis Denis Denis

Barisan mewakili tiga dari R, yaitu pernyataan dalam bentuk "x bahwa y suka z". Misalnya, baris pertama menyatakan bahwa "Siti mengira Udin menyukai Denis". Semua baris berbeda. Urutan baris tidak signifikan tetapi urutan kolom signifikan.[1]

Tabel di atas juga merupakan contoh sederhana dari database relasional, bidang dengan teori yang berakar pada aljabar relasional dan aplikasi dalam manajemen data.[6] Ilmu komputer, logikawan, dan matematikawan, bagaimanapun, cenderung memiliki konsepsi yang berbeda tentang relasi umum, dan terdiri dari apa. Misalnya, basis data dirancang untuk menangani data empiris, yang menurut definisi hingga, sedangkan dalam matematika, relasi dengan aritas tak hingga (yaitu, relasi tak hingga) dipertimbangkan.

Definisi

Ketika dua objek, kualitas, kelas, atau atribut, dilihat bersama oleh pikiran, terlihat di bawah beberapa koneksi, koneksi tersebut adalah relasi.

— Augustus De Morgan[7]

Definisi pertama dari relasi yang dijumpai dalam matematika adalah:

Definisi 1. — relasi n-ari R dari himpunan X1, …, Xn adalah bagian dari produk Kartesius X1 × … × Xn.[1]

Definisi kedua dari relasi menggunakan idiom umum dalam matematika, menetapkan bahwa "ini dan itu adalah tupel-n" untuk memastikan bahwa ini dan itu objek matematika ditentukan oleh spesifikasi objek matematika dengan elemen n. Dalam kasus relasi R di atas himpunan n, maka n + 1 hal-hal yang perlu ditentukan, yaitu, himpunan n ditambah bagian dari produk Kartesius mereka. Dalam idiom hal ini diungkapkan dengan mengatakan bahwa R adalah tupel-(n + 1).

Definisi 2. — relasi n-ari R dari himpunan X1, …, Xn adalah tupel-(n + 1), (X1, …, Xn, G) dimana G adalah bagian dari produk Kartesius X1 × … × Xn disebut grafik dari R.

Sebagai kaidah, definisi dengan aplikasi yang ada akan dipilih untuk tujuan, dan jika perlu untuk membedakan antara dua definisi, maka entitas yang memenuhi definisi kedua dapat disebut tertanam atau relasi disertakan.

Kedua pernyataan (x1, …, xn) dalam R (di bawah definisi pertama) dan (x1, …, xn) dalam G (di bawah definisi kedua) maka "x1, …, xn adalah relasi-R "dan dilambangkan dengan notasi awalan oleh Rx1…xn dan menggunakan notasi postfix oleh x1…xnR. Dalam kasus dimana R adalah relasi biner, pernyataan tersebut dilambangkan dengan notasi infix oleh x1Rx2. Misalkan domain Boolean B menjadi himpunan dua elemen, misalnya, B = {0, 1}, yang elemennya dapat diartikan sebagai nilai logika, biasanya 0 = salah dan 1 = benar. fungsi karakteristik dari R, dilambangkan dengan χR, adalah Fungsi nilai Boolean χR: X1 × … × Xn → B, didefinisikan oleh χR((x1, …, xn)) = 1 jika Rx1…xn dan χR((x1, …, xn)) = 0.

Dalam matematika terapan, ilmu komputer dan statistik, adalah umum untuk merujuk ke fungsi bernilai Boolean sebagai n-ari predikat. Dari sudut pandang yang lebih abstrak dari logika formal dan teori model, relasi R merupakan model logika atau struktur relasional, yang berfungsi sebagai salah satu dari banyak kemungkinan interpretasi dari beberapa simbol predikat n-ari.

Karena relasi muncul dalam banyak disiplin ilmu, serta di banyak cabang matematika dan logika, banyak variasi dalam terminologi. Selain dari teori himpunan ekstensi dari konsep atau istilah relasional, istilah "relasi" juga dapat digunakan untuk merujuk ke entitas logis yang sesuai, baik Komprehensi logika, yang merupakan totalitas intensi atau sifat abstrak yang dimiliki oleh semua elemen dalam relasi, atau simbol yang menunjukkan elemen dan intensitas. Lebih lanjut, beberapa penulis dari persuasi terakhir memperkenalkan istilah dengan konotasi yang lebih konkret (seperti "struktur relasional" untuk perluasan teori himpunan dari konsep relasional tertentu).

Sejarah

Lihat pula: Logika aljabar § Sejarah

Logikawan Augustus De Morgan, dalam karya yang diterbitkan sekitar tahun 1860, adalah orang pertama yang mengartikulasikan gagasan relasi dalam segala hal seperti pengertiannya saat ini. Dia juga menyatakan hasil formal pertama dalam teori relasi (tentang De Morgan dan relasi, lihat Merrill 1990).

Charles Peirce, Gottlob Frege, Georg Cantor, Richard Dedekind dan lainnya mengajukan teori relasi. Banyak ide mereka, terutama pada relasi yang disebut order, diringkas dalam The Principles of Mathematics (1903) di mana Bertrand Russell memanfaatkan hasil ini secara bebas.

Pada tahun 1970, Edgar Codd mengusulkan model relasional untuk database, sehingga mengantisipasi pengembangan sistem manajemen basis data.[1]

Lihat pula

Referensi

  1. ^ a b c d Codd, Edgar Frank (June 1970). "A Relational Model of Data for Large Shared Data Banks" (PDF). Communications of the ACM. 13 (6): 377–387. doi:10.1145/362384.362685. Diakses tanggal 2020-04-29. 
  2. ^ "The Definitive Glossary of Higher Mathematical Jargon — Relation". Math Vault (dalam bahasa Inggris). 2019-08-01. Diakses tanggal 2019-12-12. 
  3. ^ "Relation - Encyclopedia of Mathematics". www.encyclopediaofmath.org. Diakses tanggal 2019-12-12. 
  4. ^ "Definition of n-ary Relation". cs.odu.edu. Diakses tanggal 2019-12-12. 
  5. ^ Nivat, Maurice (1981). Astesiano, Egidio; Böhm, Corrado, ed. "Infinitary relations". CAAP '81. Lecture Notes in Computer Science (dalam bahasa Inggris). 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. Diakses tanggal 2019-12-11. 
  7. ^ De Morgan, A. (1858) "On the syllogism, part 3" in Heath, P., ed. (1966) On the syllogism and other logical writings. Routledge. P. 119,

Bibliografi

  • Codd, Edgar Frank (1990). The Relational Model for Database Management: Version 2 (PDF). Boston: Addison-Wesley. ISBN 978-0201141924. 
  • Bourbaki, N. (1994) Elements of the History of Mathematics, John Meldrum, trans. Springer-Verlag.
  • Carnap, Rudolf (1958) Introduction to Symbolic Logic with Applications. Dover Publications.
  • Halmos, P.R. (1960) Naive Set Theory. Princeton NJ: D. Van Nostrand Company.
  • Lawvere, F.W., and R. Rosebrugh (2003) Sets for Mathematics, Cambridge Univ. Press.
  • Lewis, C.I. (1918) A Survey of Symbolic Logic, Chapter 3: Applications of the Boole—Schröder Algebra, via Internet Archive
  • Lucas, J. R. (1999) Conceptual Roots of Mathematics. Routledge.
  • Maddux, R.D. (2006) Relation Algebras, vol. 150 in 'Studies in Logic and the Foundations of Mathematics'. Elsevier Science.
  • Merrill, Dan D. (1990) Augustus De Morgan and the logic of relations. Kluwer.
  • Peirce, C.S. (1870), "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic", Memoirs of the American Academy of Arts and Sciences 9, 317–78, 1870. Reprinted, Collected Papers CP 3.45–149, Chronological Edition CE 2, 359–429.
  • Peirce, C.S. (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, 2nd ed. Cambridge Univ. Press.
  • Suppes, Patrick (1960/1972) Axiomatic Set Theory. Dover Publications.
  • Tarski, A. (1956/1983) Logic, Semantics, Metamathematics, Papers from 1923 to 1938, J.H. Woodger, trans. 1st edition, Oxford University Press. 2nd edition, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.
  • Ulam, S.M. and Bednarek, A.R. (1990), "On the Theory of Relational Structures and Schemata for Parallel Computation", pp. 477–508 in A.R. Bednarek and Françoise Ulam (eds.), Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators, University of California Press, Berkeley, CA.
  • Ulam, S.M. (1990) Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators in A.R. Bednarek and Françoise Ulam, eds., University of California Press.
  • Roland Fraïssé (2000) [1986] Theory of Relations, North Holland