בתשובה להאייל הצעיר, 04/09/05 23:44
על מושג האירציונליות 327582
לא טענתי אחרת שיש, בכל הנוגע לנכונות הטענה, אם כי ההוכחה קצת פחות מיידית: צריך להראות שכל שארית חלוקה ב-p, כשהיא מועלית בריבוע, לא מתחלקת ב-p.
על מושג האירציונליות 327583
אתה לא טענת אחרת. משה כן ‏1. הטיעון הזה מופנה כלפיו. משה טען שבלי המשפט היסודי של האריתמטיקה אפשר להוכיח את הטענה הזאת רק עבור 2.

1 בפתיל שמתחיל בתגובה 327530.
על מושג האירציונליות 327585
הטענה יותר בעייתית: היא אומרת שלכל n שאינו ריבוע (לא בהכרח ראשוני) מתקיים שאם n מחלק את a^2 אז n מחלק את a.

אם יש לך הוכחה של זה שאינה מערבת את המשפט היסודי, אני אשמח לשמוע.
על מושג האירציונליות 327586
הדגשתי את זה בתגובה 327559: לא ניתן (כנראה) להוכיח בלי המשפט היסודי של האריתמטיקה, את הטענה "לכל p ראשוני, שורש p אירציונלי". לעומת זאת, עבור כל p ראשוני, ניתן להוכיח את הטענה "שורש p אירציונלי".
על מושג האירציונליות 328325
זוהי הבחנה דקה ויפה
על מושג האירציונליות 328330
האמת, כשאני קורא שוב את ההודעה אני לא ממש מבין אותה. נניח שעבור כל p ראשוני, ניתן להוכיח את הטענה "שורש p אירציונלי". הנה הוכחה שלכל p ראשוני, שורש p אירציונלי: יהי p ראשוני כלשהו. יש להראות שהשורש שלו אי רציונלי. ידוע כי קיימת הוכחה שהשורש שלו אי רציונלי, ולכן השורש שלו אי רציונלי. מ.ש.ל?
על מושג האירציונליות 328347
לא, כי אנחנו (כלומר, הצעיר) יודעים שעבור כל p ראשוני נצליח להוכיח את הטענה "שורש p אירציונלי" רק בזכות המשפט היסודי של האריתמטיקה, והצעיר החליט לא להשתמש בו.
על מושג האירציונליות 328368
זה רק הופך את ההודעה ההיא של הצעיר למובנת עוד פחות לי.
על מושג האירציונליות 328377
למה? את המשפט "לכל p ראשוני שורש p אי-רציונלי" אפשר להוכיח רק אם מניחים משהו על פריקות - המשפט היסודי של האריתמטיקה. אם אנחנו מחליטים שאנחנו לא יודעים את המשפט הזה, הוא לא הופך באחת ללא-נכון, רק שאסור לנו להשתמש בו. לכן, אנחנו יכולים לעבור p אחרי p וכל פעם להוכיח "בכח" שהשורש שלו אי-רציונלי.
אולי יום אחד נתקל ב-p ששורשו רציונלי? כאן בא אחד שיודע את המשפט היסודי ואומר לנו, כמיטב המסורת הישראלית - "יהיה בסדר. סמוך".
על מושג האירציונליות 328378
מה זאת אומרת "בכוח"? תוכל להראות את ההוכחה?
על מושג האירציונליות 328380
מישהו כבר הקדים אותי: תגובה 327564 מראה איך לעשות את זה עבור 2, ו-תגובה 327579 נותנת את המתכון לכל מספר ראשוני (ולכך התכוונתי ב-"בכוח"): לכל p מכינים רשימת שאריות (1 עד p-1) ומראים שכל העלאה בריבוע של מספר המתחלק ב-p עם כל אחת מהשאריות לא מתחלקת ב-p.
כך נוכל להראות שאם a^2=b^2*p אז גם a וגם b מחלקים את p, ומגיעים לסתירה.
יכול להיות שאני לא מבין משהו עמוק כאן, ואולי עדיף לחכות לצעיר.
על מושג האירציונליות 328385
יפה. מכיוון שההוכחה הזו כללית לכל p, אין שום מניעה להוכיח את המשפט "לכל p שורש p אי רציונלי" בלי להשתמש במשפט היסודי של האריתמטיקה: יהא p כלשהו אז נשתמש בהוכחה הכללית כדי להראות שריבוע מתחלק על ידי p אם ורק אם השורש שלו מתחלק על ידי p ובא לציון גואל. השימוש היחיד שצריך לעשות במשפט היסודי של האריתמטקה הוא כדי שהטענה תהיה נכונה לשורש של כל n שאיננו ריבוע, גם אם n לא ראשוני.
על מושג האירציונליות 328390
אני אולי לא מבין מספיק מתמטיקה, אבל איך אתה מוכיח עבור שארית a כללית ש-a^2 לא מתחלק ב-p בלי המשפט היסודי?
(מעניין אותנו a^2 כי את הריבוע אפשר לפתוח לשני גורמים שבוודאות מתחלקים ב-p ועוד a^2).
על מושג האירציונליות 328395
עוזי הראה בתגובה 327627.
על מושג האירציונליות 328398
אכן לא הבנתי את התגובה ההיא ואיך ההוכחה שם הולכת. כנראה שאני מפספס משהו מאוד בסיסי פה, אז אני אפסיק להטריד.
על מושג האירציונליות 328401
אתה לא מטריד. עוזי מתבסס על מה שמכונה "האלגוריתם האוקלידי". בעזרת האלגוריתם ניתן להראות שאם x זר ל-n אז קיימים מספרים שלמים a,b כך ש-an+bx=1. האלגוריתם הזה מתקיים באוסף מיוחד של חוגים שנקראים "חוגים אוקלידיים" ושיש בהם מושג כלשהו של חילוק עם שארית (אם תרצה אני ארחיב) - המספרים השלמים הם חוג כזה, ולא צריך את המשפט היסודי של האריתמטיקה בשביל להראות את זה. גם ההפך נכון אם an+bx=1 עם a,b שלמים אז x,n זרים (כי המחלק המשותף המקסימלי של x,n מחלק כל אחד משני האיברים בסכום אז הוא מחלק גם את מה שבצד ימין, ולכן הוא חייב להיות 1).

