கடப்பு உறவு
கணிதத்தில் 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 (PDF). Prague: School of Mathematics - Physics Charles University. p. 1. Archived from the original (PDF) on 2013-11-02. பார்க்கப்பட்ட நாள் 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, பன்னாட்டுத் தரப்புத்தக எண் 0-201-19912-2.
- Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, பன்னாட்டுத் தரப்புத்தக எண் 978-0-521-76268-7.
வெளியிணைப்புகள்
தொகு- Hazewinkel, Michiel, ed. (2001), "Transitivity", Encyclopedia of Mathematics, Springer, பன்னாட்டுத் தரப்புத்தக எண் 978-1556080104
- Transitivity in Action at cut-the-knot