உள்ளடக்கத்துக்குச் செல்

கடப்பு உறவு

கட்டற்ற கலைக்களஞ்சியமான விக்கிப்பீடியாவில் இருந்து.

கணிதத்தில் 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

மேற்கோள்கள்

[தொகு]
  1. 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".
  2. Steven R. Finch, "Transitive relations, topologies and partial orders" பரணிடப்பட்டது 2007-06-28 at the வந்தவழி இயந்திரம், 2003.
  3. Götz Pfeiffer, "Counting Transitive Relations", Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
  4. Gunnar Brinkmann and Brendan D. McKay,"Counting unlabelled topologies and transitive relations"

உசாத்துணை

[தொகு]

வெளியிணைப்புகள்

[தொகு]
"https://ta.wikipedia.org/w/index.php?title=கடப்பு_உறவு&oldid=3237716" இலிருந்து மீள்விக்கப்பட்டது