المقالات

1.4: مجموعات معدودة وغير قابلة للعد


التعريف 1.18

المجموعة (S ) قابلة للعد إذا كان هناك انحراف (f: mathbb {N} rightarrow S ). المجموعة اللانهائية التي لا يوجد لها مثل هذا التحيز تسمى غير معدودة.

الاقتراح 1.19

تحتوي كل مجموعة لانهائية (S ) على مجموعة فرعية قابلة للعد.

الاقتراح 1.19

تحتوي كل مجموعة لانهائية (S ) على مجموعة فرعية قابلة للعد.

إثبات

اختر عنصرًا (s_ {1} ) من (S ). الآن (S - {s_ {1} } ) ليس فارغًا لأن (S ) ليس محدودًا. لذا اختر (s_ {2} ) من (S - {s_ {1} } ). إذن ، (S - {s_ {1}، s_ {2} } ) ليس فارغًا لأن (S ) غير محدود. بهذه الطريقة ، يمكننا إزالة (s_ {n + 1} ) من (S - {s_ {1} ، s_ {2} ، cdots ، s_ {n} } ) للجميع (n ). ثم مجموعة ( {s_ {1} ، s_ {2} ، cdots } ) قابلة للعد ومضمنة في (S ).

لذا فإن المجموعات القابلة للعد هي أصغر المجموعات اللانهائية بمعنى أنه لا توجد مجموعات لا نهائية لا تحتوي على مجموعة قابلة للعد. لكن هناك بالتأكيد مجموعات أكبر ، كما سنرى لاحقًا.

نظرية 1.20

المجموعة ( mathbb {R} ) غير معدودة.

إثبات

الدليل هو أحد أشهر حجج الرياضيات: حجة كانتور القطرية [8]. تم تطوير الحجة في خطوتين.

لنفترض (T ) أن تكون مجموعة التسلسلات شبه اللانهائية المكونة من الرقمين 0 و 2. عنصر (t في T ) له شكل (t = t_ {1} t_ {2} t_ {3 } dots ) ​​حيث (t_ {i} in {0، 2 } ). الخطوة الأولى للإثبات هي إثبات أن (T ) غير معدود. لذا افترض أنه قابل للعد. ثم يسمح لنا الانحراف (t ) بين ( mathbb {N} ) و (T ) بتعريف التسلسل بشكل فريد (t (n) ) ، التسلسل الفريد المرتبط بـ (n ) . علاوة على ذلك ، فإنها تشكل قائمة شاملة لعناصر (T ). على سبيل المثال ،

[t (1) = textbf {0}، 0،0،0،0،0،0،0،0،0،0، dots nonumber ]

[t (2) = 2، textbf {0}، 2،0،2،0،2،0،2،2،2، dots nonumber ]

[t (3) = 0،0، textbf {0}، 2،2،2،2،2،2،2،2، dots nonumber ]

[t (4) = 2،2،2، textbf {2}، 2،2،0،0،0،0،0، dots nonumber ]

[t (5) = 0،0،0،2، textbf {2}، 0،2،0،0،2،0، dots nonumber ]

[t (6) = 2،0،0،0،0، textbf {2}، 0،0،0،2،2، dots nonumber ]

[ vdots nonumber ]

أنشئ (t ^ {*} ) على النحو التالي: لكل (n ) ، يختلف رقمه التاسع عن الرقم التاسع (t (n) ). في المثال أعلاه ، (t ^ {*} = textbf {2}، textbf {2}، textbf {2}، textbf {0}، textbf {2}، textbf {0}، النقاط ). لكن لدينا الآن تناقض ، لأن العنصر (t ^ {*} ) لا يمكن أن يظهر في القائمة. بمعنى آخر ، لا يوجد أي اعتراض من ( mathbb {N} ) إلى (T ). ومن ثم لا يوجد انحياز بين ( mathbb {N} ) و (T ).

الخطوة الثانية هي إظهار أن هناك مجموعة فرعية (K ) من ( mathbb {R} ) بحيث لا يوجد اعتراض (وبالتالي لا يوجد اعتراض) من ( mathbb {N} ) إلى (ك ). لنفترض (t ) أن يكون تسلسلاً يحتوي على أرقام (t_ {i} ). حدد (f: T rightarrow mathbb {R} ) كما يلي

[f (t) = sum_ {i = 1} ^ { infty} t_ {i} 3 ^ {- i} nonumber ]

إذا كان (s ) و (t ) عبارة عن تسلسلين متميزين في (T ) ، فبالنسبة لبعض (ك ) يتشاركون الأرقام (ك -1 ) الأولى ولكن (t_ {ك} = 2 ) و (s_ {ك} = 0 ). هكذا

[f (t) -f (s) = 2 cdot 3 ^ {- k} + sum_ {i = k + 1} ^ { infty} (t_ {i} -s_ {i}) 3 ^ { -i} ge 2 cdot 3 ^ {- k} -2 sum_ {i = k + 1} ^ { infty} 3 ^ {- i} = 3 ^ {- k} nonumber ]

وبالتالي فإن (f ) هو حقنة. لذلك (f ) هو انحياز بين (T ) والمجموعة الفرعية (K = f (T) ) من ( mathbb {R} ). إذا كان هناك تخمين (g ) من ( mathbb {N} ) إلى (K = f (T) ) ، إذن ،

[ mathbb {N} xrightarrow { text {g}} K xleftarrow { text {f}} T nonumber ]

ومن ثم فإن (f ^ {- 1} g ) هو نبذ من ( mathbb {N} ) إلى (T ). بالخطوة الأولى ، هذا مستحيل. لذلك ، لا يوجد اعتراض (g ) من ( mathbb {N} ) إلى (K ) ، ناهيك عن ( mathbb {N} ) إلى ( mathbb {R} ) .

النتيجة الطبيعية 1.21

(1) مجموعة التسلسلات اللانهائية في ( {1،2، cdots، b-1 } ^ { mathbb {N}} ) غير معدودة.

(2) مجموعة التسلسلات المحدودة (ولكن بدون قيود) في ( {1، 2، cdots، b-1 } ^ { mathbb {N}} ) قابلة للعد.

إثبات

إثبات (i) هو نفس الدليل على أن (T ) غير معدود في إثبات النظرية 1.20. يتكون دليل (ii) من كتابة جميع (b ) الكلمات التي يبلغ طولها 1 أولاً ، ثم جميع (b ^ {2} ) الكلمات ذات الطول 2 ، وهكذا. كل سلسلة محدودة ستحدث في القائمة.

نظرية 1.22

(i) المجموعة ( mathbb {Z} ^ 2 ) قابلة للعد.

(ii) ( mathbb {Q} ) معدود.

إثبات

(i) يعتمد الإثبات على الشكل 2. حيث يتم تتبع مسار موجه ( gamma ) يمر عبر جميع نقاط ( mathbb {Z} ^ 2 ). تخيل أنك تبدأ من ((0 ، 0) ) وتسافر على طول ( جاما ) بسرعة الوحدة. احتفظ بمقياس (c in mathbb {N} ) يميز النقطة ((0 ، 0) ) بـ "1". ارفع قيمة العداد بمقدار 1 عندما تصل إلى نقطة ( mathbb {Z} ^ 2 ). يؤسس هذا انحيازًا بين ( mathbb {N} ) و ( mathbb {Z} ^ 2 ).

الشكل 2. مسار موجه ( gamma ) يمر عبر جميع نقاط ( mathbb {Z} ^ 2 ).

(2) السفر مرة أخرى على طول ( جاما ) بسرعة الوحدة. احتفظ بمقياس (c in mathbb {N} ) يميز النقطة ((0 ، 1) ) بـ "1". قم بزيادة قيمة العداد بمقدار 1. استمر في التحرك على طول المسار حتى تصل إلى النقطة التالية ((p، q) ) التي ليست من مضاعفات أي سابق ومثل هذا (q ) ليس صفرًا. ضع علامة على هذه النقطة بقيمة العداد. ( mathbb {Q} ) يحتوي على ( mathbb {N} ) وبالتالي فهو لانهائي. إن تحديد كل نقطة مميزة ((p، q) ) بالرقم المنطقي ( frac {p} {q} ) يؤسس قابلية العد ( mathbb {Q} ).

لاحظ أن هذه الحجة تخبرنا حقًا أن منتج مجموعة قابلة للعد ومجموعة أخرى قابلة للعد لا يزالان قابلين للعد. ينطبق الشيء نفسه على أي منتج محدود لمجموعة قابلة للعد. نظرًا لأن المجموعة غير المعدودة أكبر تمامًا من المجموعة المعدودة ، فهذا يعني بشكل بديهي أن المجموعة غير المعدودة يجب أن تكون أكبر بكثير من المجموعة القابلة للعد. في الواقع ، يُظهر امتداد الوسيطة أعلاه أن مجموعة الأرقام الجبرية قابلة للعد. وبالتالي ، بمعنى ما ، فإنه يشكل مجموعة فرعية صغيرة من كل الواقعية. من اللافت للنظر أن جميع القيم الحقيقية تقريبًا التي نعرف أي شيء عنها هي أرقام جبرية ، وهو الوضع الذي أشرنا إليه في نهاية القسم 1.4.

من المفيد والمهم أن يكون لديك تعريف أكثر عمومية عندما يكون لمجموعتين "نفس عدد العناصر".

