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

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

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

1 پاسخ

+1 امتیاز
توسط erfanm
ویرایش شده توسط 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
+1
چرا H1⊆X مگه H1 همون B نیست ؟
توسط maara
+1
به نظرم این قسمت که گفته "فرض کنید h عنصر دلخواهی در H1 باشد چون آزاد نیست پس یک Fi وجود دارد که h∈Fi ."این اتفاق نمی افته چون ما B رو طوری انتخاب کردیم که Fi ها رو نداشته باشه.و یه جور تناقضه
توسط erfanm
خوب معلومه تناقضه اصلا میخواهیم با زبان ریاضی به همین تناقض برسیم چون ما فرض کردیم از اول که $B$ای وجود داره واین حالت میگه اگر فقط یک فست داشته باشه چنین $B$ای نمیتونه وجود داشته باشد  که با زبان ریاضی میشه همون چیزی که نوشته شده

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...