עכשיו עוזי לוקח את המספרים שלנו וכותב ax+bn=1 ו- cy+dn=1. הוא כופל ומקבל את הדבר הבא:

(ac)xy+(da+cb+db)n=1

תכפול ותעשה כינוס איברים אם אתה לא מאמין לי. אבל מה קיבלנו? מה שבסוגריים הם מספרים שלמים, ולכן אפשר להפעיל את הכיוון ההפוך ולקבל ש-xy זר ל-n.
על מושג האירציונליות 328404
כינוס האברים לא יצא לי ממש מה שכיוונת (בתוך הסוגריים לפני n יצא לי dax+bcy+dbn, זה לא משנה כי זה בכל מקרה שלם), אבל הבנתי את ההוכחה. עוזי לא רשם שהמספרים a עד d שלמים ולא הכרתי את "האלגוריתם האוקלידי".
תודה רבה.
על מושג האירציונליות 328432
בכינוס האיברים כמובן שזו טעות שלי ואתה צודק (גם בתשובה וגם בכך שזה ממילא מספר שלם). אם אתה לא מכיר את האלגוריתם האוקלידי זה קצת יותר בעייתי, כי קשה להסביר על רגל אחת. אני אנסה כאן ואפשר גם לקשר אותך לויקיפדיה:
הרעיון הבסיסי הוא זה: אם יש לך יכולת לחלק דברים עם שארית (כלומר, אם יש לך איברים x,y אז קיימים איברים q,r כך ש-x=qy+r כאשר r קטן מ-y במובן מסויים שלא ניכנס אליו כאן אבל כשמדובר במספרים שלמים הוא פשוט הערך המוחלט שלהם) אז יש אלגוריתם למציאת מחלק משותף מקסימלי של שני איברים.