التعريف 1.23

يُقال إن مجموعتين A و B لهما نفس العلاقة الأساسية إذا كان هناك انحياز (f: A rightarrow B ). تتم كتابته كـ (| A | = | B | ). إذا كان هناك حقنة (f: A rightarrow B ) ، إذن (| A | le | B | ).

التعريف 1.24

علاقة التكافؤ في مجموعة (A ) هي مجموعة (فرعية) ( mathbb {R} ) من الأزواج المرتبة في (A times A ) التي تفي بثلاثة متطلبات.

  • ((a، a) in mathbb {R} ) (الانعكاسية).
  • إذا كان ((a، b) in mathbb {R} ) ، إذن ((b، a) in mathbb {R} ) (تناظر).
  • إذا كان ((a، b) in mathbb {R} ) و ((b، c) in mathbb {R} ) ، فإن ((a، c) in mathbb {R } ) (انتقالية).

عادةً ما يتم اختصار ((a، b) in mathbb {R} ) إلى (a sim b ). الرمز الرياضي " (= )" هو معادل.

من السهل إظهار أن وجود نفس العلاقة الأساسية هو علاقة تكافؤ في المجموعات (تمرين 1.23). لاحظ أن أصل مجموعة محدودة هو مجرد عدد العناصر التي تحتوي عليها. يمكن العثور على مقدمة ممتازة للعناصر الأساسية للمجموعات اللانهائية في سياق نظرية المجموعات الساذجة في [15].


المجموعات المحدودة والمعدودة وغير القابلة للعد - نظرية المجموعات ، CSIR-NET الرياضيات علوم الرياضيات ملاحظات | EduRev

1. إدخال معادلة المجموعات والمجموعات المعدودة وغير المعدودة

نفترض أننا نعرف مجموعة Z + للأعداد الصحيحة الموجبة ، والمجموعة N = Z + U <0> من الأعداد الطبيعية. لأي n & isin Z + ، نشير بواسطة [n] المجموعة <1. ن>. نحن نعتبر أنه من الواضح أن [n] لديها n من العناصر ، وكذلك أن المجموعة الفارغة & Oslash بها 0 عنصر. فقط بدافع الدقة الرياضية ، دعنا نعرّف [0] = & Oslash (لماذا لا؟).

من الواضح تمامًا ما يعنيه أن تحتوي مجموعة S التعسفية على 0 عناصر: يجب أن تكون المجموعة الفارغة. هذا هو - وهذه خاصية غريبة إلى حد ما للمجموعة الفارغة - & Oslash كمجموعة تتميز بشكل فريد بحقيقة أنها تحتوي على عناصر 0.

ماذا يعني أن تحتوي المجموعة التعسفية S على n من العناصر؟ بحكم التعريف ، فهذا يعني أن هناك انحيازًا i: S & rarr [n] ، أي وظيفة حُقنية وسخرية أو ، على نحو مكافئ ، وظيفة توجد لها دالة عكسية i: [n] & rarr S. 2

دعونا نطلق على مجموعة محدودة إذا كانت تحتوي على n من العناصر لبعض n & isin N ، ومجموعة لانهائية إذا لم تكن محدودة.

بالتأكيد هناك بعض الحقائق الأساسية التي نشعر بضرورة إرضائها بهذه التعريفات. على سبيل المثال:

الحقيقة 1. المجموعة Z + لانهائية.

إثبات: إنه بالتأكيد غير فارغ ، لذا نود أن نبين أنه بالنسبة لـ no & isin Z + هل هناك انحياز i: [n] & rarr Z +. يبدو هذا واضحًا. لسوء الحظ ، في بعض الأحيان في الرياضيات يجب أن نكافح لإظهار أن ما هو واضح صحيح (وأحيانًا ما يبدو واضحًا ليس صحيحًا!). نحن هنا نواجه مشكلة إضافية تتمثل في عدم إضفاء البديهيات رسميًا على الأشياء ، لذلك ليس من الواضح تمامًا ما "اللعبة العادلة" التي يجب استخدامها في الإثبات. لكن ضع في اعتبارك ما يلي: هل يحتوي + Z على عنصر واحد؟ لا إطلاقا: بالنسبة لأي دالة i: [1] = <1> & rarr Z + ، أنا ليس خائفا لأنه لا يصل إلى i (1) + 1. هل يحتوي Z + على عنصرين؟ ومع ذلك ، لا: إذا لم تكن حقنة ، فإن نفس الحجة كما كانت من قبل تعمل إذا كانت i حقنة ، فإن صورتها عبارة عن مجموعة فرعية من عنصرين من Z +. نظرًا لأن Z + مرتب تمامًا (في الواقع منظم جيدًا) ، فإن أحد العنصرين في الصورة أكبر من الآخر ، ومن ثم لا يكون هذا العنصر زائد واحد في صورة خريطتنا. يمكننا إثبات ذلك لـ 3 أيضًا ، مما يجعلنا نعتقد أنه من المحتمل أن نعمل بالاستقراء على n. كيف أقوم بإعداده بشكل صحيح؟ دعونا نحاول إظهار أنه بالنسبة لجميع n و all i: [n] & rarr Z + ، يوجد N = N (i) بحيث أن i ([n]) & sub [N]. إذا تمكنا من القيام بذلك ، فبما أن [N] من الواضح أنها مجموعة فرعية مناسبة من Z + (لا تحتوي على N + 1 ، وما إلى ذلك) فسوف نكون قد أظهرنا أنه بدون وجود n يوجد تخريب [n]! Z + (وهو في الواقع أقوى مما قلناه). لكن الاستمرار في الإثبات بالاستقراء ليس واضحًا الآن ولكنه (أفضل بكثير!) سهل جدًا ، لذلك يُترك للقارئ.

  • حسنًا ، ليس حقًا: سيصبح هذا منطقيًا تمامًا.
  • أفترض معرفة عملية جيدة بالوظائف والحقن والتخمينات والانحرافات والوظائف العكسية. يؤكد هذا في نفس الوقت (1) قدرًا معينًا من التطور الرياضي ، و (2) قدرًا معينًا من الطابع غير الرسمي الرياضي.


ملاحظة: ما الذي استخدمناه حول Z + في الإثبات؟ بعض من بديهيات Peano لـ Z + ، والأهم من ذلك أنها تفي بمبدأ الحث الرياضي (POMI). نظرًا لأنه من الصعب تخيل دليل صارم على بيان غير بديهي حول Z + لا يستخدم POMI ، فهذه علامة جيدة: تسير الأمور بشكل جيد حتى الآن.

ماذا عن Z: هل هو لانهائي للغاية؟ يجب أن يكون كذلك ، لأنه يحتوي على مجموعة فرعية لا نهائية. هذا يكافئ منطقيًا الحقيقة التالية:

حقيقة 2. مجموعة فرعية من مجموعة محدودة منتهية.

إثبات: بشكل ملموس ، يكفي إظهار أنه بالنسبة لأي n & isin N ومجموعة فرعية S & sub [n] ، فبالنسبة لبعض m & isinN يوجد انحياز i: S & rarr [m]. كما هو مذكور أعلاه ، لأي قيمة محددة لـ n ، من السهل توضيح ذلك ، لذا مرة أخرى يجب علينا إدخال n. لنفعل ذلك هذه المرة: افترض العبارة n ، ودع S & sub [n + 1]. ضع S & # 39 = S & cap [n] ، لذا عن طريق الاستقراء يوجد انحراف i & # 39: [m] & rarr S & # 39 لبعض m & # 39 & isin N.
بالتضمين S & # 39 & sub ، نحصل على حقنة i: [m] & rarr S. إذا لم يكن n + 1 عنصرًا في S ، فإن S & # 39 = S و i هو انحراف. إذا كانت n + 1 & isin S ، فإن تمديد i & # 39 إلى خريطة من [m + 1] إلى S عن طريق إرسال m + 1 إلى n + 1 يعطي انحرافًا. تم.

مرة أخرى ، يظهر هذا من خلال التناقض أن العديد من مجموعات الأرقام الأكثر شيوعًا لدينا - على سبيل المثال Z Q R C - لانهائية.

هناك شيء آخر يجب علينا بالتأكيد التحقق منه: تحديدًا ، قلنا أن المجموعة S تحتوي على n من العناصر إذا كان من الممكن وضعها في انحياز مع [n] لبعض n. لكننا لم نظهر أن هذا n فريد: ربما يمكن أن تحتوي المجموعة على n من العناصر وأيضًا n + 691 عنصرًا؟ بالطبع لا:

الحقيقة 3. لنفترض أن S مجموعة تحتوي على عناصر m ومجموعة T تحتوي على n من العناصر.

أ) إذا كان هناك تخمين & phi: S & rarr T ، ثم m & GT ص.

ب) إذا كان هناك حقنة & phi: S & rarr T ، ثم m & lt ص.

التمرين 1: قدم دليلاً على الحقيقة 4 وهو دليل صارم بما يكفي لذوقك.

ملاحظة: على سبيل المثال ، الجزء ب) هو المبدأ الشهير & ldquoPigeonhole & quot أو & ldquoDirichlet & # 39s box & quot ، وعادة ما يعتبر واضحًا. بالطبع ، إذا لعبنا لعبة الرياضيات الرسمية ، فعندئذ & quot؛ واضح & quot؛ يعني & quot؛ المتابعة من بديهياتنا بطريقة فورية للغاية بحيث لا تستحق الذكر ، & quot؛ والحقيقة 3 ليست واضحة بهذا المعنى. (ولكن يمكن للمرء أن يقدم دليلاً يتماشى مع البراهين الاستقرائية أعلاه ، فقط لفترة أطول قليلاً).

