חוצץ - הסבר במתמטיקה דיסקרטית

(לפי ההגדרה חוצץ הוא בעצם איבר בקבוצה אשר עוצמת האיברים הגדולים ממנו שווה
לעוצמת האיברים הקטנים ממנו :

במקרה של קבוצות סופיות çאותו מס' של איברים(גדולים וקטנים ממנו)

במקרה של קבוצות אינסופיות çאותו מס' קרדינלי (בן מניה, רצף ...)

א. העוצמה היא 0 (אין חוצצים).

בגלל שהקבוצה אינסופית ומוכלת ב N אז לכל איבר a ב A יש לכל היותר a איברים קטנים

ממנו ואינסוף גדולים ממנו ולכן אין התאמה חח"ע çאין חוצצים.

ב. ידוע (ראיתם בהרצאה) שכל קטע (a,b) של מספרים ממשיים בעל עוצמת הרצף.

קבוצת החוצצים במקרה זה היא הקבוצה (c,d) עצמה, כי כל a ב (c,d) מגדיר קבוצה

(c,a) של איברים הקטנים ממנו בעלת עוצמת רצף וקבוצה

(a,d) של איברים הגדולים ממנו בעלת עוצמת רצף.

ג. A סופית ולכן חוצץ משמעו חלוקה של הקבוצה לשתי קבוצות שוות גודל ולכן

אם |A| זוגית אז יש 0 חוצצים, אחרת חוצץ אחד שהוא האיבר האמצעי.

ד.

A אינסופית : אם A היתה סופית אז היה לה לכל היותר חוצץ אחד (לפי הסעיף הקודם) בסתירה לנתון שיש ל A יותר מחוצץ אחד.

טענה 1:

אם A תת קבוצה אינסופית של קבוצה בת מניה אז A בת מניה.

הוכחה:

נראה מניה (סידור) של איברי A באופן הבא : ניקח את המניה של קבוצת האם ונשמיט את

כל האיברים שלא שייכים ל A, סידור זה הוא טוב כי

1.כל איבר של A מופיע פעם אחת.(כי כל איבר כזה הופיע במניה של קב' האם)

2.במניה המקורית לפני כל איבר a ב A היה מס' סופי של איברים, כל מה שעשינו

היה השמטת איברים ולכן גם במניה הזו יש לפניו מס' סופי של איברים.



טענה 2:

אם A בת מניה אז הוצאת/הכנסת איבר אחד משאיר את A בת מניה.

הוכחה:

הכנסה:

A בת מניה çקיימת פונקציה F חח"ע ועל מ N ל A .

נראה פונקציה G חח"ע ועל מ N ל A איחוד {a} : G[0]=a; G[i]=F[i] i>0

הוצאה:

A בת מניה çקיימת פונקציה F חח"ע ועל מ A ל N .

נראה פונקציה G חח"ע ועל מ A ל N הפרש {a} : G[x]=F[x] F[x]<F[a]

G[x]=F[x] - 1 F[x]>F[a]



----------------------------------------------



1.לפי טענה 1 A בת מניה, כי A אינסופית (כי יש לה יותר מחוצץ אחד) וגם תת קבוצה של Z (בת מניה).

2.ל A יש חוצץ (לפי הנתון) נקרא לו a ,עוצמת קבוצת האיברים הגדולים ממנו B שווה לעוצמת האיברים הקטנים ממנו S ,ולכן או ששתיהן סופיות או שתיהן אינסופיות.

אם שתיהן סופיות &ccedil; A סופית בסתירה ל 1 ולכן שתיהן אינסופיות &ccedil;גם S וגם B תתי קבוצות אינסופיות של קבוצה בת מניה A ולכן S,B בנות מניה.

נוכיח שגם a' (האיבר אחרי a במניה של A) הוא חוצץ :

S' היא S בהוספת a &ccedil;לפי טענה 2 S' בת מניה

B' היא B להוציא a' &ccedil;לפי טענה 2 B' בת מניה

וזה מוכיח ש a' הוא חוצץ.תחזור על תהליך זה לגבי a' וכך הלאה אפשר להוכיח שכל האיברים אחרי a במניה הם חוצצים,וזה בעצם מוכיח שיש אינסוף חוצצים כי יש אינסוף איברים אחרי a במניה של A .

הערות :

A לא חייבת להיות שווה ל Z.כמו שהרבה סטודנטים טענו.

סטודנטים רבים הסיקו מסעיף א' ש- A לא חסומה משני הכיוונים, היה צריך להראות ביתר פירוט למה זה נכון,ואז להראות שמשני הכיוונים יש מס' בן מניה של איברים ולהמשיך כמו הפתרון הנ"ל.

זה שיש אינסוף איברים אחרי ולפני איבר מסוים לא מוכיח שהוא חוצץ.

סטודנטים רבים הוכיחו ש- A אינסופית ולא התיחסו לקבוצת החוצצים שעליהם התבקשתם לענות.