ت.7 · صور المجموعات، علاقات التكافؤ والنفي المنطقي

تحضير GRE للطلاب الجامعيين. أهداف محلية ضمن نطاق ETS المراجَع؛ هذا تعليم أصلي، وليس اختباراً رسمياً أو تنبئاً بالدرجات.

المواصفات المسبقة: عمليات المجموعات، الكمية، الدوال والإثبات الأساسي.

• أثبت هويات الصور وميز بين الانتماء والمساواة
• تحقق من الانعكاسية والتناظر والانتقالية بالحالات الصريحة
• أنكر الاستلزمات والكلمات الكمية دون تغيير نطاقها

الصورة العكسية: مجموعة المدخلات التي تقع مخارجها في مجموعة مستهدفة محددة.

العلاقة التكافؤ: علاقة انعكاسية وتناظرية وانتقالية.

بالنسبة لـ f:X→Y و A⊆X، تتكون صورة f(A) من جميع المخارج f(a) حيث a في A. النقطة تكون في f(A∪B) إذا وجئت من A أو B، لذا f(A∪B)=f(A)∪f(B). إذا كان A⊆B، فإن f(A)⊆f(B). بالنسبة للتقاطع فقط f(A∩B)⊆f(A)∩f(B) تلقائياً: قد يأتي نفس المخرج من مدخلات مختلفة. استخدم f(x)=x²، A={−1}، B={1}؛ الصورة اليسرى فارغة بينما التقاطع الأيمن هو {1}.

تتصرف الصور العكسية بشكل مختلف. بالنسبة لـ C⊆Y، f⁻¹(C) هنا تشير إلى مجموعة جميع المدخلات المرسلة إلى C، حتى لو لم يكن للدالة دالة عكسية. الانتماء إلى صورتين عكسيتين يعني أن نفس المدخل يترجم إلى كلتا المجموعتين المستهدفتين. بالتالي تحافظ الصور العكسية على الاتحادات والتقاطعات والمكممات بالنسبة للمجال/المجال المقابل المذكور. لا تنقل نظرية حول الصور العكسية إلى الصور. إذا كانت f متباينة، فإن تقاطعات الصور تصبح مساوية، لأن المخارج المتساوية تجبر على وجود مدخل مشترك.

العلاقة R على X انعكاسية عندما يكون xRx لكل x، تناظرية عندما يفرض xRy أن yRx، وانتقالية عندما يفرض xRy و yRz أن xRz. الثلاثة جميعها يشكلون علاقة تكافؤ؛ فئاتها تقسم X. على الأعداد الصحيحة، xRy عندما يكون x و y لهما نفس الباقي قسمة أربعة يعطي أربع فئات. العلاقة |x−y|≤1 انعكاسية وتناظرية لكنها ليست انتقالية: 0R1 و 1R2 بينما 0 غير مرتبط بـ 2. التحقق من رسم بياني واحد أو خاصيتين غير كافٍ.

يكون الاستلزام P⇒Q كاذباً بالضبط عندما يكون P صحيحاً و Q خاطئاً. وبالتالي نفي P⇒(Q∧R) هو P∧(¬Q∨¬R)، وليس ¬P⇒(¬Q∧¬R). نفي "كل x له الخاصية A" يعطي "يوجد x بدون A"؛ نفي "يوجد x" يعطي "كل x ليس كذلك". المثال المضاد يمكنه نفي ادعاء عالمي، بينما الأمثلة لا تثبته. تحتفظ الكلمات الكمية بترتيبها عند نفيها فردياً: ¬(∀x∃y S(x,y)) هي ∃x∀y ¬S(x,y).

ليكن f يحوّل a و b كلاهما إلى التسمية L. مع A={a}، B={b}، f(A∩B)=∅ لكن f(A)∩f(B)={L}. بالنسبة لـ xRy المعرّفة بـ x=y أو x=−y على R، الانعكاسية والتناظر يتبعان مباشرة، وتغييران في الإشارة لا يزالان يعطيان z=±x، مما يثبت التعددية. الفئات هي {x,−x}، مع {0} كعنصر وحيد. العبارة الخاطئة "كل ملف مخزن له هاش" تعني أن هناك على الأقل ملفاً واحداً مخزناً ليس له هاش؛ ولا تعني أن كل الملفات تفتقر للهاش.

f⁻¹(C) قد تعني مجموعة ما قبل الصورة دون وجود دالة عكسية. قد تفشل العلاقة الانعكاسية والمتناظرة في التعددية. انفي العبارة كاملة قبل تبسيط أجزائها.

أثبت $f(A\cap B)\subseteq f(A)\cap f(B)$. قدم مثالاً للانتماء الصارم. تحت أي افتراض إضافي على f تتبع المساواة لجميع A و B؟

حل نموذجي

إذا كان $y=f(x)$ لـ $x\in A\cap B$، فإن x ينتمي إلى كل مجموعة، لذا y ينتمي إلى كل صورة. بالنسبة للصراحة، خذ a,b مختلفين ويترجمان إلى نفس c وأخذ $A=\{a\}$، $B=\{b\}$. الصورة اليسرى فارغة والتقاطع الأيمن هو $\{c\}$. إذا كانت f متباينة و $y=f(a)=f(b)$ مع $a\in A,b\in B$، فإن التباين يعطي a=b في التقاطع، مما يثبت الانتماء العكسي. ومن ناحية أخرى يظهر مثال المفرد أن المساواة لجميع الأزواج تجبر التباين.

على الأعداد الصحيحة، عرّف $aRb$ عندما يكون $a-b$ قابلاً للقسمة على 4. أثبت أنه علاقة تكافؤ ووصف كل فئة. نفي: "لكل عدد صحيح n يوجد عدد صحيح m أكبر من n له الخاصية P."

تحقق بعد المحاولة

الانعكاسية تستخدم $a-a=0$؛ التماثل يستخدم سالب مضاعف لأربعة؛ الترانزيتيفية تستخدم مجموع مثل هذين المضاعفين. الفئات هي بقايا القسمة على أربعة الأربعة؛ فئة a هي $a+4\mathbb Z$. النفي هو: يوجد عدد صحيح n بحيث يفشل كل عدد صحيح m أكبر من n في P. يكافئ $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$. إنه لا يدعي أن P تفشل لكل عدد صحيح، ولا أن m أصغر من أو يساوي n لكل m.