מחלק משותף מקסימלי d של x,y הוא פשוט מספר שמחלק את x,y וכל מספר שמחלק גם את x וגם את y מחלק בהכרח גם את d. כבר אתה רואה ש-d לא יחיד - מחלק משותף מקסימלי של 6,15 הוא גם 3 וגם מינוס 3. מתברר שזה ההבדל היחיד שיכול להיות בין מחלקים מקסימליים במספרים שלמים - הסימן.

איך עובד האלגוריתם האוקלידי? נניח שהמספרים שלנו הם x>y ולצורך פשטות הם טבעיים. תחלק את x ב-y ותקבל, כאמור, x=qy+r. עכשיו שים לב למשהו מעניין: מחלק משותף מקסימלי של y ו-r הוא גם מחלק משותף מקסימלי של x,y (שאנחנו מסמנים d). למה? ברור ש-d מחלק את r כי הוא מחלק את x,y והרי r=x-qy (אז d מחלק כל גורם באגף ימין ולכן מחלק את אגף שמאל). בנוסף, אם e הוא איבר שמחלק את r,y (סליחה על עודף האותיות) אז הוא מחלק גם את x, כי הרי x=qy+r. לכן e מחלק את d, כי הרי אמרנו שכל מי שמחלק את x ואת y מחלק את d.

מה יצא לנו מכל זה? שעכשיו כדי למצוא את מחלק משותף מקסימלי של x,y מספיק למצוא מחלק משותף מקסימלי של y,r, והרי y>r ולכן הממדים של הבעיה שלנו מצטמצמים, ואנחנו יכולים להמשיך באותה השיטה בדיוק עד שנקבל בשלב מסויים שני מספרים a>b שאנחנו מחפשים להם מחלק משותף מקסימלי ומתקיים ש-b מחלק את a ללא שארית, ואז b הוא מן הסתם המחלק המשותף המקסימלי.

כל זה ארוך ומסובך אבל לא השתמשנו בכלל במשפט היסודי של האריתמטיקה.

עכשיו נשאר הטוויסט האחרון, שאני לא אוכיח לך כאן: אם d הוא מחלק משותף מקסימלי של x,y אז קיימים מספרים שלמים a,b כך ש-ax+by=d - ואפשר למצוא אותם באמצעות הרחבה קלה של האלגוריתם האוקלידי.

אם כל זה ברור לך ועדיין ההוכחה של עוזי לא ברורה לך תגיד ואני אמשיך (כבר כמעט גמרנו).
על מושג האירציונליות 328454
יפה מאוד ותודה רבה. אין צורך להמשיך.
אלגוריתם אוקלידס - נוסח מקוצר 328460
לא חיוני לשיחה, אבל הגרסה שלהלן כל כך חמודה:
כדי למצוא את הממג"ב של a ו־b, חסר מן הגדול את הקטן. המשך עד שתקבל אפס באחד מהם. השני הוא הפתרון.
אלגוריתם אוקלידס - נוסח מקוצר 328472
מה שמעניין הוא אם האלגוריתם הזה יעיל באותה מידה כמו האלגוריתם המקורי. למישהו יש דוגמה שעליה האלגוריתם הזה "ייתקע" להרבה זמן?
אלגוריתם אוקלידס - נוסח מקוצר 328482
אם אתה מחפש את הממג"ב של 1,000,000 ו-‏7, האלגוריתם המחסר יבלה זמן רב בניסיון להיפטר מה-‏7.

