கடப்பு உறவு
கணிதத்தில் X கணத்தின் மீது வரையறுக்கப்பட்ட ஒரு ஈருறுப்பு உறவு R ஒரு கடப்பு உறவு (transitive relation) எனில், R இன் கீழ் அக்கணத்திலுள்ள ஒரு உறுப்பு a ஆனது b உடன் தொடர்புள்ளதாகவும், b ஆனது c உடன் தொடர்புள்ளதாகவும் இருந்தால், a ஆனது c உடன் தொடர்பு கொண்டிருக்கும். பகுதி வரிசை உறவுகளுக்கும், சமான உறவுகளுக்கும் கடப்புத்தன்மை முக்கியமான பண்பு ஆகும்.
வரையறை[தொகு]
கணக்கோட்டின்படி, கடப்புறவின் வரையறை:
எடுத்துக்காட்டுகள்[தொகு]
"விடப் பெரியது," "குறைந்தபட்சப் பெரியது," "விடச் சிறியது," "சமம்" ஆகியவை கடப்புறவுகள்:
- A > B, B > C எனில், A > C
- A ≥ B, B ≥ C எனில், A ≥ C
- A < B, B < C எனில், A < C
- A ≤ B, B ≤ C எனில், A ≤ C
- A = B, B = C எனில், A = C.
"உட்கணம்," "வகுக்கும்," என்பவையும் கடப்புறவுக்கு எடுத்துக்காட்டுகளாகும்.
பண்புகள்[தொகு]
அடைவுப் பண்புகள்[தொகு]
- ஒரு கடப்புறவின் மறுதலையும் கடப்புறவாக இருக்கும்.
எடுத்துக்காட்டாக,
கடப்புறவு விடப் பெரியது என்பதன் மறுதலை விடச் சிறியது ஆகும். இதுவும் ஒரு கடப்பு உறவு.
- இரு கடப்புறவுகளின் வெட்டு, எப்போதும் ஒரு கடப்புறவாகவே இருக்கும்.
- ≥ , ≤ ஆகிய இரு கடப்புறவுகளின் வெட்டாக அமையும் உறவு = ஆகும். இதுவும் ஒரு கடப்புறவே.
- இரு கடப்புறவுகளின் ஒன்றிப்பும் ஒரு கடப்புறவாகும்.
- ஒரு கடப்புறவின் நிரப்பியாக அமையும் உறவு கடப்புறவாக இருக்காது.
எடுத்துக்காட்டாக, "சமம்" ஒரு கடப்புறவு. இதன் நிரப்பியான "சமமல்ல" என்பது கடப்புறவு இல்லை. (அதிகபட்சமாக ஒரு உறுப்பு கொண்டுள்ள கணத்தில் மட்டும் இது கடப்புறவாக இருக்கும்).
பிற பண்புகள்[தொகு]
எதிர்வு உறவாக இல்லாமல் இருந்தால், இருந்தால் மட்டுமே ஒரு கடப்பு உறவு, சமச்சீர்மையற்றதாக இருக்க முடியும்.[1]
கடப்பு உறவுகளின் எண்ணிக்கை[தொகு]
ஒரு முடிவுறு கணத்தின் மீது வரையறுக்கப்படக்கூடிய கடப்பு உறவுகளின் எண்ணிக்கையைக் கணக்கிடக்கூடிய பொது வாய்ப்பாடுகள் இல்லை (OEIS-இல் வரிசை A006905) .[2] எனினும், எதிர்வு-சமச்சீர்-கடப்பு உறவுகள் (சமான உறவுகள்) – (OEIS-இல் வரிசை A000110) , சமச்சீர்-கடப்பு உறவுகள் சமச்சீர்-கடப்பு-எதிர்சமச்சீர் உறவுகள் முழு-கடப்பு-எதிர்சமச்சீர் உறவுகள் ஆகியவற்றின் எண்ணிக்கையைக் காணும் வாய்ப்பாடு உள்ளது.[3][4]
| பல்வேறு n-உறுப்பு ஈருறுப்பு உறவுகளின் எண்ணிக்கை | ||||||||
|---|---|---|---|---|---|---|---|---|
| n | அனைத்தும் | கடப்பு | எதிர்வு | முன்வரிசை உறவு | பகுதி வரிசை உறவு | முழு முன்வரிசை உறவு | முழு வரிசை உறவு | சமான உறவு |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 16 | 13 | 4 | 4 | 3 | 3 | 2 | 2 |
| 3 | 512 | 171 | 64 | 29 | 19 | 13 | 6 | 5 |
| 4 | 65536 | 3994 | 4096 | 355 | 219 | 75 | 24 | 15 |
| OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
மேற்கோள்கள்[தொகு]
- ↑ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I. Prague: School of Mathematics - Physics Charles University. பக். 1 இம் மூலத்தில் இருந்து 2013-11-02 அன்று. பரணிடப்பட்டது.. https://web.archive.org/web/20131102214049/http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf. பார்த்த நாள்: 2015-09-29. Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".
- ↑ Steven R. Finch, "Transitive relations, topologies and partial orders" பரணிடப்பட்டது 2007-06-28 at the வந்தவழி இயந்திரம், 2003.
- ↑ Götz Pfeiffer, "Counting Transitive Relations", Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
- ↑ Gunnar Brinkmann and Brendan D. McKay,"Counting unlabelled topologies and transitive relations"
உசாத்துணை[தொகு]
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, ISBN 0-201-19912-2.
- Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7.
வெளியிணைப்புகள்[தொகு]
- Hazewinkel, Michiel, ed. (2001), "Transitivity", Encyclopedia of Mathematics, Springer, ISBN 978-1556080104
- Transitivity in Action at cut-the-knot