بستار (ریاضی)

فرض کنید R رابطه‌ای روی مجموعهٔ A باشد. R ممکن است بعضی از ویژگی‌ها مثلاً ویژگی P (که می‌تواند بازتابی، تقارنی، تعدی و… باشد) را داشته باشد یا نداشته باشد. اگر رابطه‌ای مانند S وجود داشته باشد که ویژگی P را دارا باشد و رابطهٔ R را شامل شود و زیر مجموعهٔ هر رابطهٔ دیگری که ویژگی P را دارد و رابطهٔ R زیر مجموعهٔ آن است باشد آنگاه S بستار رابطهٔ R نسبت به ویژگی P است. در زیر بستار رابطه‌های بازتابی، تقارنی و تعدی را می‌بینیم.

بستار بازتابی

رابطهٔ {(R={(۱٬۱)، (۱٬۲)، (۲٬۱)، (۳٬۲ روی مجموعهٔ {A={۱٬۲٬۳ را در نظر بگیرید R بازتابی نیست برای اینکه R را بازتابی کنیم کافی است دو عضو (۲٬۲) و (۳٬۳) را به R اضافه کنیم چون این دو عضو تنها دو عضو به شکل (a,a) هستند که a عضو A است و (a,a) عضو A نیست. رابطهٔ بازتابی ساخته شده شامل رابطهٔ R است همچنین این رابطه زیرمجموعهٔ همهٔ روابط بازتابی است که R زیر مجموعهٔ آنهاست پس این مجموعهٔ جدید بستار بازتابی رابطهٔ R است.

در حالت کلی برای اینکه بستار بازتابی رابطهٔ R را بدست آوریم کافی است همهٔ عضوهای (a,a) متمایز ممکن که a عضو مجموعهٔ A باشد و (a,a) عضو R نباشد را به R اضافه کنیم پس اگر تعریف کنیم { Δ={(a,a) | a ∈ A بستار بازتابی R از رابطهٔ R∪Δ بدست می‌آید (Δ رابطهٔ قطری روی A نامیده می‌شود)

بستار تقارنی

رابطهٔ {(R={(۱٬۱)، (۱٬۲)، (۲٬۲)، (۲٬۳)، (۳٬۱)، (۳٬۲ روی مجموعهٔ {A={۱٬۲٬۳ را در نظر بگیرید این رابطه تقارنی نیست. برای اینکه R را تقارنی کنیم کافی است دو عضو (۱٬۳) و (۲٬۱) را به R اضافه کنیم زیرا این دو تنها عضوهای به فرم (a,b) هستند که (b,a) عضو R است ولی خودشان عضو R نیستند. مجموعهٔ حاصل تقارنی است و شامل R نیز می‌باشد و همچنین زیر مجموعهٔ هر مجموعهٔ تقارنی است که R زیر مجموعهٔ آنهاست پس این رابطه بستار تقارنی R است.

از این مثال می‌توان نتیجه گرفت که بستار تقارنی R با اضافه کردن هر عضو به فرم (a,b) به R بدست می‌آید به شرط اینکه (b,a) عضو R باشد ولی خود (a,b) عضو R نباشد. اگر تعریف کنیم {R={(a,b)|(b,a)∈R بستار تقارنی R از رابطهٔ R∪R بدست می‌آید. (R رابطهٔ معکوس رابطهٔ R نامیده می‌شود)

بستار تراگذری

فرض کنید می‌خواهیم بستار تراگذری (تعدی) رابطهٔ R را بدست آوریم آیا اضافه کردن هر عضو به فرم (a,c) به R به شرط اینکه (a,b) و(b,c) عضو R باشند کافی است؟

به مثال دقت کنید:

رابطهٔ {(R={(۱٬۳)، (۱٬۴)، (۲٬۱)، (۳٬۲ روی مجموعهٔ {A={۱٬۲٬۳٬۴ را در نظر بگیرید. این رابطه تراگذری (تعدی) نیست زیرا شامل همهٔ عضوهای (a,c) به شرط اینکه (a,b) و (b,c) عضو R باشند نمی‌شود. عضوهای به این فرم عبارت اند از (۱٬۲)، (۲٬۳)، (۲٬۴) و (۳٬۱) اضافه کردن این عضوها رابطهٔ R را تعدی نخواهد کرد! چون رابطهٔ حاصل شامل اعضا ی (۳٬۱) و (۱٬۴) است ولی عضو (۳٬۴) را ندارد این مثال نشان می‌دهد که ساختن بستار تعدی رابطهٔ R به سادگی ساختن بستار بازتابی یا تقارنی رابطهٔ R نیست.

برای بدست آوردن تعریف کلی به چند تعریف اولیه نیاز داریم که در زیر آمده‌است.

ترکیب دو تابع:

فرض کنید R رابطه‌ای از A به S,B رابطه‌ای از B به C باشد، رابطهٔ SoR رابطه‌ای از A به C است که شامل همهٔ عضوهای به صورت (a,c) است به طوریکه (a,b) عضو R و (b,c) عضو S باشد.

R:

R را به صورت بازگشتی تعریف می‌کنیم داریم:

R=R

R= RoR

برای اینکه تعریف R درست باشد لازم است که R رابطه‌ای روی یک مجموعه باشد.

حال اگر R بستار تعدی رابطهٔ R باشد داریم:

این مطلب را به صورت شهودی اثبات می‌کنیم اثبات دقیق آن با استفاده از نظریه گراف‌ها ممکن است.

گفتیم در مرحلهٔ اول برای اینکه R تعدی کنیم لازم است همهٔ اعضای (a,c) که (a,b) و (b,c) عضو R است ولی خودشان عضو R نیستند را به R اضافه کنیم این مطلب معادل با این است که R یا RoR را با R اجتماع کنیم به عبارت دیگر R∪R. حال فرض کنید سه عضو (c,d)، (b,c) و (a,b) عضو R باشند می‌دانیم با این عمل اعضای (a,c) و (b,d) به R اضافه می‌شوند حال چون دو عضو (a,b) و (b,d) عضو مجموعهٔ حاصل هستند باید عضو (a,d) هم عضو آن باشد. اما اگر به تعریف R دقت کنیم در این تعریف داریم R= RoR. یعنی R شامل همهٔ عضوهای (x,z) است به شرطی که (x,y) عضو R و (y,z) عضو R باشد پس R شامل (a,d) نیز هست چون (a,b) عضو R و (b,d) عضو R است.

پس می‌توان رابطهٔ بهتری به صورت R∪R∪R نوشت و به بستار تعدی R نزدیک تر شد اما این کافی نیست. به صورت بالا می‌توان مشاهده کرد که برای بدست آوردن بستار تعدی R لازم است اجتماع Rها (n∈N) را بدست آوریم یا همان:

R = ${\displaystyle \bigcup _{n=1}^{\mathrm{\infty }}}$

• مشارکت کنندگان ویکی‌پدیا((Closure (mathematics) در دانشنامه ویکی‌پدیای انگلیسی. بازبینی در ۳۱ می ۲۰۱۹.