تالار گفتمان مانشت

سلام

زیرمجموعه های شمارای بازگشتی شمارش پذیر شماراست؟
کلاً تعداد زیرمجموعه های شمارای مجموعه های شمارا و ناشمارا، شمارا هستن؟!

وقتی یه مجموعه ی شمارای نامتناهی داریم تعداد کل زیر مجموعه هاش ناشماراتاست.
و وقتی یه مجموعه ی ناشمارای نامتناهی هم داریم تعداد کل زیر مجموعه هاش ناشماراتاست.

اما
از بین این زیر مجموعه ها بعضی هاشون r.e هستند بعضی هاشون r.e نیستند
و تعداد r.e ها همیشه نمی تونه از شمارا تا بیشتر باشه.
یعنی تعداد زیر مجموعه های r.e یک مجموعه ی شمارا، شماراتاست
و تعداد زیر مجموعه های r.e یک مجموعه ی ناشمارا هم شماراتاست

rec ها هم خب معلوم دیگه که تعداد همیشه کمتر از r.e هاست (چون هر rec ای r.e هم هست اما هر r.e ای rec نیست)
پس تعداد زیر مجموعه های rec یک مجموعه نهایتا شماراتاست.

تشکر
کتاب پارسه نوشته، ناشماراست!

(30 دى 1393 08:36 ب.ظ)Ametrine نوشته شده توسط: [ -> ]تشکر
کتاب پارسه نوشته، ناشماراست!

چی ناشماراست؟

(30 دى 1393 09:26 ب.ظ)fatemeh69 نوشته شده توسط: [ -> ]چی ناشماراست؟

تعداد زیرمجموعه های شمارای بازگشتی شمارش پذیر، ناشماراست.

کاملا غلطه

تعداد ماشین های تورینگ شماراتاست این یعنی تعداد زبان های r.e شماراتاست
زبان های rec زیر مجموعه ای از مجموعه ی زبان های r.e هستند یعنی تعداد زبان های rec از تعداد زبان های r.e کمتره
پس تعداد زبان های rec نیز شمارا تاست