זו חידה נחמדה למצוא את צמדי המספרים הכי גרועים לאלגוריתם האוקלידי (רמז: בצמדים האלה, האלגוריתם המחלק מתנהג דומה מאוד לאלגוריתם המחסר). (עוד רמז: שפנים).
אלגוריתם אוקלידס - נוסח מקוצר 328494
פיבונאצ'י?
אלגוריתם אוקלידס - נוסח מקוצר 328495
כן. (למה?)
אלגוריתם אוקלידס - נוסח מקוצר 328502
נניח ש-x,y הם שני מספרי פיבונאצ'י רצופים, אז x=y+z כש-z הוא זה שלפני שניהם, ו-y>z כי y עצמו הוא סכום של שני מספרים טבעיים שאחד מהם הוא z. לכן x=y+z זו גם החלוקה עם שארית של x ב-y.

נחמד.
אלגוריתם אוקלידס - נוסח מקוצר 328527
בינתיים רק הסברת למה בהפעלת אוקלידס על פיבונצ'י, המנה בכל סיבוב היא תמיד 1 (והשארית היא מספר פיבונצ'י קודם). אינטואיטיבית זה נראה "הכי גרוע", אבל זה תרגיל מעניין וחינוכי לנסח בדיוק את הטענה שזה באמת "הכי גרוע", ואז להוכיח אותה בזהירות.
אלגוריתם אוקלידס - נוסח מקוצר 328483
מה זה כבר מקדם פולינומי ביני ובינך...
אלגוריתם אוקלידס - נוסח מקוצר 328474
ממג"ב?
אלגוריתם אוקלידס - נוסח מקוצר 328477
מחלק משותף גדול ביותר.
אלגוריתם אוקלידס - נוסח מקוצר 328481
תודה.
על מושג האירציונליות 328411
עיקר שכחתי - אשמח אם תרחיב על האלגוריתם האוקלידי.
על מושג האירציונליות 464354
מי שיודע מה זה כופל משותף מקסימלי?
על מושג האירציונליות 328384
למשחק "הוכח ש... בלי להשתמש ב..." יש לפעמים ערך פדגוגי, לא מתמטי. במקרה שלנו, אגב, באמת לא צריך את המשפט היסודי של האריתמטיקה - ראה תגובה 327627.
ערך לא פדגוגי ולא מתמטי 328387
הוכח שהגבול של sinx/x כש-x שואף לאפס הוא 1 מבלי להשתמש בכך שידוע ששטחו של מעגל היחידה הוא פאי. בכל הספרים שראיתי ההוכחה הגיאומטרית מתבססת על הנתון הזה או על דברים ש"קל לראות" מהשרטוט, אבל לא ברור לי איך מוכיחים שהשטח של מעגל היחידה הוא פאי בלי להשתמש איכשהו בגבול הזה קודם.

(אם אפשר, גם בלי להגיד "sinx מוגדר להיות הטור x-x^3/6+..." - השאלה היא האם אפשר בלי זה).
ערך לא פדגוגי ולא מתמטי 328392
הנגזרות של סינוס נחשבות למידע שהושג בעזרת כך שידוע ששטחו של מעגל היחידה הוא פאי?
ערך לא פדגוגי ולא מתמטי 328394
כדי לגזור את סינוס (כפי שהוא מוגדר בעזרת מעגל היחידה) אתה צריך את הגבול sinx/x (ככל הידוע לי). בשביל לגזור את סינוס אם הוא מוגדר כטור אתה רק צריך להראות שהטור מתנהג נחמד.
ערך לא פדגוגי ולא מתמטי 401385
לפרשייה הזו יש הפי אנד:
(ואפשר גם לעיין ב-Calculus של Moise שגם מוכיח את הגבול בצורה משכנעת בלי להשתמש בשטח המעגל וגם מחשב את שטח המעגל בצורה משכנעת בלי להשתמש בגבול).
על מושג האירציונליות 328422
אלא אם ה... (האחרונות) הן אקסיומה בלתי תלויה.
על מושג האירציונליות 328447
במקרה הזה זו פשוט הייתה תגובה למשה, שטען טענה היסטורית: לפני שידעו את המשפט היסודי של האריתמטיקה, ניתן היה להשתמש בשיטת ההוכחה האלגברית שמשה הציג כדי להוכיח את אי הרציונליות *רק* של שורש 2. אני טענתי שגם בלעדיו יכלו בקלות להרחיב את ההוכחה לשורשים של ראשוניים אחרים. זה הכל.
על מושג האירציונליות 328459
האמת היא שהפתיל הזה, כמו שאמר עוזי, מיותר. הוא התחיל מטענה היסטורית שטען משה: לפני שהכירו בני האדם את משפט היסוד של האריתמטיקה, הם יכלו להוכיח באמצעות ההוכחה האלגברית עליה אנחנו מדברים *רק* ששורש 2 אירציונלי. אני הראיתי שיש הרחבה פשוטה שלו גם לראשוניים אחרים.
אח"כ עברנו לדיון מתמטי-סמנטי על מיקום הכמת "לכל" לפני ואחרי המרכאות. דיון כזה הוא כמובן מתמטי ולא היסטורי, ולכן אין טעם להמשיך להתעלם מקיומו של המשפט היסודי של האריתמטיקה.

