شمارش‌پذیری مجموعه‌ها

Stephen L. Campbell, Countability of sets, Amer. Math. Monthly, 93 (June-July 1986), no. 6,480 – 481

ترجمه‌ی دکتر اکبری مجدآباد نو

در دروس مقدماتی، معمولاً شمارش‌پذیری اعداد گویا به کمک استدلال‌های مبتنی بر قطری‌سازی ثابت می‌شود. ولی روش دیگری نیز وجود دارد که شاید از نظر شهودی مناسب‌تر باشد. این ایده از من نیست؛ من نیز آن را 15 سال پیش شنیده‌ام. اما پس از آن هرگز به شخص دیگری که آن را شنیده باشد برخورد نکرده‌ام.

گوییم عدد اصلی دو مجموعه با هم برابر است هرگاه بتوان یک تناظر یک به یک بین آنها برقرار کرد. یک مجموعه شماراست هرگاه عدد اصلی آن با عدد اصلی مجموعه‌ی اعداد طبیعی برابر باشد.

قضیه: مجموعه‌ی اعداد گویا شمارش‌پذیر است.

اثبات: واضح است که اعداد صحیح را می‌توان به اعداد گویا نگاشت. حال توجه کنید که با استفاده از مبنای 11 هر عدد گویای $a/b$ را می‌توان به یک عدد صحیح نظیر کرد که در آن نماد $/$ به جای عدد 10 به کار می‌رود. برای مثال داریم: $$2/3=2(11^2)+10(11^1)+3(11^0)=355$$بدیهی است که با به کارگیری مبناهایی بزرگتر، به آسانی می‌توان شمارش‌پذیری بسیاری از مجموعه‌های دیگر را نشان داد. برای مثال، مجموعه‌ی چندجمله‌ای‌های روی اعداد گویا را می‌توان با استفاده از مبنای 16 با نمادهای $$\{0,1,2,3,4,5,6,7,8,9,/,+,-,\%,\&,x\}$$ به اعداد صحیح نگاشت که در آن $\%$ اندیس آغازی، $\&$ اندیس پایانی و $x$ متغیر مستقل است.