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

در ریاضی یک مجموعه را نسبت به یک عمل بسته می‌گویند، اگر آن عمل روی اعضای مجموعه یک عضو از همان مجموعه را تولید کند. برای نمونه اعداد حقیقی نسبت به عمل تفریق بسته هستند اما اعداد طبیعی نه. اگر یک مجموعه مانند S نسبت به عملی مثل * بسته نباشد، کوچکترین مجموعه‌ای شامل S که نسبت به * بسته باشد، یک بَستار[1] (به انگلیسی: Closure) برای S خوانده می‌شود.

بستار رابطه‌ها

فرض کنید 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 نامیده می‌شود)[2]

بستار تقارنی

رابطهٔ {(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ⁿ= R^n-1oR

برای اینکه تعریف 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^۳= R^۲oR. یعنی R^۳ شامل همهٔ عضوهای (x,z) است به شرطی که (x,y) عضو R و (y,z) عضو R^۲ باشد پس R^۳ شامل (a,d) نیز هست چون (a,b) عضو R و (b,d) عضو R^۲ است.[3][4]

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

R^* = $\bigcup _{n=1}^{\infty }$ Rⁿ

منابع

«بَستار» [ریاضی] هم‌ارزِ «closure»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر پنجم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۷۸-۹۶۴-۷۵۳۱-۷۶-۴ (ذیل سرواژهٔ بَستار3)
Gunther Schmidt (2011) Relational Mathematics, pages 169 and 227, Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press شابک ‎۹۷۸−۰−۵۲۱−۷۶۲۶۸−۷
Gunter Schmidt and M. Winter (2018) Relational Topology, Lecture Notes in Mathematics vol. 2208, Springer Verlag, شابک ‎۹۷۸−۳−۳۱۹−۷۴۴۵۱−۳
Baader، Franz (۱۹۹۸). Term Rewriting and All That. Cambridge University Press. صص. ۸–۹.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] «بَستار» [ریاضی] هم‌ارزِ «closure»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر پنجم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۷۸-۹۶۴-۷۵۳۱-۷۶-۴ (ذیل سرواژهٔ بَستار3)

[2] Gunther Schmidt (2011) Relational Mathematics, pages 169 and 227, Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press شابک ‎۹۷۸−۰−۵۲۱−۷۶۲۶۸−۷

[3] Gunter Schmidt and M. Winter (2018) Relational Topology, Lecture Notes in Mathematics vol. 2208, Springer Verlag, شابک ‎۹۷۸−۳−۳۱۹−۷۴۴۵۱−۳

[4] Baader، Franz (۱۹۹۸). Term Rewriting and All That. Cambridge University Press. صص. ۸–۹.