التمرين 2: أظهر أنه بالنسبة للمجموعتين S و T ، فإن العناصر التالية متكافئة:

أ) يوجد عارض S & rarr T.

ب) يوجد حقنة T & rarr S.

دعونا نضغط على دراسة خصائص المجموعات اللانهائية.

التعريف الأساسي (كانتور): نقول أن S و T مكافئين ، ونكتب S & # 8780 T إذا كان هناك انحياز i: S & rarr T.

ومع ذلك ، لدينا أسبابنا لاختيار استخدام & ldquo equivalent. & quot ، يشير المصطلح & ldquoequinumerous ، & quot على سبيل المثال ، إلى أن المجموعتين لهما نفس عدد العناصر ، أو بعبارة أخرى ، هناك بعض الثوابت العددية التي نربطها بمجموعة واحدة مع خاصية أنه يمكن وضع مجموعتين في انحياز بالضبط عندما يكون لكل منهما نفس قيمة هذا الثابت العددي. لكننا نرغب في رؤية الأشياء بالطريقة المعاكسة تمامًا. دعونا نتوسع قليلاً في هذه النقطة.

كانت فكرة كانتور هي أننا يجب أن نعتبر مجموعتين & ldquo لهما نفس الحجم & quot إذا كانتا متساويتين ، أي إذا كان من الممكن إقران عناصرهما عبر مراسلة واحد لواحد. بالتأكيد هذا يتوافق مع تجربتنا من مجموعات محدودة.

ومع ذلك ، هناك تطور رائع ودقيق: بالعامية ، يفكر المرء في حساب أو قياس شيء ما كعملية تأخذ كمدخل مجموعة واحدة من الكائنات ومخرجات a number. لذلك يجب أن يكون لدينا أسماء لجميع الأرقام & quot التي تقيس أحجام الأشياء: إذا أردت ، فنحن بحاجة إلى حساب ارتفاع عشوائي. لم تضع كل حضارة مثل هذا النظام العام للعد: لقد سمعت أنه في بعض قبيلة بدائية & quot ؛ لديهم فقط كلمات للأرقام حتى 4 وأي شيء فوق هذا يشار إليه فقط بـ كثير. & quot في الواقع ليس لدينا أسماء مناسبة لأعداد كبيرة بشكل تعسفي في اللغة الإنجليزية (باستثناء اللجوء إلى التكرار ، على سبيل المثال ، مليون مليون مقابل تريليون).

لكن لاحظ أنه لا يتعين علينا امتلاك مثل هذه المعرفة التفصيلية مثل الأرقام & quot ؛ لنقول ما إذا كان شيئين لهما نفس الحجم أم لا. على سبيل المثال ، قد يفترض المرء أن الرعي يسبق التطور اللفظي ، لذلك يحتاج الراعي اللغوي الأولي إلى بعض الوسائل الأخرى للتأكد من أنه عندما يأخذ أغنامه إلى الخارج للرعي في الريف ، فإنه يعود مع العديد ممن بدأ معهم. يمكن للراعي القيام بذلك على النحو التالي: في أول يوم له في العمل ، مع دخول الخراف ، جهز نوعًا من الأكياس ووضع الحجارة في الكيس ، واحد لكل شاة. ثم في المستقبل يحسب خرافه ، ليس بالمعنى المطلق ، ولكن فيما يتعلق بهذه الحجارة. إذا نفد من الغنم في يوم من الأيام قبل الحجارة ، فهو يعلم أنه ينقصه بعض الأغنام (على الأقل إذا كان لديه عدد قليل من الخراف!).

حتى اليوم ، هناك بعض المواقف التي نختبر فيها التكافؤ بدلاً من العد بالمعنى المطلق. على سبيل المثال ، إذا أتيت إلى قاعة وكان الجميع جالسًا في مقعد (فريد!) ، فأنت تعلم أن هناك على الأقل عددًا من المقاعد مثل عدد الأشخاص في الغرفة دون احتساب كلا الكميتين.

3. أو بالأحرى ، قال شيئًا باللغة الألمانية يُترجم إلى هذا. سيتم حذف هذه الملاحظات المتحذلق من الآن فصاعدا!

4. هذه لعبة يلعبها البعض بشكل أفضل من الآخرين ، أي: التوليد ، والتشبع ، والوحدة.


الأمر المثير للاهتمام في المجموعات اللانهائية هو أن هذه الأنواع من الحجج تتفكك: يصبح عمل الاستبعاد من مجموعة لا نهائية أكثر تعقيدًا مما هو عليه في الحالة المحدودة ، حيث ، بالنظر إلى مجموعة S من n من العناصر وأي عنصر x & isin S ، ثم يحتوي S x على n - 1 من العناصر. (هذا شيء يمكنك تأسيسه من خلال إنشاء انحياز وهو خطوة وسيطة جيدة نحو الحقيقة 4.) من ناحية أخرى ، Z + و N متكافئان ، نظرًا لأن الخريطة n & rarr n - 1 تعطي انحرافًا بينهما. وبالمثل ، فإن Z + تكافئ مجموعة الأعداد الصحيحة الزوجية (n & rarr 2n). في الواقع ، سرعان ما نرى أن المزيد هو الصحيح:

حقيقة 4. لأي مجموعة فرعية لانهائية S & sub Z + ، S و Z + متكافئة.

الدليل: باستخدام حقيقة أن Z + مرتبة جيدًا ، يمكننا تحديد دالة من S إلى Z + عن طريق تعيين أقل عنصر s1 من S إلى 1 ، أقل عنصر s2 من S <>1> إلى 2 ، وهكذا. إذا انتهت هذه العملية بعد خطوات n ، فإن S تحتوي على n من العناصر ، لذلك يكون التناقض محدودًا. وهكذا يستمر إلى الأبد ويعطي بوضوح انحيازًا.

من الطبيعي الآن أن نتساءل ما هي المجموعات اللانهائية المألوفة الأخرى التي تعادل Z + (أو N). لهذا ، دع & # 39 s استدعاء مجموعة مكافئة للعد Z +. 5 يعطي اختلاف طفيف في الحجة أعلاه

حقيقة 5. كل مجموعة لانهائية لها مجموعة فرعية معدودة.

