שלום לכולם, אני מנסה להוכיח כיצד הקבוצה \mathbb{N}^{\mathbb{N}} אינה בת מנייה בעזרת האלכסון של קנטור.
אני אף פעם לא מצליח להבין כיצד אני בונה את הפונקציה כדי להפריך שההעתקה על.
אשמח להכוונה, תודה רבה.
נניח בשלילה כי הקבוצה \mathbb{N}^{\mathbb{N}} בת מניה. לכן קיימת פונקציה h\,:\,\mathbb{N}^{\mathbb{N}}\to \mathbb{N} חד-חד-ערכית. לפיכך, ע"פ משפט קיימת פונקציה g\,:\,\mathbb{N}\to \mathbb{N}^{\mathbb{N}} על. נוכיח כי היא אינה על ונקבל סתירה. לשם כך, נראה כי קיים f\in \mathbb{N}^{\mathbb{N}} כך שלכל n\in\mathbb{N} מתקיים g(n)\neq f.
נגדיר פונקציה f\,:\,\mathbb{N}\to\mathbb{N} המוגדרת באופן הבא:
f(n)=g(n)(n)+1
ברור כי f\in \mathbb{N}^{\mathbb{N}}. כמו כן, הפונקציה f מוגדרת היטב שכן הפונקציה g היא פונקציה מוגדרת היטב ולכן מקיימת את תנאי הקיום ותנאי היחידות. נשים לב, כי לכל n\in\mathbb{N} מתקיים f(n)=g(n)(n)+1 ולכן g(n)\neq f לכל n\in\mathbb{N}.
הראנו כי לכל n\in\mathbb{N} מתקיים g(n)\neq f ולכן g אינה על, סתירה. לפיכך נובע כי \mathbb{N}^{\mathbb{N}} אינה בת מניה.