ובכל זאת אני אענה לך: קודם חשבתי שכדי להוכיח את ה"ידוע" שלך חייבים להשתמש ב"משפט האסור". עוזי הראה שטעיתי.
על מושג האירציונליות 327596
(הטענה הזו לא נכונה: קח n=8 ו- a=4).
על מושג האירציונליות 327600
עוזי:
(הטענה הזו לא נכונה: קח n=8 ו- a=4).

אביב:
אבל זו בסה"כ הפרכה ע"י דוגמא נגדית וזה לא מחזיק מים. הבעיה היא שאתה מניח את הפרכת הטענה ע"י דוגמתך משום שאתה שבוי בתפישה בה הטענה יכולה להיות רק נכונה או לא נכונה ואתה מתעלם לחלוטין הן ממצבי רוויה והן מן המצבים המעורבלים הנדירים (אך מהותיים למערכת) שאליהם ניתן להגיע. אם היית מוסיף לתורת הקבוצות את ההנחה לגבי קיום הקבוצה המעורבלת (המסומנת כך {..۞..} בניגוד למצב ההופכי של הקבוצה המנותקת לסירוגין {__ __ __}) היית מגיע למסקנה שהמצב המעורבל כולל את רשמי החושים בצורה המתאזנת עם ההנחות הלא מודעות, בקרב יצורים תבוניים, כפי שמתואר בפירוט באסטרולוגיה הגושמנית.

כמובן, שלפני שתוכל להבין תגובה זו, אני ממליץ על קריאת הפירוט על אותה תורה שחושפת את האמת לגבי מושג הזמן ועוקרת את הקוסנפציה שלנו לגבי יחסי סיבה-תוצאה. תורה זו, המערערת את אושיות החשיבה המערבית, כפי שאנו מכירים אותה היום, אף מפריכה את הלוגיקה הטמפולרית ואת עצם האפשרות לקיומו של פתית השלג של Koch. ראה את המאמר אודות האסטרולוגיה הגושמנית שהעלתי לרשת http://humor.co.il/astrology.php?PHPSESSID=8281ac011...).

תודה.
על מושג האירציונליות 327612
אופס.

איך מוכיחים ששורש 8 אי רציונלי? מתבססים על אי הרציונליות של שורש 2?

האם הטענה כן נכונה עבור מספרים שאינם מתחלקים על ידי ריבוע? אחרת קצת קשה לי לראות איך אפשר, מנכונות הטענה עבור p ראשוני, להגיע לכך שהיא נכונה לכל n שאינו ריבוע.
איך מוכיחים 327616
אולי אני לא מבין מה אתה לא מבין, אבל הנה: אם

a^2 = m b^2