(في الواقع ، بالنسبة إلى S اللانهائي ، استمر في اختيار العناصر لتحديد الانحراف من Z + إلى مجموعة فرعية من S يمكننا & # 39t نفاد العناصر لأن S لانهائي!) كمثال أول:

حقيقة 6. المجموعتان Z و Z + متكافئتان.

نحدد الانحراف الصريح Z & rarr Z + على النحو التالي: نقوم بتعيين 0 & rarr 1 ، ثم 1 & rarr 2 ، & rarr1 & rarr 3 ، 2 & rarr 4 ، -2 & rarr 5 وما إلى ذلك. (إذا كنت من النوع الذي يعتقد أن وجود صيغة تجعل شيئًا أكثر صرامة ، فإننا نضع & macrne للإيجابية n ، n! 2n والسالب n ، n & rarr 2 | n | + 1.)

الطريقة تثبت شيئًا أكثر عمومية ، a & quotinging & quot النتيجة.

حقيقة 7. افترض أن S.1 و S.2 مجموعتان معدودتان. ثم س1 & كوب S.2 معدود.

في الواقع ، يمكننا عمل بناء تضفير أكثر عمومية:

حقيقة 8. دع <>أنا> أنا & isinI أن تكون عائلة مفهرسة من المجموعات غير الفارغة المنفصلة الزوجية تفترض أن أنا وكل S.أنا قابل للعد على الأكثر (أي معدود أو محدود). ثم S: = Uأنا & isinI سي
يمكن عدها على الأكثر. علاوة على ذلك ، فإن S محدودة إذا كنت أنا و S.أنا محدودة.

نحن نرسم البناء: منذ كل Sأنا قابل للعد على الأكثر ، يمكننا ترتيب العناصر كـ sij حيث إما 1 & lt ي & lt & infin أو 1 & lt ي & lt ني . إذا كان كل شيء في الأفق محدودًا ، فمن الواضح أن S ستكون محدودة (اتحاد محدود من المجموعات المحدودة هو محدود). بخلاف ذلك ، نحدد الانحراف من Z + إلى S على النحو التالي: 1 & rarr s11 & rarr 2 & rarr s12 & rarr 3 & rarr s22 & rarr 4 & rarr s13 & rarr 5 & rarr s23 & rarr6 & rarr s33 ، وما إلى ذلك. هنا نحتاج إلى الاتفاقية التي عندما يكون sij غير موجود ، نحذف هذا المصطلح وننتقل إلى العنصر التالي في المجال المشترك.

ربما يكون المعيار الأكثر هو أن نقول اللانهائية والاحتياطية & ldquocountable & quot ؛ بمعنى غير محدود أو محدود. نقترح هنا تبسيط المصطلحات.

يتم استخدام الحقيقة 8 في كثير من الأحيان في الرياضيات. كتطبيق فوري:

الحقيقة 9. مجموعة الأعداد المنطقية Q قابلة للعد.

إثبات: يمكن كتابة كل رقم منطقي وألفا بشكل فريد + a / b ، حيث a ، b & isin Z +. نحدد ارتفاع h (& alpha) & alpha ليكون max ab وأيضًا h (0) = 0. من الواضح أنه بالنسبة لأي ارتفاع n & gt 0 ، يوجد على الأكثر 2n 2 رقمان منطقيان للارتفاع n ، وأيضًا ذلك لـ كل n & isin Z + هناك رقم منطقي واحد على الأقل للارتفاع n ، وهو العدد الصحيح n = n / 1. لذلك ، أخذ I = N ووضع بعض الترتيب التعسفي على مجموعة محدودة من الأعداد المنطقية للارتفاع n ، تعطينا الحقيقة 9 انحياز Z + & rarr Q.

بطريقة مماثلة ، يمكن للمرء أن يثبت أن المجموعة من الأعداد الجبرية قابلة للعد.

الحقيقة 10. إذا كان A و B قابلين للعد ، فإن المنتج الديكارتي A x B قابل للعد.

التمرين 3: إثبات الحقيقة رقم 10. (الإستراتيجية 1: اختصر حالة Z + x Z + واستخدم المسار القطري من إثبات الحقيقة 8. الإستراتيجية 2: لاحظ أن A x B & # 8780 Uأ & إسينا (ب) وطبِّق حقيقة 8 مباشرةً.)

توقف باك مع R. Let & # 39s أولاً لإثبات نظرية كانتور التالية ، والتي يمكن القول إنها النتيجة الوحيدة الأكثر أهمية في نظرية المجموعات. تذكر أنه بالنسبة لمجموعة S ، فإن مجموعة قوتها 2 S هي مجموعة من جميع مجموعات S الفرعية.

نظرية 11. (النظرية الأساسية الأولى لنظرية المجموعات)

لا يوجد اعتراض من مجموعة S لمجموعة قوتها 2 S.

ملاحظة: عندما تكون S محدودة ، فهذا يعني فقط أنه بالنسبة لجميع n & isin N ، 2 n & gt n ، وإن كان ذلك صحيحًا ، إلا أنه ليس مثيرًا بشكل رهيب. من ناحية أخرى ، فإن أخذ نظرية S = Z + Cantor & # 39s يوفر لنا مجموعة غير معدودة 2 Z +. في الحقيقة يخبرنا أكثر من ذلك بكثير ، كما سنرى بعد قليل.

إثبات نظرية كانتور: افترض أن f: S & rarr2 S هي أي وظيفة. سننتج عنصر 2 S ليس في صورة f.
على وجه التحديد ، دع T هو مجموعة كل x & isin S بحيث لا يكون x عنصرًا في f (x) ، لذلك T هو عنصر من 2 S. هل يمكن أن يكون f (s) لبعض s & isin S؟ حسنًا ، افترض أن T = f (s) لبعض s & isin S. نسأل السؤال البريء ، & quotIs & isin T؟ & quot افترض أولاً أنه: s & isin T بتعريف T وهذا يعني أن s ليست عنصرًا من f (s). لكن f (s) = T ، وبعبارة أخرى ، فإن s ليست عنصرًا من عناصر T ، وهو تناقض. حسنًا ، ماذا لو لم تكن s في T؟ ثم s & isin f (s) ، ولكن مرة أخرى ، نظرًا لأن f (s) = T ، نستنتج أن s في T. وبعبارة أخرى ، تمكنا من تحديد مجموعة فرعية T من S لها فكرة أن T في صورة f متناقضة منطقيًا. لذا فإن f ليست طائشة!

ما علاقة هذا بـ R؟ دعونا نحاول إظهار أن الفترة (0 1] غير قابلة للعد. من خلال الحقيقة 5 ، يشير هذا إلى أن R غير قابلة للعد. الآن باستخدام التوسعات الثنائية ، يمكننا تحديد (0 1] مع مجموعة القوة لـ Z +. حسنًا ، تقريبًا: هناك هو الغموض المعياري المزعج قليلاً في التوسع الثنائي ،

هناك طرق مختلفة حول هذا: على سبيل المثال ، لنفترض أننا نتفق على تمثيل كل عنصر من (0 1] بواسطة عنصر لا ينتهي بسلسلة لا نهائية من الأصفار. وهكذا حددنا (0 1] مع مجموعة فرعية معينة T من مجموعة القوة لـ Z + ، مجموعة المجموعات الفرعية اللانهائية من Z +. لكن مجموعة المجموعات الفرعية المحدودة لـ Z + قابلة للعد (الحقيقة 8 مرة أخرى) ، وبما أن اتحاد مجموعتين معدودتين سيكون قابلاً للعد (ومرة أخرى!) ، يجب أن يكون أن T غير معدود ، ومن ثم فهو كذلك (0 1] وكذلك R.

هناك العديد من الأدلة الأخرى على عدم إمكانية عد R. على سبيل المثال ، يمكننا التفكير في وظيفة f: Z + & rarr R ، وتقليدًا لإثبات نظرية Cantor & # 39s ، نظهر أنه لا يمكن أن يكون مفاجئًا من خلال إيجاد عنصر صريح لـ R لا في صورتها. يمكننا كتابة كل رقم حقيقي f (n) في توسيعه العشري ، ثم بناء رقم حقيقي & alpha & isin [0 1] الذي هو رقمه العشري التاسع وألفاص يختلف عن الرقم العشري التاسع لـ f (n). مرة أخرى ، يجب معالجة الغموض في التمثيلات العشرية بطريقة ما: هنا يمكننا الابتعاد عن 9 & # 39s و 0 & # 39s. التفاصيل متروكة للقارئ.

يأتي الدليل الأكثر جاذبية ، وإن كان أكثر تقدمًا ، من حالة خاصة من نظرية فئة Baire: في أي مساحة مترية كاملة ، يظل تقاطع عدد لا يحصى من المجموعات الفرعية الكثيفة المفتوحة كثيفًا (على الرغم من أنه ليس بالضرورة مفتوحًا بالطبع). الازدواجية (على سبيل المثال ، أخذ المكملات) ، نحصل على ذلك في أي مساحة مترية كاملة ، فإن اتحاد عدد لا يحصى من المجموعات الفرعية المغلقة مع الداخلية الفارغة له أيضًا مساحة داخلية فارغة. هكذا:

نتيجة طبيعية 13. مساحة مترية كاملة بدون نقاط معزولة غير معدودة.

إثبات: قم بتطبيق الصيغة المزدوجة لنظرية Baire & # 39s على المجموعات الفرعية المكونة من نقطة واحدة في الفضاء.

وبالتالي ، نظرًا لأن R بحكم تعريفها هي إكمال Q فيما يتعلق بالمقياس الإقليدي القياسي ، وليس لها نقاط معزولة ، يجب أن تكون R غير قابلة للعد. بالنسبة لهذه المسألة ، حتى Q ليس له نقاط معزولة (وهو أقوى تمامًا: لا يمكن عزل أي عنصر من عناصر إكمال الفضاء المتري مطروحًا منه المساحة نفسها ، لأن هذا سيتعارض مع كثافة الفضاء في اكتماله) ، لذلك بما أننا نعلم أنه قابل للعد ، نستنتج أنه غير مكتمل دون الحاجة إلى الحديث عن & Radic2 أو أي شيء من هذا القبيل. في الواقع ، تنطبق نفس الحجة على Q الممنوحة بمقياس p-adic: لا توجد نقاط معزولة ، لذلك Qص غير معدود ولا يساوي Q.

ما ورد أعلاه كان مجرد مثال واحد على أهمية التمييز بين المجموعات المعدودة وغير المعدودة. اذكر بإيجاز بعض الأمثلة الأخرى:

المثال 2: نظرية القياس. المقياس هو دالة ذات قيمة [0 & infin] محددة في عائلة معينة من مجموعات فرعية من مجموعة معينة ، يجب أن تكون مضافة بشكل معدود ولكن ليس مضافة بشكل غير معدود. على سبيل المثال ، هذا يعطينا فكرة طبيعية عن الحجم على دائرة الوحدة ، بحيث تكون المساحة الإجمالية & pi ومساحة أي نقطة مفردة هي 0.
يمكن أن يكون للكامل قياس أكبر من مجموع مقاييس الأجزاء إذا كان هناك عدد لا يحصى من الأجزاء!

المثال 3: بالنظر إلى متشعب قابل للتفاضل M للبعد n ، فإن أي عديدات طيات فرعية من البعد n- 1 لها ، بمعنى محدد جيدًا ومستقل عن أي مقياس معين على M ، قياس الصفر. على وجه الخصوص ، يحصل المرء من هذا على أن عائلة معدودة من عديدات الطيات الجزئية ذات البعد على الأكثر n - 1 لا يمكنها & الاقتباس من مشعب ذو أبعاد n. في الهندسة الجبرية المعقدة ، تحدث مثل هذه الطبقات بشكل طبيعي ، ويمكن للمرء أن يشير إلى & quot؛ نقطة عامة & quot في مجموعة متنوعة كنقطة تقع على تكملة عائلة معدودة (معطاة) من التفرعات منخفضة الأبعاد ، وتكون واثقًا من وجود مثل هذه النقاط !

المثال 4: نظرية النموذج هي فرع من فروع الرياضيات تميل إلى استغلال التمييز بين المعدود وغير المعدود بطرق مخادعة إلى حد ما. على وجه التحديد ، هناك نظرية Lowenheim-Skolem ، التي تنص على وجه الخصوص على أن أي نظرية (مع لغة معدودة) تعترف بنموذج لا نهائي يقبل نموذجًا قابلًا للعد. علاوة على ذلك ، بالنظر إلى أي نموذج غير معدود للنظرية ، هناك نموذج فرعي قابل للعد يتقاسم جميع خصائص & quotfirst Order & quot ، وعلى العكس من ذلك ، فإن الانقسام القابل للعد / غير المعدود هو طريقة جيدة للحصول على حدس حول الفرق بين الترتيب الأول والترتيب الثاني الخصائص.

2. بعض النتائج الأساسية الأخرى

Dedekind & # 39s توصيف مجموعات لانهائية.

الحقيقة 14. المجموعة S لا نهائية إذا كانت معادلة لمجموعة فرعية مناسبة من نفسها.

إثبات: اتجاه واحد يعبر عن حقيقة واضحة حول المجموعات المحدودة. على العكس من ذلك ، دع S مجموعة لا نهائية كما هو مذكور أعلاه ، هناك مجموعة فرعية قابلة للعد T & S. اختر بعض الانحراف i بين T و N ثم هناك انحياز i & # 39 بين T & # 39: = T i -1 (0) و T (لمجرد وجود انحراف بين N و Z +. لذلك نحصل على الانحراف بين S & # 39: = S i -1 (0 و S من خلال تطبيق i & # 39 من T & # 39 إلى T والهوية على S T.

هذا التوصيف للمجموعات اللانهائية يرجع إلى Dedekind. الأمر المثير للسخرية هو أنه بطريقة ما أنظف وأكثر جوهرية من توصيفنا للمجموعات المحدودة ، حيث كان علينا المقارنة مع عائلة مميزة من المجموعات <[n] | n & isin N>.
وبالتالي ربما يجب علينا تحديد مجموعة ما لتكون محدودة إذا لم يكن من الممكن وضعها في حالة انحراف بمجموعة فرعية مناسبة من نفسها! (من ناحية أخرى ، هذه ليست خاصية & quotfirst order & quot ، لذا فهي ليست في الواقع ملائمة للعمل معها.)

مجموعة غير معدودة ليست من النوع المتصل. لاحظ أنه عند جعل التعريف & quot قابلًا للعدالة ، & quot ، أي مجموعة لا نهائية لا تعادل Z + ، فقد فعلنا بشكل أساسي ما سخرنا منه سابقًا & quot القبائل البدائية & quot من أجل القيام به: التخلي عن التمييز بين المجموعات الكبيرة جدًا. بمعنى ما ، تبدأ نظرية المجموعات عندما نحاول تصنيف المجموعات غير المعدودة إلى التكافؤ. اتضح أن هذا مشروع طموح تمامًا - سنقدم النتائج الأساسية لهذا المشروع في الدفعة التالية - ولكن هناك بعض الحقائق الإضافية التي يجب على المرء أن يأخذها في الاعتبار طوال الحياة الرياضية.

دعونا نحدد مجموعة S لتكون من النوع المتصل (أو باختصار ، سلسلة متصلة) إذا كان هناك انحياز i: S & rarr R. يستحق المرء أن يعرف ما يلي:

حقيقة 15. توجد مجموعة غير معدودة ليست من النوع المتصل ، وهي 2 R.

دليل - إثبات: من خلال النظرية 11 ، لا يوجد أي اعتراض من R إلى 2 R ، لذا فإن 2 R بالتأكيد ليست من النوع المتصل. ومع ذلك ، يجب أن نؤكد ما يبدو معقولًا بشكل حدسي: أن 2 R هي بالفعل غير قابلة للعد. إنه بالتأكيد لانهائي ، لأنه عن طريق الحقن الطبيعي أنا: R & rarr 2R، r & rarr ، فهو يحتوي على مجموعة فرعية لا نهائية. ولكن في الواقع ، يوضح هذا أيضًا أن 2 R غير قابلة للعد ، لأنه إذا كانت قابلة للعد ، فإن مجموعتها الفرعية i (R) & # 8780 R ستكون قابلة للعد ، وهي ليست & # 39t.

بعض المجموعات من النوع المتصل. لأي مجموعتين S و T ، نحدد T S كمجموعة من جميع الوظائف f: S & rarr T. عندما تكون T = [2] ، يتم تحديد مجموعة جميع الوظائف f: S & rarr [2] بشكل طبيعي مع مجموعة الطاقة 2 S من S (لذا فإن الترميز متسق تقريبًا: من أجل الاتساق الكامل ، يجب أن نشير إلى مجموعة الطاقة لـ S بحلول [2] S ، وهو ما لن نتعب أنفسنا للقيام به).

حقيقة 16. المجموعات (0 1] و 2 Z + و R Z + من النوع المتصل.

دليل - إثبات: حددنا في وقت سابق فترة الوحدة (0 1] في R مع المجموعات الفرعية اللانهائية من Z + ولاحظنا أنه نظرًا لأن المجموعات الفرعية المحدودة لـ Z + تشكل مجموعة قابلة للعد ، فهذا يعني أن (0 1] وبالتالي فإن R نفسها غير قابلة للعد. صقل هذه الملاحظة الأخيرة قليلاً:

ليما 17. لنفترض أن S مجموعة غير معدودة و C & S مجموعة فرعية قابلة للعد على الأكثر.
ثم S C & # 8780 S.

دليل - إثبات: افترض أولاً أن C محدودة ، على سبيل المثال C & # 8780 [n]. ثم يوجد حقنة i: Z + & rarr S بحيث أن i ([n]) = C (على النحو التالي مباشرة من الحقيقة 6). دع ج& ما لا نهاية = أنا (Z +). الآن يمكننا تحديد انحياز صريح وبيتا من S C إلى S: أي أننا نأخذ & beta لتكون الهوية على تكملة C& ما لا نهاية وعلى ج& ما لا نهاية نحدد & beta (i (k)) = i (k - n).

افترض الآن أن C قابلة للعد. نحن نفعل شيئًا مشابهًا. وهي أخذ C1 = C ، منذ S C.1 غير معدود ، يمكننا العثور على مجموعة فرعية لا حصر لها C2 & س ج1 . بهذه الطريقة يمكننا إيجاد عائلة <>أنا>i & isinZ + من المجموعات الفرعية القابلة للعد والفصل الزوجي من S. ، دعونا نحدد كل مجموعة من هذه المجموعات الفرعية باستخدام Z + ، والحصول على مجموعة فرعية قابلة للعد مفهرسة بشكل مضاعف& ما لا نهاية : = يوأناجأنا = <>ij> - هنا جij هو العنصر jth لـ Cأنا . الآن نحدد bijection & beta من S C1 إلى S عن طريق أخذ & beta لتكون هوية مكملة لـ C& ما لا نهاية وعن طريق وضع & بيتا (cij) = ج(i-1) ي . هذا يكمل برهان اللمة.

وبالتالي ، فإن مجموعة المجموعات الفرعية اللانهائية من Z + - كونها مجموعة فرعية من 2 Z + مع تكملة معدودة - تعادل 2 Z + ، وبالتالي (0 1] & # 8780 2 Z +. لذلك دعونا نرى أن (0 1] هي سلسلة متصلة النوع. إحدى الطرق هي كما يلي: مرة أخرى بواسطة lemma أعلاه ، [0 1] & # 8780 (0 1) ، و R حتى متماثل مع (0 1): على سبيل المثال ، الوظيفة

بالنسبة لحالة (Z +) R: منذ R & # 8780 2 Z + ، يكفي إيجاد انحراف من (Z +) 2 Z + إلى 2 Z +. هذا في الواقع سهل للغاية: لقد حصلنا على تسلسل أij من المتواليات الثنائية وتريد عمل تسلسل ثنائي واحد. ولكن يمكننا القيام بذلك فقط عن طريق اختيار bijection Z + x Z + & rarr Z +.

المزيد من التجريد سيجعل هذه الحجة تبدو أكثر منطقية:

ليما 18. افترض أن أ ، ب ، ج هي مجموعات. ثم هناك انحراف طبيعي

دليل على اللمة: في الواقع ، بالنظر إلى الوظيفة F من C إلى AB والزوج المرتب (c ، b) & isin C x B ، F (c) هي دالة من B إلى A ، وبالتالي فإن F (c) (b) هي عنصر من .

على العكس من ذلك ، يمكن النظر إلى كل وظيفة من C x B إلى A كدالة من C إلى المجموعة A B من الوظائف من B إلى A ، ومن الواضح أن هذه التطابقات معكوسة بشكل متبادل. 8 إذن ما قلناه أعلاه يصل إلى حد

التمرين 4: الفاصل الزمني الفرعي لـ R الذي يحتوي على أكثر من نقطة هو من النوع المتصل.

كما أن الحالة (Z +) Z + من النوع المتصل. At the moment I do not see a proof of this within the framework we have developed. What we can show is that there exists an injection R ,&rarr (Z + ) Z+ < indeed, since R ≌ 2 Z+ , this is obvious < and also that there exists an injection (Z + ) Z+ ,&rarr 2 Z+ ≌ R.

But this can be remedied in many ways. One obvious way is to retreat from binary notation to unary notation: we encode aأنا as a string of i ones, and in between each string of ai ones we put a zero to separate them. This clearly works (it seems almost cruelly ine±cient from the perspective of information theory, but no matter).

Roughly speaking, we have shown that (Z + ) Z+ is "at least of continuum type" and at most of continuum type," so if equivalences of sets do measure some reasonable notion of their size, we ought to be able to conclude from this that (Z + ) Z+ is itself of continuum type. This is true, a special case of the important SchrÄoderBernstein theorem whose proof we defer until the next installment.

Lots of inequivalent uncountable sets. From the fundamental Theorem 12 we first deduced that not all infinite sets are equivalent to each other, because the set 2 Z+ is not equivalent to the countable infinite set Z + . We also saw that 2 Z+ ≌ R so called it a set of continuum type. Then we noticed that Cantor's theorem implies that there are sets not of continuum type, namely 2 R ≌ 2 2Z+ . By now one of the most startling mathematical discoveries of all time must have occurred to the reader: we can keep going!

To simplify things, let us use (and even slightly abuse) an obscure but colorful notation due to Cantor: instead of writing Z + we shall write Z0 . For 2 Z+ we shall write Z1 , and in general, for n &isin N, having defined in (informally, as the n-fold iterated power set of Z + ), we will define Zn+1 as 2 Zn . Now hold on to your hat:

Fact 19. The infinite sets fin <>n>n&isinN are pairwise inequivalent.

Proof: Let us first make the preliminary observation that for any nonempty set S , there is a surjection 2 S &rarr S . Indeed, pick your favorite element of S , say x for every s &isin S we map fsg to s, which is "already" a surjection we extend the mapping to all of 2 S by mapping every other subset to x.

8. This is canonical bijection is sometimes called "adjunction."


Now we argue by contradiction: suppose that for some n > m there exists even a surjection s : Zm &rarr Zn. We may write n = m + k. By the above, by concatenating (finitely many) surjections we get a surjection &beta : Zm+k &rarr Zm+1 . But then &beta º s : Zm &rarr Zm+1 = 2 Zm is a surjection, contradicting Cantor's theorem.

Thus there are rather a lot of inequivalent in¯nite sets. Is it possible that the Zn 's are all the infinite sets? In fact it is not : define Zw := Un&isinN Zn. This last set Zw is certainly not equivalent to Zn for any n, because it visibly surjects onto Zn+1 . Are we done yet? No, we can keep going, defining Zw+1 := 2 Zw .

To sum up (!!), we have a two-step process for generating a mind-boggling array of equivalence classes of sets. The first step is to pass from a set to its power set, and the second stage is to take the union over the set of all equivalence classes of sets we have thus far considered. Inductively, it seems that each of these processes generates a set which is not surjected onto by any of the sets we have thus far considered, so it gives a new equivalence class. Does the process ever end.

Well, the above sentence is an example of the paucity of the English language to describe the current state of affairs, since even the sequence Z0 Z1 Z2 . does not end in the conventional sense of the term. Better is to ask whether or not we can reckon the equivalence classes of sets even in terms of infinite sets. At least we have only seen countably many equivalence classes of sets thus far: is it possible that the collection of all equivalence classes of sets is countable?

No again, and in fact that's easy to see. Suppose <>أنا> i&isinN is any countable collection of pairwise inequivalent sets. Then - playing both of our cards at once! - one checks immediately that there is no surjection from any Sأنا onto . In fact it's even stranger than this:

Fact 20. For no set I does there exists a family of sets <>أنا>i&isinI such that every set S is equivalent to Sأنا for at least one i.

دليل - إثبات: Again, take . There is no surjection from U i&isinI Sأنا onto Sbigger , so for sure there is no surjection from any Sأنا onto Sbigger .

3. Some Final Remarks

Fact 20 is a truly amazing result. Once you notice that it follows readily from Cantor's Theorem 12, you may believe, as I do, that this theorem is the single most amazing result in all of mathematics.

There is also the question of whether this result is disturbing, or paradoxical. Can we then not speak of the set of all equivalence classes of sets (let alone, the set of all sets)? Evidently we cannot. There are too many sets to wrap all of them up into a single set. Some people have referred to this as Cantor's Paradox, although I do not favor this terminology: as far as I am aware, Cantor did not regard his results as paradoxical, nor do I. It does destroy the ultranaive" notion of a set, namely, that given any "property" P , there is a set SP = [x | P (x)>: according to Cantor's result, we cannot take P to be the property x = x. This was surprising in the late 19th century. But now we know of such things as Russell's paradox, which shows that the property P (x) given by x ¬in x does not give rise to a set: the set of all sets which are not members of itself is a logical contradiction.


1.4: Countable and Uncountable Sets

The nonnegative integers are countable, as shown by the bijection f(n) = n+1. Some people prefer this definition. It is sometimes more natural to begin counting at 0, rather than 1. I guess it depends on whether you program in C or fortran.

The even numbers are countable map n to n/2. Thus an infinite set can be just as large as a proper subset of itself.

The integers are countable. Map n to 2n for n ≥ 0, and map n to 1-2n for n < 0.

Any set that can be listed in order, or enumerated, is countable. For instance, any subset of the positive integers is countable. Take the smallest number in the set and place it first on the list. Take the next smallest and place it second on the list. Continue this process until the entire set has been "counted", i.e. mapped onto the positive integers. Thus the prime numbers are countable, and so on.

Ordered pairs of positive integers are countable. List them this way:

1/1 2/1 1/2 3/1 2/2 1/3 4/1 3/2 2/3 1/4 5/1 4/2 3/3 2/4 1/5 …

Since fractions are ordered pairs of integers, the rational numbers are countable. This is counterintuitive, since they are densely packed in the number line. There are infinitely many rationals packed into the tiniest of intervals, yet there are just as many rationals as integers.

We showed that the cross product (i.e. ordered pairs) of countable sets is countable. Use this fact again and again to show that the n-tuples of integers are countable. The integer points, or even the rational points in n space are countable.

In fact all finite ordered tuples of the integers, or any other countable set for that matter, are countable. Here is a recipe for listing all possible tuples in order. We know that the tuples of size n can be listed in order this was described above. So start with the first tuple of size 1, then the first tuple of size 2 followed by the second tuple of size 1, then the first tuple of size 3 and the second tuple of size 2 and the third tuple of size 1, then the first tuple of size 4 and the second tuple of size 3 and the third tuple of size 2 and the fourth tuple of size 1, and so on.

As a corollary, the finite sets of integers are countable, as these are all represented, perhaps many times, by various ordered tuples. The set (1,2,3) appears six times when order is significant. Since the ordered tuples over count the unordered subsets, and the tuples are countable, the finite subsets are also countable.

Note that the integer polynomials are precisely the finite ordered tuples of integers. Wel almost the tuples that have leading zeros can be thrown away. Anyways, since the tuples are countable, the polynomials are countable. Of course the coefficients can be drawn from any countable set, so the polynomials over the rationals are countable.

The polynomials over x and y are the polynomials in y, whose coefficients are polynomials in x. We just showed the polynomials in x are countable, and since these act as coefficients, the polynomials in x and y are countable. This extends to polynomials in x y z, and so on.

Diagonalization

Combinations that are not Sets

Yes I know, all ordinals are sets, and there are uncountably many ordinals. This is a contradiction that I don't understand. If you can explain it to me, please drop me a line.


Finite cardinality

Definition: If (X) is a set and (n in ℕ) , the expression "|X| = n" means (|X| = <1,2,dots,n>) .

This matches the usual notion of the number of things in the set.

Claim: If (|A| = a) and (|B| = b) , and if (A) and (B) are disjoint, then (|A cup B| = a + b) .

ملحوظة: This can be shortened to " (|A cup B| = |A| + |B|) , as long as you keep in mind that this equation only makes sense if (|A|) and (|B|) are numbers (i.e. if (A) and (B) are finite)

دليل - إثبات: Since (|A| = a) , there exists a bijection (f : A → <1,2,dots,a>) . Similarly, there exists (g : B → <1,2,dots,b>) . We can build a function (h : A cup B → <1,2,dots,a+b>) by defining [h(x) := left<egin f(x), & ext g(x), & ext end ight.]

To complete the proof, we need to show that (h) is a bijection. We left this as an exercise. While you're doing the exercise, make sure you use the fact that (A cup B = emptyset) .


Countable and Uncountable Sets

Probability models often involve infinite sample spaces, that is, infinite sets.

But not all sets are of the same kind.

Some sets are discrete and we call them countable, and some are continuous and we call them uncountable.

But what exactly is the difference between these two types of sets?

How can we define it precisely?

Well, let us start by first giving a definition of what it means to have a countable set.

A set will be called countable if its elements can be put into a 1-to-1 correspondence with the positive integers.

This means that we look at the elements of that set, and we take one element-- we call it the first element.

We take another element-- we call it the second.

Another, we call the third element, and so on.

And this way we will eventually exhaust all of the elements of the set, so that each one of those elements corresponds to a particular positive integer, namely the index that appears underneath.

More formally, what's happening is that we take elements of that set that are arranged in a sequence.

We look at the set, which is the entire range of values of that sequence, and we want that sequence to exhaust the entire set omega.

Or in other words, in simpler terms, we want to be able to arrange all of the elements of omega in a sequence.

So what are some examples of countable sets?

In a trivial sense, the positive integers themselves are countable, because we can arrange them in a sequence.

This is almost tautological, by the definition.

For a more interesting example, let's look at the set of all integers.

Can we arrange them in a sequence?

Yes, we can, and we can do it in this manner, where we alternate between positive and negative numbers.

And this way, we're going to cover all of the integers, and we have arranged them in a sequence.

How about the set of all pairs of positive integers?

Let us look at this picture.

This is the set of all pairs of positive integers, which we understand to continue indefinitely.

Can we arrange this sets in a sequence?

And we can do it by tracing a path of this kind.

So you can probably get the sense of how this path is going.

And by continuing this way, over and over, we're going to cover the entire set of all pairs of positive integers.

So we have managed to arrange them in a sequence.

So the set of all such pairs is indeed a countable set.

And the same argument can be extended to argue for the set of all triples of positive integers, or the set of all quadruples of positive integers, and so on.

This is actually not just a trivial mathematical point that we discuss for some curious reason, but it is because we will often have sample spaces that are of this kind.

And it's important to know that they're countable.

Now for a more subtle example.

Let us look at all rational numbers within the range between 0 and 1.

What do we mean by rational numbers?

We mean those numbers that can be expressed as a ratio of two integers.

It turns out that we can arrange them in a sequence, and we can do it as follows.

Let us first look at rational numbers that have a denominator term of 2.

Then, look at the rational numbers that have a denominator term of 3.

Then, look at the rational numbers, always within this range of interest, that have a denominator of 4.

And then we continue similarly-- rational numbers that have a denominator of 5, and so on.

This way, we're going to exhaust all of the rational numbers.

Actually, this number here already appeared there.

So we do not need to include this in a sequence, but that's not an issue.

Whenever we see a rational number that has already been encountered before, we just delete it.

In the end, we end up with a sequence that goes over all of the possible rational numbers.

And so we conclude that the set of all rational numbers is itself a countable set.

So what kind of set would be uncountable?

An uncountable set, by definition, is a set that is not countable.

And there are examples of uncountable sets, most prominent, continuous subsets of the real line.

Whenever we have an interval, the unit interval, or any other interval that has positive length, that interval is an uncountable set.

And the same is true if, instead of an interval, we look at the entire real line, or we look at the two-dimensional plane, or three-dimensional space, and so on.

So all the usual sets that we think of as continuous sets turn out to be uncountable.

How do we know that they are uncountable?

There is actually a brilliant argument that establishes that the unit interval is uncountable.

And then the argument is easily extended to other cases, like the reals and the plane.

We do not need to know how this argument goes, for the purposes of this course.

But just because it is so beautiful, we will actually be presenting it to you.


1.4: Countable and Uncountable Sets

While writing the paradox series, and thinking about set theory for the item on Russell’s Paradox, I decided to do some related entries, considering things that seem contradictory but aren’t. This one is on the cardinality of sets, and, in particular, about countable and uncountable sets.

[Let me start by saying that this will be a simplified explanation, making a number of unstated assumptions (such as assuming the axiom of choice, as is standard in modern set theory). If one is rigorous, this stuff can get way more complicated than I’ll ever want to get into here PhD theses, and, indeed, whole careers are often based on rigorous coverage of this. We’re not going there.]

I think we all understand that there are finite sets, and infinite ones. A finite set has. well, a finite number of elements &mdash the set of all U.S. presidents, the set of bones in the human body, the set of all films that have won “Best Picture” Academy Awards, the set of all people in the world. Or the set of all natural numbers less than or equal to 5: < 1, 2, 3, 4, 5 >.

An infinite set has an infinite number of elements. We have a vague idea what that means, but it’s harder to write that down, isn’t it? Examples are easy, though: the set of all natural numbers, for example: < 1, 2, 3, 4, 5, 6, . >, with no bound. The set of all integers &mdash positive and negative natural numbers, and zero. The set of all rational numbers &mdash the integers and all the fractions. The set of all real numbers &mdash the rationals, plus the irrational numbers, numbers such as &radic2, &radic3, and &pi.

There are other sets in the real world that we think of as infinite, but are we sure they are? The set all of grains of sand in the world the set of all stars in the universe the set of all atoms in the universe, come to that. But in mathematics, an infinite set is more precise. It doesn’t refer to something bigger than we can imagine, but really something that no number, however vastly, immensely large, can describe.

To get a less vague meaning of “infinite”, we’ll go back to the finite sets and talk about countability and cardinality. Clearly, one aspect of any finite set is that there’s a natural number (or zero, for the empty set) that tells us how many elements are in the set. For the set of all U.S. presidents, it’s 43 (soon to be 44). For the set of all natural numbers less than or equal to 5, it’s 5. For the set of all people in the world, we don’t know the number. but it’s clear to us that there is one, and it’s quite large.

We call that number the cardinal number of a set, and every finite set has a cardinal number that’s a non-negative integer. And we can define an infinite set as a set that does not have an integral cardinal number. It seems intuitive, then, that the sets of natural numbers, integers, rationals and reals are all infinite.

Going back to finite sets, we also understand that we can count the elements of any finite set. George Washington is 𔄙”, John Adams is 𔄚”, . Abraham Lincoln is 󈬀”, . Woodrow Wilson is 󈬌”, . and George Bush is 󈬛”. We hope Barack Obama will be 󈬜”. And the counting stops. Similarly, for bones, films, and people, we can assign a natural number to each element, starting at 1 and increasing by 1 for each element, and we call that “counting” (and here’s where the axiom of choice comes in).

More formally, what we’re really doing when we count is creating a one-to-one correspondence between the elements of the set and the subset of natural numbers less than or equal to the cardinal number of the set (we’ll ignore, for the presidents, the fact that Grover Cleveland appears twice think of him as having a not-so-evil twin).

But why do we have to stop? For an infinite set, T , suppose we can create a one-to-one correspondence between T and the entire set of natural numbers, unbounded. Have we not “counted” the set T , in some sense? Granted, our counting never stops &mdash it’s an infinite set, after all &mdash but if we can prove that every element of T has a natural number associated with it, we can say that we can count the elements.

Clearly, all finite sets are countable, so all uncountable sets are infinite. Let’s play with some countable sets for a bit. First, another definition: the cardinal number of the natural numbers is a thing we call (said “aleph-null”, using the Hebrew letter aleph).

The set of natural numbers is countable, of course, by definition &mdash each number maps to itself, and there’s our one-to-one correspondence. What about the set of even natural numbers? Our intuition certainly tells us that there are fewer of those &mdash half as many, because all evens are also natural numbers, but half the natural numbers are not even. How well does our intuition serve us when we look at one-to-one correspondences?

We can define the function f(n) := 2n , for all natural numbers n . It’s pretty easy to see that f defines a one-to-one correspondence between the naturals and the evens: for every natural number n there’s a well defined and unique value of 2n , and that value is even for every even number k , there’s a well defined and unique natural number n such that 2n = k . So the set of even natural numbers is countable: its cardinal number is .

It’s also not hard to show a mapping from the naturals to the whole numbers (naturals and zero): f(n) := n - 1 , giving us the counter-intuitive concept that we can add an element (zero) to the set, and not increase the cardinal number. Such is the mystique of infinite sets. In fact, we can also easily map the whole numbers (and, therefore, the natural numbers) to the integers (positive and negative), with a simple alternation:

And there’s another apparent paradox: that we can, as it seems, halve or double the number of elements in our countably infinite set, and not change the cardinal number, the “size” of the set. It’s still .

This goes along with the popular notion that when you do arithmetic on “infinity”, you don’t change anything: infinity plus one equals infinity infinity times two equals infinity. In mathematics that’s not quite right, though, and next time we’ll look more at countable sets, uncountable sets, and infinite cardinal numbers.


Countable and uncountable sets

This page is intended to serve as a reference for those who are being supervised on Monday and would like to tackle questions on Sheet 4 about countability over the weekend. A general remark: in order to understand this final part of the course it is essential to be clear about the definitions and basic results about injections, surjections and bijections.

Let me start with a few basic definitions.

1. A set X is said to have cardinality or size n if there is a bijection f:X--><1,2. n>. This does justice to our intuitive idea that it has size n if you can count its elements one after another and end up with the number n. If g is the inverse of f (and therefore a bijection from <1,2. n>to X) then you are counting g(1), then g(2), then g(3) and so on. The empty set is said to have cardinality zero.

2. A set is finite if it has cardinality n for some non-negative integer n.

3. A set is infinite if it is not finite.

Proposition

N, the set of all natural numbers, is infinite.

Proof

We must show that, for any n, there is no bijection f:N--><1,2. n>. Let us show more - that there is no surjection from <1,2. n>to N. Let g be any function from <1,2. n>to N. Then the sum g(1)+. +g(n) is bigger than g(k) for every k < n, so it does not belong to the image of g. Notice that this also proves (via left and right inverses) that there is no injection from N to <1,2. n>.

Proposition

A set X is infinite if and only if there is an injection f from N (the set of all natural numbers) to X.

Proof

This is a good example of a result that seems fairly obvious and therefore hard to prove properly. When in that situation, you should always go back to first principles - that is the definitions of finite and infinite. Then the proof becomes easy to find.

Suppose X is finite. Then there is a bijection f from X to <1,2. n>for some n. But then there cannot be an injection g from N to X, since then fg would be an injection from N to <1,2. n>, contradicting the previous proposition (or rather the stronger statement actually proved).

Conversely, suppose that X is infinite, and build an injection f:N-->X inductively as follows. Suppose you have decided on f(1),f(2). f(m) in such a way that they are all different. Then is not equal to X (or there would be a bijection between X and <1. m>which we are given that there isn't. So we can find another element of X and call it f(m+1). Continuing in this way we get our map f. [For the cognoscenti: I have used the axiom of countable choice, because I made a countably infinite number of decisions (one for each m) without saying how I did it.]

4. A set X is countable if it is finite or if there is a bijection f from X to N.

This is supposed to capture the idea that the elements of X can be arranged in a "list". (But be careful with this way of looking at it - the idea of a bijection is more precise.) If g:N-->X is a bijection, then the list would go g(1),g(2).

A few useful facts (especially for examples sheet questions).

(A) The following statements about a set X are equivalent:

(ii) There is an injection f:X-->N

(iii) There is a surjection g:N-->X

I'll prove this in lectures. Notice that (ii) and (iii) follow immediately from (i). Also, (ii) and (iii) are easily seen to be equivalent if you use the fact that a function is an injection/surjection if and only if it has a left/right inverse.

(B) A union of countably many countable sets is countable. To be more precise, if A 1 , A 2 . are countable sets, then A 1 U A 2 U A 3 U. is countable.

This is very useful for showing that sets are countable. For example, to show that the rational numbers form a countable set, let A q be the set of all rational numbers that are equal to p/q for some integer p. Since A q is the union of the three obviously countable sets <0>, <1/q,2/q,3/q. >and <-1/q,-2/q. >, it is countable. Since Q is the union of the sets A 1 ,A 2 . , Q is also countable. (In lectures I shall prove this from first principles as well.)

This is proved by Cantor's famous diagonal argument. I shan't reproduce it here but it is very easy to find on the web. This is one of many expositions.

(D) The set of all subsets of N is uncountable.

This can also be proved by a diagonal argument. Given a sequence A 1 ,A 2 . of subsets of N, define a new set A by the condition that n belongs to A if and only if n does not belong to A n . This is enough to ensure, for every n, that A does not equal A n . Therefore A was not part of the sequence.

(E) If X is uncountable and f:X-->Y is an injection, then Y is uncountable.

This simple fact is often useful for showing that sets are uncountable. To prove it, note that if Y were countable, then there would be an injection g from Y to N (by the equivalent condition (ii) above) and then gf would be an injection from X to N, contradicting the uncountability of X (again by (ii) above).


Countable nouns (also called count nouns) are nouns that can be counted (apple, orange) and can be therefore be pluralized (apples, oranges). Uncountable nouns (also known as non-count or mass nouns) are amounts of something, which we cannot count (gunpowder, rice).

Examples of countable nouns: babies, cakes, dogs, fingers, gowns, huts, ideas, lies, owls, papers, pencils, suitcases

Examples of uncountable nouns: air, ash, barley, bread, butter, dirt, flour, money, fun, gas, grass, gunpowder, ice, ink, juice, luggage, music, news, oil, pepper, rice, sand, soil, steam, sugar, vapour, water, wheat, wine

So how do we know whether a noun is countable or uncountable?

The noun is countable:

if we can use the indefinite artice a/an قبله.

if we can use the word many (not كثير), more, or most to describe it.

if we can express its quantity by using a number before it.

if it takes on singular as well as plural forms.

The noun is uncountable:

if a/an is not normally used in front of it.

  • He is eating some rice. (Not: He is eating a rice.) Rice is an uncountable noun, so some (which can be used for both countable and uncountable nouns) is used with it.

if the word كثير can be correctly used before it.

if it is not possible for us to count it. However, we can make it countable by having a quantity for it.

  • I have just bought two cartons or litres/liters of milk. (Not: I have just bought two milk.)

if it takes only a singular form.

  • some ice (Not: some ices) / some ink (Not: some inks) / some soup (Not: some soups)

Examples:

    • There are two hairs on the snooker table. (Countable noun)
      You think my hair looks nice? (Uncountable noun)
    • You can boil an egg. (Countable noun)
      I like to eat egg. (Uncountable noun as it refers to egg in general, not one or two eggs.)
    • Let's stop for a coffee on our way to the library. (Countable noun)
      She thinks she drinks too much coffee. (Uncountable noun)
    • You had أ bad خبرة on that trip.(Countable noun)
      I have no previous خبرة of this type of work. (Uncountable noun)
    • We bought أ big fish and أ roast chicken in the supermarket. (Countable noun)
      We had some fish for lunch and chicken for dinner. (Uncountable noun)
    • As the group was large, we decided not to clink glasses. (Countable noun)
      His car windows are made of bulletproof glass. (Uncountable noun)
    • I need to press my shirt with aniron before we go. (Countable noun)
      The heavy chains are made of iron. (Uncountable noun)
    • We could see the bright lights of the city from that hill. (Countable noun)
      Light emitted by a star takes light-years to reach us. (Uncountable noun)
    • I need to press my shirt with aniron before we go. (Countable noun)
      The heavy chains are made of iron. (Uncountable noun)
    • He never missed the cartoon section in the papers (newspapers) every day. (Countable noun)
      She can fold paper into shapes that look like dinosaurs. (Uncountable noun)
    • I was robbed twotimes in one week. (Countable noun)
      It was a waste of precious time to watch him speak. (Uncountable noun)
    • They consider her book أ definitive work on penguins. (Countable noun)
      We're going to have some renovation work done on the house. (Uncountable noun)

    Examples:

    Mail : letters, postcards, bills, packages, parcels, etc.

    Not : I received a mail today.

    Furniture : tables, chairs, beds, desks, cupboard

    Not :The family bought a furniture yesterday.

    Fruit : apples, oranges, bananas, mangoes and papaya

    Not : We want to buy two (tropical)fruits today, some mangoes and a papaya.

    Jewelry : rings, necklaces, earrings, bracelets, brooches


    Uncountable Noun Examples

    Anything that cannot be counted is an uncountable noun. Even though uncountable nouns are not individual objects, they are always singular and one must always use singular verbs in conjunction with uncountable nouns. The following uncountable noun examples will help you to gain even more understanding of how countable and uncountable nouns differ from one another. Notice that singular verbs are always used with uncountable nouns.

    1. There is no more water in the pond.
    2. Please help yourself to some cheese.
    3. I need to find information about Pulitzer Prize winners.
    4. You seem to have a high level of intelligence.
    5. Please take good care of your equipment.
    6. Let’s get rid of the garbage.

    Uncountable nouns can be paired with words expressing plural concept. Using these words can make your writing more specific. Here are some examples of how to format interesting sentences with uncountable nouns.

    Garbage – There are nine bags of garbage on the curb.

    Water – Try to drink at least eight glasses of water each day.

    Advice – She gave me a useful piece of advice.

    Bread – Please buy a loaf of bread.

    Furniture – A couch is a piece of furniture.

    Equipment – A backhoe is an expensive piece of equipment.

    Cheese – Please bag ten slices of cheese for me.


    Countable and Uncountable Food

    Learn useful English vocabulary words for countable and uncountable food and drink to improve your English.

    Learn more food vocabulary with American English pronunciation video lesson.

    List of Countable and Uncountable Food

    Countable Food

    • Burger
    • Sandwich
    • Hot dog
    • Cherry
    • Apple
    • Grape
    • Orange
    • Olive
    • Watermelon
    • Carrot
    • Tomato
    • Pea
    • Salad
    • Vegetable
    • Pancake
    • Sausage
    • Egg
    • Potato
    • Cookie
    • Fries
    • Candy

    Uncountable Food

    • Bread
    • Fruit
    • Juice
    • Meat
    • Rice
    • Cereal
    • لبن
    • Coffee
    • Tea
    • Flour
    • Salt
    • Soup
    • Sugar
    • Butter
    • Cheese
    • Honey
    • Water
    • Chocolate
    • Jam
    • Seafood
    • Mustard

    Pin

    Pin

    List of Countable Food with Examples

    Burger

    Do you want some ketchup with your burger?

    Sandwich

    We went for a sandwich lunch at the local bar.

    Hot dog

    He bought a hot dog and had it covered with all the fixings.

    Cherry

    Each cake had a cherry on top.

    Apple

    The apple never falls far from the tree.

    Grape

    He put a grape into his mouth and swallowed it whole.

    Orange

    He cut the orange into quarters.

    Olive

    Have you eaten a kind of fruit called olive?

    Watermelon

    The woman cut up the watermelon and shared it out among the four children.

    Carrot

    We used a carrot for the snowman’s nose.

    Tomato

    Tomato soup is my cup of tea.

    Pea

    I felt like a pea on a drum.

    Salad

    The salad was decorated with segments of orange.

    Vegetable

    Vegetable prices fluctuate according to the season.

    Pancake

    Do you want a sweet pancake or a savoury one?

    Sausage

    She sliced off a piece of sausage.

    Egg

    He poached an egg for breakfast.

    Potato

    Potato chips are served for the children.

    Cookie

    The baby chewed the cookie up and swallowed it.

    Fries

    I’d like a steak and fries with chocolate mousse to follow.


    Watch the video: مجموعة قابلة للعد وغير قابلة للعد (ديسمبر 2021).