מספר רמזי formula_21 (עבור formula_22) הוא המספר הקטן ביותר בעל התכונה הבאה: בכל אירוע שבו נפגשים formula_21 אנשים, מוכרחים להיות n אנשים שכולם מכירים זה את זה, או m אנשים שאף אחד מהם אינו מכיר את רעהו. (יחס ההיכרות הוא יחס סימטרי: אם a מכיר את b, אז גם b מכיר את a). מלכתחילה לא ברור שהמספרים האלו קיימים (משום שייתכן, לכאורה, שאפשר להימנע מן הקבוצות המיוחדות גם באירועים המוניים).
נוכיח שמספרי רמזי קיימים, בכך שנראה ש-formula_24, כאשר formula_25 הוא מקדם בינומי.
ראשית, formula_26 משום שאם אין אפילו זוג אנשים שאינם מכירים זה את זה, מוכרחים כולם להכיר את כולם. מאותה סיבה גם formula_27, ולכן הטענה נכונה כאשר n=2 או m=2. זהו בסיס האינדוקציה. כעת נניח ש-formula_28. נניח שבאירוע משתתפים formula_29 אנשים. נתבונן במערך ההיכרויות של אחד ממשתתפי האירוע: או שהוא מכיר לפחות formula_30 משתתפים, או שהוא אינו מכיר לפחות formula_31 משתתפים. במקרה הראשון, לפי ההגדרה של formula_30, יש בין האנשים שהוא מכיר n-1 מכרים-הדדית (ואז יש באירוע כולו קבוצה של n מכרים-הדדית), או שיש ביניהם קבוצה של m זרים-הדדית; במקרה השני, יש בין האנשים שהוא אינו מכיר קבוצה של n מכרים-הדדית, או שיש ביניהם קבוצה של m-1 זרים-הדדית (ואז יש m זרים-הדדית באירוע). הוכחנו שמספר המשתתפים גדול דיו כדי לחייב אחת משתי התוצאות שבהגדרה, ולכן formula_33.
לפי הנחת האינדוקציה, formula_34. (הערך המדויק של מספרי רמזי ידוע רק במקרים בודדים; אפילו הערך של formula_35 אינו ידוע).
דוגמה 4.
עץ בינארי הוא עץ מכוון, שבו לכל קודקוד יש לכל היותר שני בנים, ולכל קודקוד, פרט לקודקוד מיוחס הנקרא שורש, יש אב יחיד. קודקוד של עץ כזה נקרא גם צומת. עלה הוא צומת חסר בנים. עץ לא ריק הוא עץ שקיים בו שורש. צאצאים של כל צומת בעץ יוצרים ביחד איתו תת-עץ של העץ המקורי. נגדיר "צומת מלא" כצומת שיש לו שני בנים.
נוכיח באינדוקציה שבעץ בינארי לא ריק, שמספר העלים בעץ גדול ב-1 ממספר הצמתים המלאים בו.
עבור עץ עם צומת בודד הטענה מתקיימת: ישנו עלה אחד ואין צמתים מלאים. נניח שהטענה נכונה עבור כל עץ בינארי עם n צמתים, כאשר n חיובי. נוכיח שהטענה נכונה עבור עץ עם 1+n קודקודים:
בהינתן עץ שאינו שורש עם n+1 צמתים, נסיר ממנו עלה כלשהו ונקבל עץ חדש עם n צמתים. נסמן את מספר העלים ב-N0 ואת מספר הצמתים המלאים ב-N2. על-פי הנחת האינדוקציה בעץ החדש מתקיים השוויון N0=N2+1.
נחזיר חזרה לעץ את העלה שהסרנו.
אם העלה שהוסר היה בן יחיד מספר העלים לאחר החזרתו לא השתנה: מצד אחד עלה אחד נוסף ומצד שני אותו הצומת שהוסיפו לו עלה הפך מעלה לאב יחיד. מספר הצמתים המלאים לא השתנה אף הוא ולכן השוויון נשמר.
אם העלה שהוסר לא היה בן יחיד אז מצד אחד מספר הצמתים המלאים בעץ לאחר החזרת העלה גדל ב-1, ומצד שני מספר העלים גדל ב-1 לאחר החזרת העלה. ולכן גם במקרה זה השוויון נשמר.
דוגמה 5.
ישנן גם הוכחות שגויות, המבוססות על גרסה שגויה של אקסיומת האינדוקציה או שיש בהן דילוג על שלב מהותי. אף על פי שברוב ההוכחות באינדוקציה הבדיקה לערך קטן של n היא קלה ומיידית, ישנם מקרים שבהם צעד האינדוקציה תקין והבעיה היא דווקא בערכים הקטנים. דוגמה מפורסמת לתופעה זו היא פרדוקס הסוסים, המתיימר להוכיח שכל הסוסים בעולם הם בעלי אותו צבע. מכיוון שמספר הסוסים בעולם סופי, אפשר להוכיח את הטענה באינדוקציה: בכל קבוצה בת n סוסים, לכולם יש אותו צבע. טענה זו נכונה כמובן עבור n=1. כעת נניח שהטענה נכונה עבור n, ונוכיח אותה עבור n+1: נבודד אחד מבין n+1 הסוסים, כך שישארו n סוסים, שכולם בעלי אותו צבע לפי הנחת האינדוקציה. נחליף את הסוס שהוצאנו קודם לכן בסוס אחר, ושוב נקבל שלכל הסוסים בקבוצה שלפנינו אותו צבע. לכן לכל n+1 הסוסים יש אותו צבע.
הטענה נכונה עבור n=1, אבל המעבר בין n לבין n+1 תקין רק בתנאי ש-n&gt;1, משום שכדי להסיק שלכל n+1 הסוסים אותו צבע, אנו מניחים שבשתי הקבוצות בגודל n יש סוסים משותפים, שאליהם אפשר להשוות את שני הסוסים שהוצאנו בתחילת הצעד ובסופו. אם הטענה הייתה נכונה עבור n=2 (לכל שני סוסים יש אותו צבע), באמת אפשר היה להוכיח אותה לכל n. אבל המעבר בין n=1 לבין n=2 (אם לכל סוס יש הצבע שלו, אז לכל שני סוסים יש צבע משותף) שגוי, ולכן ההוכחה אינה תקפה.
תקפותה של הוכחה באינדוקציה.
לכאורה, מבוססת האינדוקציה המתמטית על הפעלה חוזרת של כלל הגזירה מודוס פוננס. לדוגמה, כדי להוכיח את הטענה formula_36, די להוכיח את טענת הבסיס formula_37, ואת הגרירות formula_38,
formula_39 ו-formula_40: מן הגרירה הראשונה נובע (לפי טענת הבסיס) formula_41, מן הגרירה השנייה נובע כעת formula_42, ומן השלישית – formula_36. מכיוון שבצעד האינדוקציה הוכחנו את כל הגרירות formula_44, אפשר להוכיח באופן הזה את כל הטענות formula_8.
אם לדייק, מצאנו, לכל n, סדרה סופית של טיעונים, המוכיחה ש-formula_8; אבל מספר הצעדים בכל הוכחה הולך וגדל. זהו מעין "אפקט דומינו": כל אבן מפילה את האבן שאחריה, וכל אבן תיפול בזמן סופי, אבל אם השרשרת אינסופית, הזמן עד שיפלו כולן הוא אינסופי. עקרון האינדוקציה הופך את הסדר: הוא נותן הוכחה בסדרה סופית של טיעונים, לכל אינסוף הטענות formula_8.
יש שתי גישות להצדקת עקרון האינדוקציה. במערכת האקסיומות המגדירה את מערכת פאנו של המספרים הטבעיים, ישנה סכימת אקסיומות מיוחדת, הקובעת את חלות האינדוקציה. במסגרת הרחבה יותר של תורת הקבוצות האקסיומטית, המבוססת על אקסיומות צרמלו-פרנקל, נובע עקרון האינדוקציה מכך שקבוצת המספרים הטבעיים סדורה היטב (ראו עקרון הסדר הטוב): אם הטענה formula_8 אינה מתקיימת לכל n, מוכרח להיות מספר קטן ביותר שעבורו היא אינה מתקיימת; מספר זה אינו יכול להיות 1, משום שבסיס האינדוקציה מאשר את הטענה formula_37, והוא אינו יכול להיות גדול מ-1, משום שבמקרה כזה הטענה formula_8 נובעת מן הטענה formula_51, הנכונה לפי המינימליות של n.
בתורה, העובדה שקבוצת המספרים הטבעיים סדורה היטב נובעת מאקסיומת האינסוף (הקובעת שקיימת קבוצה רקורסיבית אינסופית), ומאקסיומת היסוד.
מספר טבעי
במתמטיקה מספר טבעי הוא מספר שלם חיובי, המתאר מספר איברים בקבוצה סופית, כמו 1,2,3 או כמו 72. מקובל לסמן את קבוצת המספרים הטבעיים באות formula_1. המספר אפס נכלל בין המספרים הטבעיים בהגדרות אחדות, ואינו נכלל בהגדרות אחרות.
המספרים הטבעיים הם הקלים ביותר להבנה, והראשונים שנלמדים על ידי ילדים. למספרים טבעיים שתי מטרות:
תכונותיהם של המספרים הטבעיים נחקרות במסגרת תורת המספרים.
קבוצת המספרים הטבעיים היא אינסופית ובת מנייה, כלומר עוצמתה היאformula_2 (אָלֶף אֶפֶס).
הגדרה ובנייה.
המספרים הטבעיים הם הראשונים שהופיעו כמושגים נבדלים: מספר טבעי מונה את האיברים בקבוצה. אפשר לראות את ההבחנה שיש משהו משותף בקבוצה של שלושה אנשים, שלושה תפוחים או שלושה נמרים כהכללה המתמטית הראשונה שעשו בני האנוש (ישנם מחקרים המראים שגם לבעלי חיים מסוימים יש יכולת הכללה זו). לאופולד קרונקר אמר ש"האל יצר את המספרים הטבעיים - כל השאר הוא יציר האדם".
במסגרת היציקה המודרנית של המתמטיקה לשפת תורת הקבוצות, הציע הלוגיקאי גוטלוב פרגה שהמספר שלוש הוא, בפשטות, קבוצת כל הקבוצות שיש בהן שלושה איברים (היינו, שהאיברים שלהן נמצאים בהתאמה לקבוצה מסוימת בת שלושה איברים). בגישה זו יש פרדוקסים, הנובעים מכך שאוסף כל הקבוצות הוא מקור לפרדוקסים מחמת גודלו, ואינו יכול להוות קבוצה בפני עצמו (ראו פרדוקס קנטור).
הבניה של מערכת פאנו מאפשרת לקבוע שמספר טבעי הוא איבר של מערכת פאנו (כל המודלים של אקסיומות פאנו הם איזומורפיים).
פון נוימן הציע בנייה מפורשת, המקובלת היום כייצוג סטנדרטי של המספרים הטבעיים בתוך תורת הקבוצות האקסיומטית: המספר 0 מוגדר כקבוצה הריקה, וכל מספר formula_3 מוגדר כקבוצה formula_4. כך למשל, formula_5.
מספרים טבעיים ראשוניים ופריקים.
בתורת המספרים, מספר ראשוני הוא מספר טבעי גדול מ-1, שלא ניתן להציגו כמכפלה של בדיוק שני מספרים טבעיים קטנים ממנו.
הראשוניים הם אבני הבניין של תורת המספרים, משום שאפשר להרכיב מהם, באמצעות פעולת הכפל, כל מספר טבעי.
מספר טבעי גדול מ-1 שאינו ראשוני נקרא מספר פריק.
המספר 1 אינו נחשב ראשוני, וגם לא פריק.
לפי "המשפט היסודי של האריתמטיקה", שהוצג לראשונה עם הוכחה, על ידי אוקלידס, כל מספר טבעי גדול מ-1 אפשר להציג באופן יחיד כמכפלה של מספרים ראשוניים (למשל: formula_6).
חיכוך
במכניקה, חיכוך הוא כוח הפועל באזור המגע של שני גופים הנמצאים במגע זה עם זה, ופועל באופן שמתנגד לתנועה יחסית בין הגופים, או לנטייה לתנועה כזו. הכוח נוצר כאשר על שני הגופים פועלת מערכת של שני כוחות ניצבים זה לזה: כוח ניצב לשטח המגע, הלוחץ את הגופים זה לזה (כוח שנוצר בדרך כלל כתגובה לכוח הכובד), וכוח נוסף, הפועל על אחד הגופים במקביל לאזור המגע. כוח החיכוך הוא למעשה כוח תגובה לכוח המקביל, והפוך לכיוון תנועת הגוף. גודלו המרבי של כוח החיכוך תלוי בגודל הכוח הניצב ובסוג החומר ממנו עשויים שני הגופים.
לחיכוך יש השלכות טכנולוגיות רבות, והמדע העוסק בחקר החיכוך, השחיקה והשימון נקרא טריבולוגיה .
סימון.
באופן כללי כוח החיכוך מסומן כך:
formula_1
כאשר האות F הגדולה מציינת שמדובר בכוח והאות f הקטנה היא קיצור של המילה חיכוך באנגלית - Friction.