بستار (ریاضی): تفاوت میان نسخه‌ها

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

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

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

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

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

رابطهٔ {(R={(1,3۱،۳),،(1,4۱،۴),،(2,1۲،۱),،(3,2۳،۲ روی مجموعهٔ {A={1,2,3,4۱،۲،۳،۴ را در نظر بگیرید.

این رابطه تراگذری(تعدی) نیست زیرا شامل همهٔ عضوهای (a,ca،c) به شرط اینکه (a,ba،b) و (b,cb،c) عضو R باشند نمی‌شود. عضوهای به این فرم عبارت اند از (1,2۱،۲) ,، (2,3۲،۳) ,، (2,4۲،۴) و (3,1۳،۱) اضافه کردن این عضوها رابطهٔ R را تعدی نخواهد کرد! چون رابطهٔ حاصل شامل اعضا ی (3,1۳،۱) و (1,4۱،۴) است ولی عضو (3,4۳،۴) را ندارد این مثال نشان می‌دهد که ساختن بستار تعدی رابطهٔ R به سادگی ساختن بستار بازتابی یا تقارنی رابطهٔ R نیست.

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

:R^1۱=R

:Rⁿ= R^n-1۱oR

گفتیم در مرحلهٔ اول برای اینکه R تعدی کنیم لازم است همهٔ اعضای (a,ca،c) که (a,ba،b) و (b,cb،c) عضو R است ولی خودشان عضو R نیستند را به R اضافه کنیم این مطلب معادل با این است که R^2۲ یا RoR را با R اجتماع کنیم به عبارت دیگر R∪R^2۲. حال فرض کنید سه عضو (c,dc،d) ,، (b,cb،c) و (a,ba،b) عضو R باشند می‌دانیم با این عمل اعضای (a,ca،c) و (b,db،d) به R اضافه می‌شوند حال چون دو عضو (a,ba،b) و (b,db،d) عضو مجموعهٔ حاصل هستند باید عضو (a,da،d) هم عضو آن باشد. اما اگر به تعریف R^3۳ دقت کنیم در این تعریف داریم R^3۳= R^2۲oR.یعنی R^3۳ شامل همهٔ عضوهای (x,zx،z) است به شرطی که (x,yx،y) عضو R و (y,zy،z) عضو R^2۲ باشد پس R^3۳ شامل (a,da،d) نیز هست چون (a,ba،b) عضو R و (b,db،d) عضو R^2۲ است.

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