אז נשים לב שכל ראשוני מחלק את a^2 וגם את b^2 מספר זוגי של פעמים, ולכן גם את m מספר זוגי של פעמים, וזהו.
איך מוכיחים 327627
אתה נופל בכשל הידוע בשם 'שימוש במשפט היסודי של האריתמטיקה', שבמקום מסויים בפתיל הזה הוחלט מסיבות לא ידועות להסתדר בלעדיו. (דלג) אבל אי אפשר.
הדרך הקלה להוכיח שאם x ו- y זרים ל- n אז גם המכפלה שלהם זרה ל- n, היא לכתוב ax+bn=1 ו- cy+dn=1, ולהכפיל את המשוואות. במקרה ש- n ראשוני, אנחנו בעצם מוכיחים שכל מספר אי-פריק (=אין לו מחלקים) הוא ראשוני (=מוכרח לחלק גורם בכל מכפלה שהוא מחלק), וזה נכון בתחומי פריקות יחידה (=המשפט היסודי של האריתמטיקה מתקיים), אבל לא בתחומי שלמות אחרים. (ע"כ)
תחומי שלמות אחרים 328033
הטענה "לכל איבר בחוג שיש לו שורש ריבועי בשדה השברים, יש שורש בחוג" נכונה לא רק בתחומי פריקות יחידה. למשל, [(Z[sqrt(-5 איננו UFD אך הטענה נכונה לגביו‏1. מצד שני, אפשר לבנות "בכוח" דוגמה לתחום שלמות בו הטענה הזו אינה נכונה:

R = C[X,Y,T] / <X^2 - T Y^2>

כאן "רואים" של-T אין שורש ב-R, אבל יש לו בוודאי שורש בשדה-השברים של R. עוד אין לי הוכחה למה ש"רואים" וייתכן שיש פה איזו הפתעה, אבל נראה לי שזה עובד. אני עדיין קצת סקרן לבחון אם הטענה בכל זאת נכונה, נניח, בשדות מספרים; בינתיים לא מצאתי הוכחה כללית.

1 ברור שכדי להוכיח זאת, משתמשים בפריקות יחידה, אבל לא בחוג (שם אי-אפשר) אלא ב-Z.
תחומי שלמות אחרים 328039
(הוכחה שאין ל- T שורש בחוג: השורש בשדה השברים יחיד עד כדי סימן, ולכן מספיק להראות ש- X/Y אינו שייך ל- R. כלומר, להראות ש- X אינו שייך לאידיאל <Y> של R. אבל מודולו האידיאל הזה, [R/<Y>=C[X,T|X^2=0 וקל לראות ש- X אינו אפס).
תחומי שלמות אחרים 328041
(לחליפין, אפשר פשוט לרשום

T + q(X,Y,T)(X^2-T Y^2) = f(X,Y,T)^2

ולהסתכל על דרגות ומקדמים חופשיים).
תחומי שלמות אחרים 328040
(א-נו. כבר יש לי הוכחה למה ש''רואים'', והיא באורך שורה).
תחומי שלמות אחרים 328050
התכונה הזו נכונה גם בחוגי דדקינד‏1. קצת מפתיע.

1 נניח ש- a^2=xb^2 בחוג. מפירוק לאידיאלים ראשוניים יוצא שהאידיאל ש-x יוצר הוא ריבועי, נניח I^2. אחרי הוצאת שורש רואים ש- I הוא ראשי, ולכן x הוא ריבוע עד-כדי יחידות. אבל אם יחידה היא ריבוע בשדה, אז היא ריבוע בחוג (כל היחידות שם ממילא).
תחומי שלמות אחרים 328055
התכונה הזו נכונה פשוט בחוגים סגורים בשלמות‏1. לא כל כך מפתיע :-)

1 אם ל-a יש שורש ריבועי בשדה השברים, השורש הזה מקיים את המשוואה המתוקנת X^2-a = 0. אם החוג סגור בשלמות, השורש הזה כבר נמצא בחוג.

חזרה לעמוד הראשי

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים