கடப்பு உறவு
கணிதத்தில் 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