به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
616 بازدید
در دانشگاه توسط maara (260 امتیاز)

برای اثبات حالت 3به 4 قضیه در صفحه ی 178 و در حالتی که فرض بر این است که $s=1$ به تناقض رسیده است.نحوه ی بدست آوردن این تناقض مبهم است.لطفا در صورت امکان تشریح کنید.

مرجع: کتاب هرزگ هیبی
توسط erfanm (13,871 امتیاز)
ویرایش شده توسط fardina
لطفا قوانین سایت رو رعایت کنید:
عنوان سوال چطور باید باشد؟
عنوان سوال باید گویای سوال شما در یک جمله باشد. لطفا سعی کنید عنوان با وجود کوتاه بودن کامل و دقیق باشد. در این صورت بعدا اگر کسی سوال مشابه سوال شما را داشته باشد سریعتر می تواند آن را پیدا کند.
لطفا مساله خود را کامل توضیح دهید و از نوشتن عباراتی نظیر " با توجه به نمودار صفحه 16 از کتاب..." یا "بنابر قضیه 1.1 از کتاب..." پرهیز کنید و تمام مفروضات مورد نیاز را بنویسید.

1 پاسخ

+1 امتیاز
توسط erfanm (13,871 امتیاز)
ویرایش شده توسط erfanm

در ابتدای قضیه میدانیم که $ B=[n] \setminus \bigcup_{i=1}^m F_{i} $ پس $ H_{1} \bigcap ( \bigcup_{i=1}^m F_{i}) = \emptyset $ اما از اینکه $H_{1} \subseteq X= \bigcup_{i=1}^m (F_{i} \setminus v_{i} ) $ و با توجه به اینکه $H_{1} \subseteq X \subseteq \bigcup_{i=1}^m F_{i} $ این تناقض است.

..............................................................................................

ویرایش پس از دیدگاه

..............................................................................................

به راحتی ثابت می شود که $X $ یک پوشش راسی است(در ابتدای اثبات قضیه در کتاب ثابت شده است)

اولا از آنجایی که $ H_{1}=[n] \setminus \bigcup_{i=1}^m F_{i} $ پس طبق آنچه در ابتدای اثبات گفته شده $ H_{1}$ فستی است که دارای راس آزاد نیست.

حال فرض کنید $h $ عنصر دلخواهی در $ H_{1}$ باشد چون آزاد نیست پس یک $ F_{i} $ وجود دارد که $ h \in F_{i} $ و چون $ F_{i} $ یک فست است پس با راس آزاد این فست یا همان $ v_{i} $ یال تشکیل می دهد ولی در پوشش راسی $ X $ راس $ v_{i} $ را نداریم لذا ناچارا باید $h \in X $باشد پس $H_{1} \subseteq X $است و از اینکه باتوجه به تعریف $ X \subseteq \bigcup_{i=1}^m F_{i} $ است پس $H_{1} \subseteq \bigcup_{i=1}^m F_{i} $

توسط maara (260 امتیاز)
+1
چرا H1⊆X مگه H1 همون B نیست ؟
توسط maara (260 امتیاز)
+1
به نظرم این قسمت که گفته "فرض کنید h عنصر دلخواهی در H1 باشد چون آزاد نیست پس یک Fi وجود دارد که h∈Fi ."این اتفاق نمی افته چون ما B رو طوری انتخاب کردیم که Fi ها رو نداشته باشه.و یه جور تناقضه
توسط erfanm (13,871 امتیاز)
خوب معلومه تناقضه اصلا میخواهیم با زبان ریاضی به همین تناقض برسیم چون ما فرض کردیم از اول که $B$ای وجود داره واین حالت میگه اگر فقط یک فست داشته باشه چنین $B$ای نمیتونه وجود داشته باشد  که با زبان ریاضی میشه همون چیزی که نوشته شده
این چرخ فلک که ما در او حیرانیم<br> فانوس خیال از او مثالی دانیم<br> خورشید چراغ دان و عالم فانوس<br> ما چون صوریم کاندرو حیرانیم
...