tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
מכאן שיש פונקציה חד-חד-ערכית מ- לקבוצת הפונקציות מהרציונליים לממשיים , ולכן .
קבוצת הרציונליים שקולה לקבוצת הטבעיים, ולכן בעזרת כללי אריתמטיקה של עוצמות (ומהזהות הנובעת מפונקציית הזיווג של קנטור) נקבל:
מצד שני, לכל מספר ממשי ניתן להתאים את הפונקציה הקבועה שהיא רציפה.
קבוצה זו כוללת בין השאר כל פונקציה מציינת של .
קבענו כבר כי עוצמת קבוצת הפונקציות המציינות של היא .
לפי משפט קנטור , ולכן .
תוצאה זו תקפה, באותה מידה ומאותם שיקולים, לקבוצת הפונקציות שיש להן לכל היותר מספר בן מנייה של נקודות אי רציפות.
שיקולי עוצמות הם גסים מידי מכדי להראות שרוב הפונקציות אינן רציפות באף נקודה.
לשם כך דרושים כלים עדינים יותר מתחום הטופולוגיה.
ממשפט קנטור מגיעה המוטיבציה להגדרת סדרה של עוצמות הקרויה מספרי ב'.
משפט קנטור מבטיח כי כל העוצמות הללו שונות.
בהגדרה רקורסיבית, מספרי ב' מוגדרים:
מספרי ב' מוגדרים גם לאינדקסים סודרים, ולא רק טבעיים.
לשם כך יש להוסיף להגדרה הרקורסיבית את המקרה של סודר גבולי:
למשל הוא העוצמה הקטנה ביותר שגדולה מכל העוצמות לכל טבעי.
בנוסף קנטור הגדיר את הסדרה (המוכללת) כסדרת כל העוצמות ( הוא העוצמה ה- בגודלה).
קנטור שיער ש- (כלומר שאין עוצמה בין עוצמת הטבעיים לעוצמת הממשיים).
השערות אלו ידועות כהשערת הרצף והשערת הרצף המוכללת בהתאמה.
חרף מאמציו הרבים, קנטור מעולם לא הצליח להוכיח או להפריך את ההשערה עד יום מותו.
התקדמות ראשונה בנושא הושגה על ידי קורט גדל שהוכיח בשנת 1937 כי השערת הרצף אינה סותרת את האקסיומות המקובלות של תורת הקבוצות.
גורלה של ההשערה הוכרע סופית בשנת 1963 כאשר פול כהן הוכיח כי גם שלילתה של השערת הרצף אינה סותרת את האקסיומות של תורת הקבוצות.
מכאן שהשערת הרצף היא טענה עצמאית (והיא הדוגמה המפורסמת ביותר לטענה שכזו), שאין אפשרות להוכיחה או להפריכה.
הוכחת משפט קנטור יחד עם טיעון האלכסון של קנטור שהוצג לצדה הולידו שיטה כללית להוכחת טענות המשמשת בתחומים רבים במתמטיקה.
השיטה נקראת אלכסון, והיא משמשת בעיקר במדעי המחשב ובלוגיקה מתמטית.
הרעיון הכללי בשיטת האלכסון הוא לבנות אובייקט מתמטי קביל המתייחס לעצמו באופן עקיף.
אופי ההתייחסות תלוי בטענה שאותה רוצים להוכיח.
הוכחה כללית בשיטה זו בנויה כך: בהינתן אוסף של איברים ואוסף של אובייקטים מהצורה , לכל .
נניח שכל אובייקט פועל בצורה כלשהי על איברי .
נסמן את הפעולה של על כ- (ניתן לחשוב על כפונקציה של איברי ).
מגדירים אובייקט שנקרא ה"אלכסון", כך שתוצאת הפעולה נקבעת על פי תוצאת הפעולה .
אם קיים כך ש-, אז הכרח שהוא מתייחס לעצמו, שכן לפי ההגדרה, נקבע על פי , כלומר על פי עצמו.
השם "אלכסון" מקורו בהמחשה הוויזואלית של שיטת ההוכחה, כפי שהיא מודגמת בטיעון האלכסון של קנטור.
הרעיון הוא לדמיין טבלה (אינסופית לרוב) שכל שורה בה מייצגת איבר וכל עמודה בה מייצגת אובייקט (באותו הסדר).
בהצטלבות בין השורה של לעמודה של מופיע .
אובייקט ה"אלכסון" נבנה על סמך התאים בטבלה שהם מהצורה , שמסודרים בקו אלכסוני לאורך ורוחב הטבלה.
להלן דוגמאות חשובות להוכחה בשיטת האלכסון:
הוכחת משפט קנטור היא מקרה כללי של הוכחה בשיטת האלכסון.
נדגים זאת עם נוסח ההוכחה לפונקציות מציינות, שנוח יותר לשימוש במקרה הזה.
מניחים בשלילה כי לכל פונקציה מציינת של ניתן להתאים איבר של .
האובייקט הוא הפונקציה המציינת שהותאמה לאיבר .
הפעולה היא פשוט הפעולה הרגילה של הפונקציה על האיבר .
אובייקט האלכסון הוא פונקציה מציינת כך ש- מוגדר כהיפך מ- (0 אם הוא 1, ו-1 אם הוא 0).
לפי ההנחה קיים כך ש-, ולכן .
זוהי סתירה, ולכן ההנחה שגויה ומשפט קנטור נכון.
כאמור, אלן טיורינג הוכיח בלכסון כי בעיית העצירה אינה ניתנת להכרעה.
כלומר לא קיימת תוכנית מחשב שבהינתן כל תוכנית מחשב וקלט אפשרי, תכריע האם התוכנית הנתונה תסיים את פועלה על הקלט הנתון, או שתכנס ללולאה אינסופית.
במקרה הזה היא קבוצת כל תוכניות המחשב (בשפה כלשהי).
נניח שקיימת תוכנית שבהינתן תוכנית וקלט מכריעה האם עוצרת על .
הביטוי יהיה "כן" אם עוצרת על , ו"לא" אם נכנסת ללולאה אינסופית בהינתן .
נגדיר תוכנית שבהינתן קלט , מריצה את כדי לגלות מהו (תוכנית יכולה לקבל כקלט את עצמה, שכן כל תוכנית היא בסך הכל רצף של סימנים בשפה) - אם הוא "לא" אז משיבה "כן", ואם הוא "לא", אז לא עוצרת.
כמסקנה נקבל ש- הוא ההפך מעצמו.
סתירה זו מראה כי ההנחה שלנו כי קיימת תוכנית שמסוגלת להכריע את בעיית העצירה היא שגויה.
משפט האי-שלמות הראשון, שהוכח על ידי קורט גדל בשנת 1931, הוא משפט מרכזי בלוגיקה מתמטית.
המשפט קובע שבכל תורה העונה לתנאים מסוימים, קיימות טענות עצמאיות שלא ניתנות להוכחה או להפרכה.
השלב העיקרי בהוכחת גדל מתבצע בלכסון.
במסגרת ההוכחה מתעניינים בכל התכונות שניתן לנסח בתורה הנוגעות למספרים טבעיים.
את התכונה שמספרה הוא (מספור גדל מראה כיצד להצמיד לכל תכונה מספר משלה) נסמן .
הביטוי הוא הטענה שהמספר מקיים את התכונה (הטענה עשויה להיות נכונה או שגויה).
גדל הראה כיצד ניתן לבנות בשפה תכונה (זוהי ) שמתקיימת רק לאותם מספרים טבעיים שלגביהם לא קיימת הוכחה לטענה .
כלומר הטענה נכונה אם ורק אם אין הוכחה לטענה .
כעת נפרש את המשמעות של הטענה .
לפי הבניה, זוהי טענה שנכונה אם ורק אם אין הוכחה ל-.
כלומר זוהי טענה שאומרת "אני נכונה אם ורק אם אי אפשר להוכיח אותי".
משפט קנטור בתורת הקבוצות האקסיומטית ובתורות חלופיות
הפרדוקסים שנתגלו בגישתו של קנטור לתורת הקבוצות – גישה שלימים נקראה תורת הקבוצות הנאיבית – הביאו לפיתוחה של תורת הקבוצות האקסיומטית.
התורה האקסיומטית מסתמכת על מערכת של אקסיומות בסיסיות ומוגדרות היטב, כדי למנוע את הופעתם של פרדוקסים.
המערכת המקובלת היא מערכת האקסיומות של צרמלו-פרנקל (ZF).
במערכת זו משפט קנטור תקף לגבי כל קבוצה.
אקסיומת קבוצת החזקה מבטיחה את קיומה של קבוצת החזקה ואקסיומת ההחלפה מבטיחה את קיומה של הקבוצה הנדרשת בהוכחה.
אקסיומת האינסוף קובעת את קיומה של קבוצה אינסופית, ולכן המסקנה ממשפט קנטור כי יש אינסוף עוצמות אינסופיות שונות, אף היא תקפה.
הפרדוקסים אינם מופיעים ב-ZF, כי במערכת זו אוסף כל הקבוצות ואוספים דומים לו אינם קבוצות.
בגישות חלופיות לתורת הקבוצות משפט קנטור עשוי שלא להיות תקף.
בתורות טיפוסים שונות להוכחת משפט קנטור אין משמעות, כי לא ניתן להשוות בין ל- שלהן טיפוסים שונים.
כדי להתגבר על כך מגדירים קבוצה שיש לה טיפוס זהה ל-, ולגביה אכן מתקיים בהתאם למשפט קנטור.
לאור העובדה שבתורת הטיפוסים קיימת קבוצת כל הקבוצות , נשאלת השאלה כיצד בתורה זו נמנעים הפרדוקסים של קנטור ושל ראסל.
התשובה היא שבתורת הטיפוסים הפונקציה המוגדרת אינה קיימת.
בתורת הטיפוסים, כאשר מתקיים , הקבוצה נקראת "קבוצה קנטורית" ולגביה מתקיים משפט קנטור במובנו הרגיל.
אסכולת הקונסטרוקטיביזם בפילוסופיה של המתמטיקה לא מכירה בקיומם של אובייקטים שלא ניתן לבנות אותם במפורש ובאופן סופי.
בפרט, חברי האסכולה אינם מכירים בקבוצות שאינן בנות מנייה ולכן משפט קנטור לא יכול להיות נכון.
לשיטתם, הוכחת המשפט אינה תקפה משום שהיא נעשית בדרך השלילה, בעוד שהם אינם מכירים בכלל השלישי מן הנמנע.
ב-1922 הציג תוראלף סקולם את פרדוקס סקולם שעוסק בסתירה לכאורה בין משפט קנטור לבין קיום מודל בן מנייה של תורת הקבוצות האקסיומטית, כפי שנובע ממשפט לוונהיים-סקולם.
סקולם הציג גם פתרון לפרדוקס, המראה שסתירה אינה קיימת באמת.
משפט קניג, שהוכח על ידי המתמטיקאי ההונגרי דיולה קניג (נודע גם כיוליוס קניג; 1849-1913) הוא הכללה מרחיקת לכת של משפט קנטור.
המשפט קובע שלכל קבוצה , אם לכל נתונות זוג עוצמות ו-, כך שמתקיים , אז:
אגף שמאל הוא סכום העוצמות , ואילו אגף ימין הוא מכפלת העוצמות .
האי-שוויון טריוויאלי כאשר העוצמות והקבוצה סופיים, אבל כלל אינו ברור מאליו למקרים אינסופיים.
אם למשל תוחלף המכפלה באגף ימין בסכום, עשוי להתקיים שוויון (מה שבוודאי לא נכון במקרה הסופי).
משפט קנטור מתקבל כמקרה פרטי של משפט קניג.
אם לכל בוחרים ו-, אז ממשפט קניג נקבל:
משפט קניג מניח את אקסיומת הבחירה, ולמעשה שקול לה.
מגדירים את הקופינליות של עוצמה בתור העוצמה הקטנה ביותר שמקיימת את התנאי הבא: לכל קיימת עוצמה כך שמתקיים: .
מסמנים את הקופינליות של בסימון .
נשים לב שתמיד ניתן לבחור , ואז .
ממשפט קניג נובע מיד ש- (בוחרים את ממשפט קניג להיות מהגדרת הקופינליות).
מהזהות האחרונה נקבל שלכל קבוצה אינסופית מתקיים .
אז לפי הזהות האחרונה נקבל את הסתירה:
קיבלנו שלקבוצות אינסופיות מתקיים האי-שוויון החזק .
זהו אי-שוויון חזק יותר מאשר משפט קנטור משום ש-, וייתכנו מקרים בהם .
תוצאות אנלוגיות למשפט קנטור מראות אי קיום איזומורפיזם בין מבנים מסוימים לבין מבנים המורכבים מתת-מבנים שלהם (למשל קבוצות סדורות).
משפט קנטור מתקבל לעיתים כמקרה פרטי של משפטים כאלה, כאשר נבחר מבנה טריוויאלי, כך שאוסף התת-מבנים הוא קבוצת החזקה וכל פונקציה חד-חד-ערכית ועל היא איזומורפיזם.
ראשיתה של תורת הקבוצות בתגליות של גאורג קנטור מראשית שנות השבעים של המאה ה-19, בעת שעסק במחקר בתחום האנליזה המתמטית.
ב-1874 הוכיח קנטור לראשונה שישנה יותר מעוצמה אינסופית אחת בכך שהראה שאין פונקציה חד-חד-ערכית ועל בין קבוצת המספרים הממשיים לקבוצת המספרים הטבעיים.
כיוון שחקר האינסוף לא נחשב עיסוק מתמטי באותם ימים, קנטור התייחס לתגליתו בעיקר כהוכחה לכך שמרבית המספרים הממשיים הם טרנסצנדנטיים (שכן המספרים האלגבריים הם בני מנייה).
בשנים שלאחר מכן פרסם קנטור סדרת מאמרים שהרחיבה את התורה.
ב-1891 פרסם קנטור מאמר בגרמנית בשם "Über eine elementare Frage der Mannigfaltigkeitslehre" ("על שאלה אלמנטרית בתורת הקבוצות").
במאמר מופיע האלכסון של קנטור, ומיד לאחריו כתב קנטור:
בהמשך המאמר, פונה קנטור להוכחת המשפט.
ההוכחה המקורית של קנטור זהה במהותה לנוסח המודרני של ההוכחה, אך היא נוסחה בצורה שונה במעט.
במקור קנטור הראה שאין התאמה חד-חד-ערכית ועל בין לבין קבוצת הפונקציות המציינות של (כאמור, נוסח זה שקול לנוסח על קבוצת החזקה).
קנטור טען שאילו הייתה התאמה כזו, הרי שהייתה קיימת פונקציה דו-מקומית , כך שלכל פונקציה מציינת שהותאם לה האיבר מתקיים: .
כעת קנטור בונה פונקציה מציינת שמוגדרת כהיפך מ- (ניתן להגדיר כך: ).
לפי ההנחה קיים כך ש-, ולכן מקבלים סתירה: .
לנוסח המודרני של ההוכחה אחראי ארנסט צרמלו.
משפט קנטור והוכחתו מופיעים במאמר של צרמלו משנת 1908 שבו ייסד את תורת הקבוצות האקסיומטית.
צרמלו הוא גם זה שקרא למשפט על שמו של קנטור.
משפט קנטור-שרדר-ברנשטיין בתורת הקבוצות אומר שאם קיימת פונקציה חד-חד-ערכית מקבוצה לקבוצה , וקיימת פונקציה חד-חד-ערכית מהקבוצה לקבוצה , אז קיימת פונקציה שהיא גם חד-חד-ערכית וגם על מהקבוצה לקבוצה , כלומר שתי הקבוצות שקולות – עוצמתן זהה.
המשפט נקרא על שם גאורג קנטור, ארנסט שרדר ופליקס ברנשטיין.
בכתיב עוצמות ניתן לנסח את המשפט כך: אם וגם אז .
המשפט מכונה גם "למת הסנדוויץ'" (משום שהוא מסיק מאי-השוויונות את שוויון העוצמות).
חשיבותו הרבה של המשפט היא בכך שהוא מראה שהיחס " אם יש פונקציה חד-חד-ערכית מ- ל-" הוא יחס יחס אנטי-סימטרי.
ברור שהיחס הזה טרנזיטיבי, ואם כך הוא מהווה יחס סדר חלש.
כדי להוכיח שהיחס הוא יחס סדר מלא, כלומר שלכל שתי עוצמות מתקיים או , דרושה אקסיומת הבחירה.
נניח ש- היא פונקציה חד-חד-ערכית מ- ל-, וש- היא פונקציה חד-חד-ערכית מ- ל-.
נציג כמה הוכחות של המשפט, המבוססות כולן, בדרכים שונות, על חלוקה של אחת הקבוצות לשני חלקים ושימוש ב- עבור אחד מהחלקים וב- עבור השני כדי להגדיר את הבייקציה בין הקבוצות.
הוכחה באמצעות סיווג של האיברים
נוכיח את המשפט על ידי בניית פונקציה חד-חד-ערכית ועל מ־ ל־.
נניח, ללא הגבלת הכלליות שהקבוצות ו- זרות.
נראה שקיימת התאמה חד-חד-ערכית ועל בין שתי הקבוצות.
נבנה עבור כל איבר של הקבוצה , וכל איבר של הקבוצה , סדרת איברים מ- ומ- לסירוגין, כך שכל איבר מתקבל על ידי החלת הפונקציה החד-חד-ערכית המתאימה על האיבר שקודם לו:
נשים לב שניתן להמשיך את הסדרה ימינה ללא סוף, אך מאחר ש- ו- לא מוגדרות לכל איברי ו- בהתאמה, לא בהכרח ניתן להמשיך את הסדרה שמאלה עד אינסוף.
הסדרות יכולות להסתיים משמאל באיבר של , להסתיים משמאל באיבר של , או להיות אינסופיות (או מעגליות) לשני הכיוונים.
נסווג את הסדרות כסדרות קצה-, סדרות קצה- או סדרות ללא קצה בהתאמה.
מכיוון ש- ו- הן פונקציות חד-חד-ערכיות, לכל איבר בכל אחת מהקבוצות קיימת רק סדרה אחת כזו עד כדי זהות: אם איבר מופיע בשתי סדרות, כל האיברים מימינו ומשמאלו חייבים להיות זהים בשתיהן.
הסדרות יוצרות חלוקה של האיחוד של ו-.
לכן מספיק לבנות פונקציה חד-חד-ערכית ועל מ- ל- בכל אחת מהסדרות בנפרד.
כעת, נבנה את הפונקציה החד-חד-ערכית ועל מ- ל-: עבור איברי ששייכים לסדרת קצה-, נגדיר את כ- (כלומר, נלך צעד אחד ימינה בסדרה המתאימה לאיבר).
עבור איברי ששייכים לסדרת קצה-, נגדיר את כ- (כלומר, נלך צעד אחד שמאלה בסדרה המתאימה לאיבר), ובאותו אופן נגדיר גם את עבור איברי ששייכים לסדרה ללא קצה.
קל לראות שהפונקציה היא אכן חד-חד-ערכית ועל.
נחליף את הקבוצה בתמונה שלה , שהיא ממילא שוות עוצמה ל- משום ש- חד-חד-ערכית.
כעת אפשר להניח ש- ונתונה פונקציה חד-חד-ערכית ; עלינו לבנות פונקציה כזו שהיא חד-חד-ערכית ועל.
נסמן ב- את ההרכבה של על עצמה פעמים (כאשר היא פונקציית הזהות).
נאמר שאיבר הוא מסוג ראשון אם קיימים ו- כך ש-, ומסוג שני אחרת.
נגדיר פונקציה באופן הבא: אם מסוג ראשון, ו- אחרת.
כעת נוכיח כמה טענות קלות:
אכן, כל איבר של הוא מסוג ראשון, ולכן .
אם שניהם מסוג ראשון הם שווים כי חד-חד-ערכית; ואם שניהם מסוג שני הם שווים לפי ההנחה.
נניח, אם כך, ש- מסוג ראשון ו- מסוג שני.
מכיוון ש- מסוג ראשון אפשר לכתוב עבור , ומכיוון ש- מסוג שני, , כלומר גם מסוג ראשון, בסתירה להנחה שהאברים מסוגים שונים.
על: אם הוא מסוג שני, אז הוא שווה לתמונת של עצמו; ואם הוא מסוג ראשון אז ובהכרח , ולכן גם הוא מסוג ראשון, ואז , כך ש- בתמונת בכל מקרה.
הוכחה באמצעות למת נקודת השבת
מסמנים ב- את קבוצת החזקה של .
למה: תהי פונקציה שומרת הכלה (כלומר, אם אז ).
אז יש לה נקודת שבת (כלומר קבוצה כך ש-).
ברור שהפונקציה הזו שומרת הכלה, ולפי הלמה יש לה נקודת שבת, שנסמן ב-.
מכיוון ש-, קיבלנו ש-, ולכן .
נחשב את (כלומר עוצמת קבוצת הפונקציות מהטבעיים לעצמם, שמסומנת גם ):
ראשית נשים לב שמתקיים כי כל פונקציה מהטבעיים לקבוצה היא בפרט פונקציה מהטבעיים לטבעיים, וכל פונקציה מהטבעיים לטבעיים היא בפרט פונקציה מהטבעיים לממשיים.
פונקציית הזהות היא תמיד חד-חד-ערכית, ולכן אם קבוצה מוכלת בקבוצה אחרת אז עוצמתה לא גדולה ממנה.
לפי ההגדרה המוכללת לחזקה, האי שוויון הנ"ל שקול ל:
(כאשר היא אָלֶף אֶפֶס ו- היא עוצמת הרצף)
אבל מתקיים וכמו כן, על פי חוקי החזקות: (להוכחת השוויון , ראו כאן)
לכן , ועל פי משפט קנטור-שרדר ברנשטיין נקבל , משמע קיבלנו .
בחשבון אינפיניטסימלי, משפט קנטור (הידוע גם כמשפט קנטור-היינה) על רציפות במידה שווה קובע כי פונקציה שהיא רציפה על קטע סגור היא רציפה במידה שווה בו.
המשפט נותר נכון גם אם נחליף את הקטע בכל קבוצה קומפקטית: כל פונקציה רציפה מקבוצה קומפקטית למרחב מטרי, היא רציפה במידה שווה.
נציג כאן הוכחה המתבססת על ההגדרה של היינה לרציפות: פונקציה היא רציפה בנקודה אם ורק אם עבור כל סדרה השואפת לנקודה זו, מתקיים .
כלומר, ערכי תמונות איברי הסדרה שואפים לתמונת גבול הסדרה.
תהא כעת פונקציה רציפה בקטע הסגור .
נניח בשלילה כי היא אינה רציפה במידה שווה בקטע זה, אז קיים כך שעבור כל קיימות שתי נקודות כך שמתקיים , אבל .
כל אברי הסדרה שייכים לקטע , כלומר זוהי סדרה חסומה.
על פי משפט בולצאנו ויירשטראס, כל סדרה חסומה מכילה תת-סדרה המתכנסת לגבול סופי.
מסגירות הקטע נובע שגבול הסדרה נמצא בתוכו, כלומר .
כעת נוכיח כי - כלומר, אם אנו לוקחים מהסדרה השנייה תת-סדרה שלאיבריה אותם האינדקסים כמו לתת הסדרה הראשונה, גם היא תתכנס לאותו גבול.
כיוון ש- נובע כי , כלומר סדרת ההפרשים שואפת לאפס ומאריתמטיקה של גבולות נובע כי
על פי רציפות , מתקיים: .
מאריתמטיקה של גבולות נקבל , וזו סתירה לכך שמתקיים לכל אברי הסדרות.
לכן ההנחה שהפונקציה אינה רציפה במידה שווה איננה נכונה, וההוכחה הושלמה.
משפט קוק-לוין הוא משפט יסודי בתורת הסיבוכיות, הקובע שהבעיה SAT היא NP-שלמה.
את המשפט הוכיחו, באופן בלתי תלוי, סטפן קוק בשנת 1971, ולאוניד לוין בשנת 1973.
במדעי המחשב התאורטיים יש חשיבות מרכזית לבעיות שניתן למצוא להן פתרון בזמן סביר (הגדרתו המדויקת של המושג "זמן סביר" היא טכנית, ומסתמכת על הגדרת המושג של מכונת טיורינג).
אוסף הבעיות שניתן למצוא להן פתרון בזמן סביר מסומן על ידי האות P.
בנוסף לבעיות שניתן למצוא עבורן פתרון בזמן סביר, קיימות גם בעיות שניתן לבדוק בזמן סביר האם פתרון מוצע כלשהו עבורן הוא אכן פתרון לבעיה.
בעיות אלו מסומנות על ידי NP.
זהו אוסף בעיות שככל הנראה גדול יותר מאוסף הבעיות P, שכן קיימות בעיות רבות שידוע כיצד לבדוק בזמן סביר אם פתרון מוצע אכן פותר אותן, אך לא ידועה דרך למצוא פתרון שכזה בזמן סביר.
דוגמה לבעיה מסוג זה היא השאלה האם ניתן לחלק קבוצת מספרים נתונה לשתי קבוצות, כך שסכום המספרים בקבוצה האחת יהיה שווה לסכומם בקבוצה השנייה.
בהינתן חלוקה של קבוצת מספרים לשתי קבוצות, קל לבדוק האם הסכומים בשתיהן אכן שווים.
אבל אם לא נתונה חלוקה כזו, קשה מאוד למצוא האם היא אכן קיימת.
כיום עדיין לא ידוע האם עבור כל בעיה שניתן לבדוק פתרון מוצע לה בזמן סביר, ניתן גם למצוא פתרון שכזה בזמן סביר.
השאלה האם הדבר אפשרי מכונה בשם בעיית P=NP, כלומר האם שתי המחלקות P ו-NP שוות זו לזו, וזוהי אחת מהשאלות המרכזיות במדעי המחשב.
הדעה הרווחת היא כי הדבר אינו נכון.
משפט קוק-לוין עוסק באחת מהבעיות הנמצאות ב-NP, ונקראת בעיית SAT (הגדרתה המדויקת של בעיה זו קשורה ללוגיקה מתמטית ואף כי אינה מסובכת היא טכנית למדי).
המשפט אומר כי SAT שייכת לאוסף הבעיות הקשות ביותר שב-NP, במובן זה שאם תתגלה דרך למצוא פתרון בזמן סביר עבור SAT, ניתן יהיה לפתור בזמן סביר כל בעיה השייכת ל-NP.
במילים אחרות, אם יתגלה פתרון בזמן סביר עבור SAT, הדבר יהווה הוכחה לכך ש-P=NP.
בעיות שניחנות בתכונת קושי שכזו מכונות NP-שלמות.
לכן, בניסוח מדויק יותר, משפט קוק-לוין אומר כי SAT היא בעיה NP-שלמה.
חשיבותו של משפט קוק-לוין אינה רק בתכונה של SAT שעולה ממנו, אלא גם בכך שהוא מאפשר להוכיח בקלות עבור בעיות רבות נוספות שגם הן NP-שלמות.
קוק הגדיר את המושג של בעיה NP-שלמה כבעיה המקיימת שני תנאים:
הבעיה שייכת למחלקת הסיבוכיות NP.
כל בעיה אחרת שהיא במחלקת הסיבוכיות NP, ניתנת לרדוקציה פולינומית אליה.
בצורה פורמלית ניתן להסתכל על בעיות הכרעה כבעיות של זיהוי שפה פורמלית.
כך ניתן לנסח את בעיית SAT בתור הבעיה של זיהוי השפה הבאה: שפת כל הפסוקים הלוגיים בצורת CNF (כלומר בצורה קנונית קוניוקטיבית), שישנה השמה המספקת אותם.
בלוגיקה מתמטית, פסוק של תחשיב פסוקים נחשב בעל השמה מספקת אם ישנה הצבה כלשהי של ערכי אמת במשתנים שלו, כך שהפסוק מקבל ערך אמת.
משפט קוק אומר כי בעיית זיהוי שפה זו היא NP-שלמה.
משמעות המשפט היא שאם ניתן לפתור את SAT בזמן ריצה פולינומי (כלומר באופן יעיל), אז ניתן להכריע את כל הבעיות שבמחלקת הסיבוכיות NP בזמן פולינומי, דבר שיגרור את השוויון P=NP.
ההוכחה פתחה פתח להוכחה מיידית כי עשרות בעיות אחרות הן NP-שלמות (בפרט מפורסם המאמר על 21 הבעיות ה-NP שלמות של קארפ מאת ריצ'רד קארפ שפורסם שנה אחרי משפט קוק).
על עבודתו זכה קוק בפרס טיורינג.
עד היום, לא נמצא אף אלגוריתם פולינומי לאף אחת מהשפות הנ"ל, והשאלה האם P=NP נותרה אחת השאלות הפתוחות העמוקות במדעי המחשב.
SAT (כשפה הפורמלית הכוללת את כל הנוסחאות הספיקות) שייכת ל-NP;
יש רדוקציה פולינומית מכל בעיית NP ל-SAT.
כדי להוכיח כי , עלינו לתאר מכונת טיורינג אי דטרמיניסטית המכריעה את בזמן פולינומי באורך הקלט.
תהי מכונת טיורינג אי דטרמיניסטית המקבלת קלט , אזי:
נחש השמה עבור המשתנים .
בדוק אם ההשמה עבור המשתנים שנמצאים בפסוקית אכן מספקים אותה.
אם כן, החזר " ספיקה".
בהינתן קלט עם משתנים ו- פסוקיות:
שלב 1 ייקח זמן ריצה של שכן המכונה מנחשת השמה או לכל ה- משתנים.
שלב 2 ייקח זמן ריצה של לכל היותר, שכן יש לנו פסוקיות ו- ליטרלים לכל היותר בכל פסוקית.
לכן זמן ריצת המכונה הוא לכל היותר , שזהו זמן ריצה פולינומי בגודל הקלט.
משפט צרמלו הוא משפט בתורת המשחקים, הקובע כי בכל משחק של שני שחקנים המשחקים בתורות לסירוגין, בו מספר תורים סופי, שהוא בעל ידיעה שלמה, שאין בו מרכיב של מזל ושלא תיתכן בו תוצאת תיקו, קיימת אסטרטגיה המבטיחה לאחד השחקנים ניצחון.
כלומר, בתנאים אלו לאחד השחקנים יש מעין "ספר הוראות" שהעוקב אחריו בקפדנות יכול להימנע בוודאות מהפסד.
ניתן להכליל את המשפט גם עבור משחקים בהם קיימת תוצאת תיקו (דוגמת איקס עיגול) ולהראות שתמיד תיתכן אחת משלוש אפשרויות:
קיימת אסטרטגיה המבטיחה ניצחון לשחקן הראשון
קיימת אסטרטגיה המבטיחה ניצחון לשחקן השני
כל צד יכול לפחות לכפות תיקו (כלומר יכול להבטיח שהמשחק יסתיים בתיקו או בניצחונו).
המשפט אינו קובע איזו אפשרות נכונה, אלא רק שאחת מהן חייבת להתקיים.
הוכיח את המשפט המתמטיקאי הגרמני ארנסט צרמלו ב-1913, כ-15 שנה לפני פרסום מאמרו של ג'ון פון נוימן על משפט המינימקס בשנת 1928. משפט המינימקס, העוסק בקיומן של אסטרטגיות אופטימליות מעורבות, נחשב למשפט הראשון בתורת המשחקים.
הוכחת המשפט מתבססת על הצגת המשחק כעץ הקרוי עץ משחק.
עץ משחק הוא גרף מכוון בו כל צומת מייצג מצב אפשרי במשחק.
מצב במשחק כולל את כל המידע ההכרחי כדי להמשיך את המשחק מאותה נקודה.
לדוגמה, עבור משחק השחמט צומת מייצג את מיקום הכלים על הלוח, תורו של מי לשחק, מידע לגבי האפשרות להצריח ולהכות דרך הילוכו וכיוצא בזה.
מכל צומת יוצאות קשתות מכוונות (חצים) לצמתים המייצגים מצבים אליהם ניתן להגיע מהמצב הנוכחי באמצעות מהלך אחד, שנקראים גם "בנים" של הצומת.
השורש של העץ הוא המצב ההתחלתי של המשחק, הבנים הישירים של השורש הם המצבים האפשריים אחרי מהלך אחד וכן הלאה.
העלים בעץ מייצגים את המצבים בהם המשחק נגמר.
מכיוון שנתון כי המשחק סופי, יש לו עץ משחק סופי.
נצבע את העלים בעץ באופן הבא: כל עלה המייצג ניצחון של השחקן הראשון (נניח כחול) ייצבע בכחול, כל עלה המייצג ניצחון של השחקן השני (אדום) ייצבע באדום, כל עלה המייצג מצב תיקו ייצבע באפור.
כעת נצבע את שאר הצמתים בעץ באופן רקורסיבי: אם צומת מייצג מצב בו תורו של השחקן הכחול, הצומת ייצבע בכחול אם יש לו בן כחול (כלומר אם הכחול יכול לעבור למצב אחר הצבוע הכחול).
אם אין בן כחול, אבל יש בן אפור, הצומת ייצבע באפור.
ואם כל הבנים אדומים הצומת ייצבע באדום.
בדומה, צומת המייצג מצב בו תור האדום לשחק יצבע באדום אם יש לו בן אדום, אחרת - באפור אם יש לו בן אפור, ואם כל הבנים כחולים הוא יצבע כחול.
באופן הזה נצבעים כל הצמתים בעץ מלמטה למעלה (מהעלים לשורש).
בפרט השורש נצבע בכחול, אפור או אדום.
נשים לב שברגע שמגיע תורו של אחד השחקנים והמצב הנוכחי צבוע בצבע שלו, הוא יכול להבטיח ניצחון (נקרא לשחקן הזה השחקן הכופה).
זאת משום שלפי חוקי הצביעה, בהכרח יש מהלך שיביא אותו לצומת אחר הצבוע בצבע שלו.
כעת תורו של השחקן הנכפה, ומכיוון שהוא בצבע הנגדי לו, כל מהלך שהוא יבצע יביא אותו לצומת בצבע של השחקן הכופה.
ושוב יבחר השחקן הכופה את צבעו שלו וחוזר חלילה.
לאחר מספר סופי של צעדים יגיע המשחק לעלה הצבוע בצבע של השחקן הכופה והוא יוכרז כמנצח.
לפי הניתוח האחרון, ייתכנו שלוש אפשרויות התלויות בצבע של השורש של העץ:
אם השורש נצבע בכחול, הכחול יכול להבטיח ניצחון.
זאת משום שבשורש המשחק זהו תורו של הכחול בצומת הצבוע בצבע שלו, ולכן הוא יכול לכפות ניצחון.
אם השורש נצבע באדום, האדום יכול להבטיח ניצחון.
זאת משום שהכחול המשחק ראשון מתחיל בצומת אדום, לכן כל מהלך שלו יביא אותו לאדום.
כעת נמצא האדום בצומת אדום ולכן יכול לכפות ניצחון.
אם השורש נצבע באפור, כל שחקן יכול להימנע בוודאות מהפסד.
כאשר תורו של אחד השחקנים (הכופה) בצומת אפור, הוא יכול לעבור לצומת אחר בצבע אפור.
יריבו (הנכפה) יוכל לעבור משם רק לצומת בצבע מנוגד לו (מה שיאפשר ניצחון לכופה) או לצומת אפור אחר.
הכופה ימשיך לעבור לצמתים אפורים ובכך יבטיח שהמשחק יסתיים בתיקו (או בניצחון שלו, במקרה והנכפה טועה).
אם השורש אפור, הכחול מתחיל באפור ולכן יכול להימנע מהפסד.
גם האדום יכול להימנע מהפסד, זאת משום שאחרי המהלך הראשון של הכחול, האדום משחק בצומת אפור או בצומת אדום.
ההוכחה האחרונה מספקת גם אלגוריתם המאפשר לקבוע לכל משחק העומד בתנאים מהי אסטרטגיית הניצחון (או התיקו) שלו.
האלגוריתם צובע את עץ המשחק ומחפש מסלול חד-צבעי מהשורש לאחד העלים.
בפועל, האלגוריתם ישים במשחקים פשוטים כגון איקס עיגול, אולם במשחקים מורכבים כמו שחמט, עץ המשחק הוא הרבה יותר גדול ממה שמחשב בן-ימינו מסוגל להכיל (מעריכים שמספר העלים בעץ המשחק של שחמט הוא לפחות 10123, הרבה יותר ממספר החלקיקים ביקום).
משפט צרמלו נשען על כמה תכונות מופשטות של המשחק:
משחק של שני שחקנים, המשחקים איש-איש בתורו
אין מידע מוסתר, כלומר לשני השחקנים ידיעה שלמה של מצב המשחק
במשחק אין אלמנט של מזל
המשחק סופי (אינו יכול להמשך עד לאינסוף)
להן דוגמאות אחדות למשחקים שעומדים בתנאי הסף של המשפט ועל כן הוא חל עליהם:
ארבע בשורה - האפשרות הראשונה נכונה - קיימת אסטרטגיה המבטיחה ניצחון לשחקן הראשון.
רברסי על לוח של 6x6 - האפשרות השנייה נכונה - קיימת אסטרטגיה המבטיחה ניצחון לשחקן השני.
איקס עיגול - האפשרות הנכונה עבורו היא השלישית - כל צד יכול לכפות תיקו.
דמקה אנגלית - האפשרות הנכונה עבורו היא השלישית - כל צד יכול לכפות תיקו.
שחמט - לא ידוע - איננו משחק פתור, טרם נמצאה הוכחה איזו משלוש האפשרויות היא הנכונה.
להן דוגמאות אחדות למשחקים של שני שחקנים שאינם עומדים בתנאי הסף של המשפט ועל כן לא חל עליהם:
סטרטגו - מכיל מידע מוסתר, לכן אין בו ידיעה שלמה.
שש בש - מכיל אלמנט של מזל.
ספיד - השחקנים לא משחקים לפי תור
בתורת החבורות, אחד המאפיינים של חבורות סופיות הוא העובדה המפתיעה שאפשר להסיק רבות על המבנה של חבורה מתוך הסדר שלה.
אחת הדוגמאות המוקדמות לתופעה הזו היא משפט קושי (שגילה אוגוסטן לואי קושי ב-1845): אם חבורה סופית, אזי לכל מספר ראשוני המחלק את סדר החבורה קיים ב- איבר מסדר .
תוצאה כללית יותר, העוסקת בקיום של תת-חבורות מכל סדר שהוא חזקה של מספר ראשוני, מנוסחת במשפטי סילו.
למשפט יסודי זה שימוש נרחב בתורת החבורות, ודרכה גם בתחומים אחרים באלגברה, בפרט בתורת גלואה.
לדוגמה, אם הוא פולינום אי פריק ממעלה מעל שדה , אז שדה ההרחבה הוא מממד , ולכן גם הממד של שדה הפיצול של , המכיל את השדה הראשון, מתחלק ב-.
אבל לפי המשפט היסודי של תורת גלואה, הסדר של חבורת גלואה שווה לממד של מעל , ולכן – לפי משפט קושי – היא כוללת איבר מסדר .
תהי חבורה מסדר המתחלק בראשוני .
יש להוכיח שקיים ב- איבר מסדר .
ראשית יש להוכיח את המשפט לחבורות אבליות, למשל באינדוקציה על הסדר: אם הוא איבר מסדר המתחלק ב-, אז יש לו חזקה מסדר .
אחרת, אפשר לעבור לחבורת מנה ביחס לתת-החבורה הציקלית הנוצרת על ידי .
כעת נוכיח את המשפט במקרה הכללי (שוב באינדוקציה על הסדר).
אם אז כל איבר לא-טריוויאלי הוא מסדר (לפי משפט לגראנז').
נניח שהטענה נכונה לכל החבורות מסדר קטן מ-.
מקרה א – קיים איבר עבורו .
כי ולכן קיים לפחות איבר אחד בחבורה שאינו ב- לכן , הנחנו , ולפי הנחת האינדוקציה קיים איבר מסדר ב-, אבל זו תת-חבורה של .
מקרה ב – לכל איבר , לא מחלק את .
לפי משפט לגראנז' ומשני הנתונים נובע כי .
לפי משוואת המחלקות כאשר נציגי מחלקות הצמידות שסדרן גדול מ-1, כמובן כי גודל מחלקת הצמידות של איבר במרכז הוא 1. הנחנו , הראינו לפי משוואת המחלקות .
חבורה אבלית לכן לפי המקרה האבלי שהוכחנו בהתחלה, קיים בה איבר מסדר וסיימנו.
נסתכל על קבוצת ה--יות של איברים שמכפלתם היא היחידה:
מכיוון שלכל יש השלמה יחידה לווקטור ב-, גודל הקבוצה הוא , המתחלק ב-.
אנו רוצים להוכיח קיום של איבר בקבוצה מהצורה כאשר .
על ידי הצמדה ב-, קל לראות כי אם ורק אם .
לכן נוח לחשוב על כל וקטור כמעגל של מספרים, המסודרים כמו על חוגה של טלפון ישן, ולחלק את למחלקות שקילות, כך ששני איברים ייקראו שקולים אם הם סיבוב אחד של השני.
ה"עוקץ" בהוכחה נעוץ בכך שאורך כל וקטור הוא ראשוני.
לכן, גודל כל מחלקת שקילות חייב להיות או 1. ניתן להבין זאת מכך שאם וקטור שווה לסיבוב של צעדים של עצמו, אז הוא בהכרח שווה גם לסיבוב של צעדים, צעדים, וכך הלאה.
אך מכיוון ש- ראשוני, ניתן להגיע לסיבוב בכל מספר של שלבים על ידי סיבוב חוזר ב- צעדים.
זאת מכיוון שלכל קיים עבורו (טענה זו שקולה לטענה שכל איבר בחבורה הציקלית יוצר אותה).
לכן, אם קיים סיבוב של הווקטור שבו הוא חוזר לעצמו, אז בכל סיבוב הוא יחזור לעצמו, והוא מהצורה .
נשים לב כי היא איחוד זר של מחלקות השקילות שלה, ולכן גודלה הוא סכום גודלי מחלקות השקילות, שגודל כל אחת מהן הוא 1 או .
נזכור גם ש- מחלק את גודל ושאנו יודעים כי קיימת מחלקת שקילות בגודל 1 - המחלקה .
אך אם גודל כל מחלקות השקילות האחרות היה , אז לא יכול היה לחלק את , כי סכום של מספרים המתחלקים ב- ועוד 1 לא יכול להתחלק ב-.
לכן, קיבלנו כי חייבת להיות לפחות עוד מחלקה בגודל 1 (למעשה חייבות להיות עוד כאלה), כלומר מחלקות מהצורה , ולכן קיים עבורו .
בתורת החבורות, משפט קיילי קובע שכל חבורה איזומורפית לתת-חבורה של חבורה סימטרית כלשהי, וכך מציג את החבורה כחבורת תמורות.
המשפט בפרט מראה שאפשר להבין את כל החבורות הסופיות באמצעות טיפול אחיד בתמורות, והוא נחשב לאחד מ"משפטי ההצגה" הקלאסיים: כל עצם מופשט (חבורה) הוא למעשה אובייקט קונקרטי ומוכר.
בעבודתו של אווריסט גלואה (בסביבות 1830), החבורה נתפסת כקבוצה קונקרטית של תמורות.
ב-1854 כתב המתמטיקאי ארתור קיילי שני מאמרים קצרים על מושג החבורה.
במאמר הראשון הוא מגדיר חבורה (סופית) על-פי האסוציאטיביות וההפיכות של כל האיברים, כלומר, כאובייקט מופשט.
קיילי מציג את הדוגמאות שלו דרך לוח כפל, ומעיר שכל איבר הוא למעשה תמורה על אברי החבורה.
בכך הוא רומז שכל חבורה (במובן המודרני, האקסיומטי, של המושג) היא למעשה חבורה של תמורות, אף על פי שאינו מוכיח את המשפט במפורש.
אכן, ויליאם ברנסייד (בספרו מ-1911) מייחס את המשפט לקאמי ז'ורדן, שסיפק לו הוכחה מפורשת ב-1870.
לפי משפט קיילי, אפשר לשכן חבורה מסדר כתת-חבורה של החבורה הסימטרית .
ההוכחה מבוססת על פעולה נאמנה הנקראת "הפעולה הרגולרית של החבורה על עצמה" .
למשפט יש הכללה חשובה, הידועה בשם העידון של משפט קיילי: אם ל- יש תת-חבורה מאינדקס , אז יש העתקה שהגרעין שלה הוא הליבה של : חיתוך תת-החבורות של הצמודות ל-, כלומר .
הוכחת העידון מתקבלת מניתוח הפעולה של על אוסף המחלקות על ידי כפל משמאל: .
מסקנה מיידית ממשפט העידון של קיילי הוא שלחבורה עם תת-חבורה מאינדקס מוכרחה להיות תת-חבורה נורמלית מאינדקס המחלק את .
אכן, לפי משפט האיזומורפיזם הראשון נקבל כי , ולכן .
בפרט, חבורה פשוטה לא-אבלית המכילה תת-חבורה מאינדקס משוכנת ב- ולכן הסדר שלה מחלק את .
תהא חבורה סופית מסדר .
ראשית, עבור נגדיר פונקציה כאשר לכל .
הפונקציה חד-חד-ערכית: אם אזי .
הפונקציה על: לכל קיים איבר עבורו .
לכן היא תמורה על איברי .
ההעתקה היא שיכון של G לתוך חבורת התמורות של G.
נבחר את החבורה ונשכן אותה ב-, כלומר נמצא תת-חבורה של שאיזומורפית ל-.
התמורות שהגדרנו אינן מקריות, בנינו אותן כך שהתמורה מעבירה את המספר ל- (הסכום בחבורה , כלומר מודולו 4).
המשפט הקאנוני הוא שיטת משפט שפותחה בידי הכנסייה הקתולית וכנסיות אחרות.
המשפט הקאנוני אומץ באופן נרחב באירופה בימי הביניים, כתחליף לשיטות המשפט היווני והרומי.
המשפט הקאנוני נתפס כעדכון של חוקי הקורפוס יוריס קיוויליס, שנוסחו בידי יוסטיניאנוס הראשון, קיסר האימפריה הביזנטית במאה השישית.
השפעתו ניכרת עד היום בחוקיהן המודרניים של ארצות אירופה רבות, בהן צרפת, איטליה וגרמניה.
המשפט הקאנוני הוא החוק הכנסייתי של הכנסייה הקתולית.
הוא פותח על ידי הכנסייה הקתולית עצמה על מנת לווסת ולשלוט בזכויות ובחובות של חבריה.
כמו שה-civil law היה החוק האזרחי וקושר ישירות לסמכות הקיסר, החוק הקאנוני היה החוק הרוחני וקושר ישירות לסמכות האפיפיור.
לכל אחד מסוגי המשפט היה תחום שונה משלו, ומערכת בתי המשפט הייתה נפרדת: מערכת אזרחית ומערכת קאנונית.
בחלק מתחומי השיפוט הייתה מגמה של חפיפה.
לפני הרפורמציה, היה נהוג שלבתי משפט קאנוניים הייתה סמכות בנושאים אזרחיים, בעיקר בענייני משפחה וירושה, אך גם בסוגים מסוימים של פשעים.
המשפט הקאנוני השפיע על המשפט הרומי שהתקבל באירופה על ידי כך שנאספו כתבים רבים על המשפט הקאנוני, ובעת תחיית ההשכלה באיטליה, שם הייתה האוניברסיטה הראשונה, כבר היה הרבה חומר מסודר ללימודים של המשפט הקאנוני.
לכן למדו אותו באוניברסיטאות באיטליה במקביל ללימוד המשפט האזרחי הרומי, ותעודת הסיום של האוניברסיטאות הייתה דוקטור בשני סוגי המשפט: civil law + canon law, התואר נקרא: juris utriusque doctor = JUD, והוא עדיין מוענק בחלק מהאוניברסיטאות בעולם המשפט האזרחי.
היות שלמדו אותם יחד, הייתה נטייה של סוגי המשפט להשפיע זה על זה, ושניהם יחד עזרו ליצור את המשפט הנוהג והמקובל = ה-jus commune שהתקבל במדינות אירופה.
המשפט הקאנוני השפיע על ה-jus commune בעיקר בתחומים של משפחה וירושה, שהיו גם חלק מהחוק האזרחי הרומי, וכן על המשפט הפלילי.
עד השלב בו נשללה מבתי המשפט הקאנוניים סמכותם לדון במשפט אזרחי, הרבה עקרונות והליכים שלהם אומצו על ידי בתי המשפט האזרחיים.
לשיטת משפט זו הייתה השפעה מסוימת גם על הדין האנגלי, דרך צינור הקליטה שנקרא "דיני היושר", שנקלט על ידי הלורד צ'נסלור והיה מבוסס על כללי צדק טבעיים.
מוסדות לחיים מקודשים הם ארגונים הפועלים לפי המשפט הקאנוני.
משפט קיילי-המילטון הוא משפט באלגברה ליניארית, הקובע שכל מטריצה ריבועית A (מעל שדה) מאפסת את הפולינום האופייני שלה , כלומר, מתקיים .
בפרט, הפולינום המינימלי של מטריצה מחלק את הפולינום האופייני שלה.
המשפט קרוי על שמם של המתמטיקאים ארתור קיילי וויליאם המילטון.
במאמר מ-1858 הראה קיילי שהמשפט נכון עבור מטריצות בגודל , והוא מדווח כי בדק את הטענה גם עבור מטריצות בגודל ; עם זאת, הוא כותב, "לא מצאתי לנכון לטרוח על הוכחה פורמלית של המשפט עבור מטריצה מכל גודל".
מעט אחר-כך, במהלך מחקריו על אלגברת הקווטרניונים, גילה המילטון את המשפט עבור מטריצות בגודל .
ב- 1878 הוכיח פרדיננד גאורג פרובניוס את המקרה הכללי.
המשפט תקף כאשר רכיבי המטריצה שייכים לחוג קומוטטיבי כלשהו, ונובע ממנו שכל חוגי המטריצות הם חוגי זהויות פולינומיות.
ראשית ידוע כי לכל מטריצה מתקיים כי , ולכן עבור מתקיים כי ומכיוון שאיברי המטריצה הם פולינומים ממעלה ראשונה נובע שאיברי הם פולינומים ממעלה קטנה או שווה ל-.
לכן ניתן לכתוב את כפולינום על מקדמים שהם מטריצות, .
מכיוון ש- אז מתקיים כי ו-
לכן על ידי השוואת מקדמים לפולינומים זהים נקבל כי אז אם נכפול ב- נקבל כי ולכן על ידי הצבה בפולינום המציין נקבל טור טלסקופי שמתאפס.
אם מניחים שהמטריצה לכסינה, ההוכחה קלה יותר:
הפעלת המטריצה הריבועית (המטריצה המתקבלת מהצבת המטריצה המקורית A בפולינום האופייני שלה) על כל אחד מהווקטורים העצמיים של A מחזירה את הווקטור העצמי כפול סקלר מסוים (זה נובע מההגדרה של וקטור עצמי).
הסקלר הזה שווה לערך הפולינום האופייני כאשר מציבים בו את הערך העצמי אליו משויך הווקטור העצמי; בכתיב מתמטי:
מהגדרת הפולינום האופייני נובע שכל ערך עצמי של המטריצה המקורית הוא שורש שלו; לפיכך המטריצה שולחת את כל אחד מהווקטורים העצמיים של A לאפס ( לכל i).
מכיוון ש-A לכסינה, אוסף הווקטורים העצמיים שלה, , הוא בסיס למרחב עליו היא פועלת.
מכיוון ששתי מטריצות הפועלות באופן זהה על כל אחד מווקטורי בסיס של מרחב ליניארי הן בהכרח זהות, מקבלים ש- שווה זהותית למטריצת האפס.
נציג הוכחה נוספת המשתמשת בצורת ז'ורדן מעל הסגור האלגברי של שדה הבסיס.
ראשית, נשים לב שאם A,B מטריצות דומות ו-A מאפסת את הפולינום האופייני שלה, כך גם B.
הוכחה: למטריצות דומות אותו פולינום אופייני.
כיוון ש-A,B דומות, קיימת מטריצה D כך ש-.
הנחנו ש-A מאפסת את הפולינום האופייני שלה, כלומר אם הפולינום האופייני הוא אז .
נכפיל ביטוי זה משמאל ב-D-1 ומימין ב-D ונקבל .
לאחר פתיחת סוגריים ושימוש בכך ש- לכל k (קל להוכיח זאת באינדוקציה), מקבלים כרצוי.
לכן, מספיק להוכיח שלכל מטריצה יש מטריצה שדומה לה עבורה משפט קיילי-המילטון מתקיים.
ראשית נניח שהמטריצה A היא בלוק ז'ורדן יחיד, שעל האלכסון שלו הערכים .
אז הפולינום האופייני שלה הוא .
נשים לב ש- היא מטריצה משולשית עם אפסים על האלכסון, לכן העלתה בחזקת n מאפסת אותה.
כעת נניח ש-A מטריצה כללית.
הפולינום האופייני נשמר תחת הרחבת שדות, לכן ניתן להניח שהשדה מעליו מוגדרת המטריצה סגור אלגברית, כלומר קיימת מטריצה B בצורת ז'ורדן שדומה לה.
מהמשפט בתחילת ההוכחה, ניתן להניח ש-A כבר נתונה בצורת ז'ורדן.
הפולינום האופייני הוא מכפלת ביטויים מהצורה כאשר הוא הערך בבלוק ה-i ו- הוא גודל הבלוק.
כמו בפסקה הקודמת, הצבת המטריצה בפולינום האופייני נותנת אפסים בשורות שבהן מופיע הבלוק הזה.
לכן הצבת המטריצה בפולינום האופייני נותנת מכפלת מטריצות שלכל אחת מהן שורות אפסים ושכולן ביחד מכסות את כל השורות - ולכן מכפלתן היא מטריצת האפס כרצוי.
הוכחה באמצעות מודולים מעל חוג פולינומים
כהקדמה להוכחה, נרחיב את המושג כפל מטריצות: יהי חוג ויהי -מודול שמאלי.
עבור שלמים חיוביים , תהיינה ו- מטריצות.
מכפלתן תוגדר לפי הנוסחה .
ההגדרה הסטנדרטית של כפל מטריצות היא מקרה פרטי כאשר כמודול מעל עצמו.
כמו בכפל המטריצות הסטנדרטי, מתקיימת תכונת האסוציאטיביות: עבור שלמים חיוביים ומטריצות , ו- מתקיים כי .
כעת נסמן ב- את השדה הנ"ל.
עבור המרחב הווקטורי עם הבסיס הסטנדרטי , נגדיר על מבנה של מודול מעל חוג הפולינומים באמצעות הנוסחה לכל וקטור ופולינום .
הגדרה זו מרחיבה את המבנה של כמרחב וקטורי מעל .
נשים לב שלכל מתקיים .
לכן, אם נסמן ב- את וקטור העמודה עם רכיבים ב- אז נקבל כי , כאשר היא המטריצה המשוחלפת של .
כעת נשתמש באסוציאטיביות של כפל מטריצות לעיל עם ו- ונקבל:
כלומר, כל עמודה של היא עמודת אפסים.
מכאן ש- היא מטריצת האפס כנדרש.
משפט קזוראטי-ויירשטראס הוא משפט מתמטי מתחום הפונקציות המרוכבות, הנותן מידע בדבר תמונת פונקציה הולומורפית בסביבה של נקודת סינגולריות עיקרית.
המשפט קרוי על שם המתמטיקאי האיטלקי פליצ'ה קזוראטי והמתמטיקאי הגרמני קארל ויירשטראס.
בספרות מתמטית רוסית המשפט קרוי משפט סוחוצקי, על שם המתמטיקאי הרוסי-פולני יוליאן סוחוצקי .
תהי פונקציה הולומורפית בתחום , מלבד נקודת סינגולריות עיקרית אחת .
אזי לכל סביבה של , הקבוצה צפופה במישור המרוכב.
למעשה קובע המשפט כי תנאי זה שקול להיות נקודת סינגולריות עיקרית של .
משפט פיקארד מחזק את המשפט, וקובע שתמונת פונקציה הולומורפית בסביבה נקובה של נקודת סינגולריות עיקרית, היא לא רק צפופה אלא ממש שווה למישור המרוכב כולו פרט אולי לנקודה אחת.
ההוכחה היא על דרך השלילה.
נניח בשלילה, שקיימת סביבה של הנקודה , בה אנליטית פרט לנקודת סינגולריות עיקרית , ו- לא צפופה במישור המרוכב.
כידוע, קבוצה היא צפופה במרחב אם ורק אם היא פוגשת כל קבוצה פתוחה.
לכן, קיימים ו-, כך ש- (כאשר הוא כדור פתוח ברדיוס סביב הנקודה ).
לכן, לכל , מתקיים , לכן .
לכן, בקבוצה מוגדרת הפונקציה .
מהגדרתה, הפונקציה אנליטית באופן מיידי בכל פרט אולי ל-.
באשר ל-, הפונקציה חסומה סביבה: , לכן נקודה סינגולרית סליקה של .
נפריד למקרים - אם , אז מכך ש- נקבל .
אחרת, אם נקבל כי .
שני המקרים מובילים לסתירה, שכן גבול הפונקציה בנקודה סינגולרית עיקרית לא קיים כלל.
ניתן לוודא על ידי פתרון ישיר, כי תמונת הפונקציה היא .
תוצאה זו צפויה ממשפט פיקארד, שכן לא ייתכן שהנקודה 0 תתקבל, ולכן כל שאר הנקודות חייבות להתקבל.
בפרט, התמונה ודאי צפופה ב-.
בתחום המתמטי של תורת הגרפים משפט קירכהוף או משפט מטריצת העץ של קירכהוף, הנקרא על שם הפיזיקאי הגרמני גוסטב קירכהוף, מספק את מספר העצים הפורשים בגרף.
המשפט הוא הכללה לנוסחת קיילי הקובעת כי מספר העצים הפורשים בגרף שלם בעל n צמתים הוא .
עבור גרף בעל קודקודים הלפלסיאן של הוא המטריצה המתקבלת מההפרש בין מטריצת הדרגות (מטריצה אלכסונית בה דרגות הצמתים מופיעות על האלכסון) למטריצת השכנויות של .
הערכים העצמיים של מטריצה זו מקיימים: (הווקטור העצמי המתאים לו הוא ) ולכל ,
מספר הפעמים שהערך 0 מופיע כערך עצמי הוא כמספר רכיבי הקשירות של , ולכן אם הגרף קשיר אז חיוביים ממש.
יהא גרף קשיר בעל קודקודים, ויהיו ערכים עצמיים שונים מאפס של הלאפלסיאן של .
נוסחת קיילי נגזרת ממשפט קירכהוף כמקרה פרטי, על ידי חישוב הערכים העצמיים של הלפלסיאן של גרף שלם בעל צמתים: כל וקטור בעל הערך 1 באיבר אחד, 1- באיבר אחר ו-0 בכל מקום אחר בווקטור העצמי של הלפלסיאן של הגרף השלם, כאשר הערך העצמי המתאים לו הוא .
הווקטורים הללו פורשים מרחב בעל ממד מסדר ולכן אין שום ערכים עצמיים נוספים השונים מ-0, כלומר .
משפט קון (נקרא על שמו של הארולד קון Harold W.
Kuhn) הוא משפט בתחום תורת המשחקים.
לפי משפט זה בכל משחק בצורה רחבה, אם לשחקן כלשהו יש זיכרון שלם אז לכל אסטרטגיה מעורבת של אותו שחקן קיימת אסטרטגיית התנהגות שקולה לה ולכל אסטרטגיית התנהגות של אותו שחקן קיימת אסטרטגיה מעורבת השקולה לה.
נאמר שלשחקן יש זיכרון שלם אם לכל שני קדקודים , הנמצאים באותה קבוצת ידיעה של שחקן , המסילות מהשורש לקדקודים , עוברות דרך אותן קבוצות ידיעה של שחקן ובאותו סדר.
יתר על כן, הפעולה שבה שחקן נוקט בקדקוד ההחלטה ה- שלו על המסילה לקדקוד שווה לפעולה בה הוא נוקט בקדקוד ההחלטה ה- שלו על המסילה לקדקוד .
שקילות בין אסטרטגיה מעורבת לאסטרטגית התנהגות
השקילות באה לידי ביטוי במובן שבו ללא תלות באסטרטגיות בהן נוקטים השחקים האחרים, ההסתברות להגיע לקדקוד בעץ כאשר שחקן משתמש באסטרטגיה מעורבת מסוימת זהה להסתברות להגיע לאותו הקדקוד כאשר שחקן נוקט באסטרטגיית ההתנהגות השקולה לה.
כלומר, אם היא אסטרטגיה מעורבת ו- היא אסטרטגית התנהגות של שחקן במשחק בצורה רחבה אז הן שקולות זו לזו אם לכל קומבינציה של אסטרטגיות של שאר השחקנים הן משרות הסתברויות שוות על כל אחד מקדקודי עץ המשחק כלומר על כל אחת מהתוצאות האפשריות במשחק.
יתרונות בהחלפת אסטרטגיה מעורבת באסטרטגיית התנהגות שקולה לה
קבוצת אסטרטגיות ההתנהגות "קטנה יותר" מקבוצת האסטרטגיות המעורבות כיוון שהיא חוסכת בפרמטרים.
למשל, אם לשחקן מסוים יש 3 קבוצות ידיעה עם שתי פעולות אפשריות בכל אחת, הרי שמספר האסטרטגיות הטהורות הן ואז כל אסטרטגיה מעורבת כוללת 7 משתנים בעוד שאסטרטגית התנהגות כוללת רק 3 משתנים.
קל יותר לחשוב על עשיית הגרלה על הפעולות האפשריות בכל קבוצת ידיעה ולא לחשוב על תוכנית פעולה כוללת לכל המשחק.
משחק בו משתתף שחקן יחיד עם אסטרטגיה מעורבת שאין אסטרטגיית התנהגות שקולה לה
לשחקן יש ארבע אסטרטגיות טהורות {}.
נראה כי לאסטרטגיה המעורבת אין אסטרטגית התנהגות שקולה.
אסטרטגיה מעורבת זו משרה את ההתפלגות הבאה על תוצאות המשחק:
אסטרטגית התנהגות משרה את ההתפלגות הבאה על התוצאות:
אם אסטרטגית ההתנהגות שקולה לאסטרטגיה המעורבת , שתיהן משרות אותה התפלגות על התוצאות.
למערכת משוואות זו אין פתרון.
כלומר, אין אסטרטגית התנהגות שקולה.
משחק בו משתתף שחקן יחיד עם אסטרטגית התנהגות שאין אסטרטגיה מעורבת שקולה לה ("הנהג השכחן")
לשחקן יש שתי אסטרטגיות ו- .
האסטרטגיה הטהורה מביאה לתוצאה , והאסטרטגיה הטהורה מביאה לתוצאה .
כידוע, אסטרטגיה מעורבת היא התפלגות על האסטרטגיות הטהורות, מכאן ניתן להסיק שאין אסטרטגיה מעורבת שניתן לקבל באמצעותה את התוצאה .
נסתכל על אסטרטגיית ההתנהגות בה השחקן מגריל בין שתי האפשרויות בהסתברויות שוות: .
במקרה כזה ההתפלגות על התוצאות האפשריות הן: .
מכיוון שהתפלגות זו אינה יכולה להתקבל באמצעות אסטרטגיה מעורבת כלשהי נאמר שאין אסטרטגיה מעורבת שקולה לאסטרטגיית ההתנהגות הנתונה.
התנאי לכך שלכל אסטרטגיית התנהגות יש אסטרטגיה מעורבת שקולה
כל מסילה היוצאת מהשורש עוברת דרך כל קבוצת ידיעה של שחקן לכל היותר פעם אחת.
משפט קניג (נקרא גם אי-שוויון קניג) הוא משפט מתמטי בתורת הקבוצות.
המשפט הוכח על ידי המתמטיקאי ההונגרי-יהודי דיולה קניג (Kőnig Gyula) המשפט מהווה הכללה של משפט קנטור.
נוסח המשפט: לכל קבוצה , אם לכל נתונות זוג עוצמות ו-, כך שמתקיים , אז:
אגף שמאל של המשפט סכום העוצמות , ואילו אגף ימין הוא מכפלת העוצמות .
אי-השוויון הוא טריוויאלי כאשר העוצמות והקבוצה סופיים, אבל כלל אינו ברור מאליו למקרים אינסופיים.
אם למשל תוחלף המכפלה באגף ימין בסכום, עשוי להתקיים שוויון (שאינו נכון כלל במקרה הסופי).
משפט קנטור מתקבל כמקרה פרטי של משפט קניג:
למעשה, ממשפט קניג נובעת תוצאה חזקה יותר:
כאשר הוא הקופינאליות של המונה האינסופי , ו- היא פונקציית גימל.
ניתן להוכיח זאת על ידי הבחירה הבאה (בסימונים של תחילת הערך):
מהעובדה הזאת נובע השיפור הבא של משפט קנטור:
ניתן להוכיח אותו על ידי הצבה , ואז אם נניח בשלילה: נקבל כי , בסתירה לטענה הקודמת.
תהי פונקציה, ונניח כי , לכל i.
נראה כי הפונקציה הזו איננה על.
לכל , נגדיר את הפונקציה fi על ידי צימצום הפונקציה f לקבוצה Bi בקלט וצמצום הפלט רק לקואורדינטה ה-i שלו.
אם נחשוב על איברי המכפלה כפונקציות עם קלט ב- , אז עבור .
הפונקציה הזו, , לא תהיה על בגלל שמתקיים .
לכן, ניתן לבחור שאינו בתמונה של fi.
נטען כי האיבר לא נמצא בתמונת f, ובכך נסיים את ההוכחה.
אחרת, היה לו מקור, .
אבל אז, הקואורדינטה ה-i של c, הייתה נמצאת בתמונה של fi, וזו סתירה לצורה בה בחרנו את c.
השימוש באקסיומת הבחירה נעשה בשלב האחרון, בו טענו כי c קיים (או באופן שקול, כאשר בחרנו לכל i את ci).
ללא אקסיומת הבחירה קיים אוסף של קבוצות לא ריקות שמכפלתו ריקה.
אוסף זה יסתור את משפט קניג באופן טריוויאלי.
משפט קושי לטורים קובע שמכפלה של טורים מתכנסים בהחלט, כאשר מפרשים אותה כטור, מתכנסת בהחלט אף היא, וסכומה הוא מכפלת הסכומים של הטורים.
יהיו ו- טורים מתכנסים בהחלט ל-A ול-B בהתאמה, אפוא הטור מתכנס אף הוא בהחלט וסכומו הוא AB.
אלא שטור הוא סכום של סדרה, וכדי שלסכום המכפלות תהיה משמעות של טור, יש לסדר את הרכיבים בסדר כלשהו, למשל כך שהרכיבים עם i+j קטן יותר מופיעים מוקדם יותר.
משפט קושי עוסק בטור המכפלה ללא סדר מוגדר על האיברים.
הוא קרוב ברוחו למשפט מרטן, העוסק באותו טור עם סדר האיברים הטבעי, כדלקמן.
יהיו ו- טורים מתכנסים, שאחד מהם מתכנס בהחלט.
אז הטור שמוגדר מתכנס אף הוא בהחלט וסכומו הוא AB.
הקשר בין שני הטורים הוא שהטור המתואר במשפט מרטן מתקבל מהטור המתואר במשפט קושי באמצעות הכנסת סוגריים לסידור נתון של הטור.
בדרך כלל הכנסת סוגריים לטור ניתנת ללא שינוי הסכום, אם מספר האיברים בכל סוגריים חסום והאיבר הכללי שואף לאפס או אם כל האיברים בכל סוגריים שווי-סימן.
משפט מרטן קובע שהכנסת סוגריים לטור המתואר במשפט קושי מותרת בהינתן הסדר המתואר ללא התנאים הללו.
כדי להוכיח שהטור מתכנס בהחלט נבחר סידור כלשהו של טור הערכים המוחלטים (כדוגמת הקונבולוציה שהוזכרה לעיל); כעת מכיוון שכל האיברים של טור הערכים המוחלטים אי-שליליים, הרי שסדרת הסכומים החלקיים עולה, ולפיכך מספיק להראות שהיא חסומה כדי להסיק שהיא מתכנסת.
נניח כי נתון סכום חלקי כלשהו, אפשר לחסום כל סכום חלקי של טור המכפלה באמצעות מכפלת הסכומים החלקיים , כאשר n הוא אינדקס מקסימלי בין כל איבר בסכום החלקי הנתון של המכפלה.
ביטוי זה חוסם את הסכום החלקי מכיוון שכל הקומבינציות של המכפלות האפשריות מופיעות בו, והוא כמובן חסום על ידי המכפלה .
מכאן שהטור מתכנס בהחלט ובפרט מתכנס, כלומר סדרת הסכומים החלקיים שלו (בסידור כלשהו) היא סדרה מתכנסת.
מהעובדה שמדובר בסדרה מתכנסת נובע שכל תת-סדרה שלה מתכנסת לאותו גבול, ולכן מספיק למצוא תת-סדרה כלשהי שמתכנסת ל-AB.
אם מתבוננים בסידור של איברי המכפלה מהצורה הבאה: , ולוקחים תת-סדרה מהצורה , ניתן להסיק שהגבול ב-n ששואף לאינסוף הוא AB.
משפט קנטור-בנדיקסון הוא משפט מתמטי הקובע שכל קבוצה סגורה בישר הממשי היא איחוד זר של קבוצה מושלמת וקבוצה בת-מנייה.
המשפט התקבל במסגרת ניסיונותיו של גאורג קנטור להוכיח את השערת הרצף.
מהמשפט נובע שכל קבוצה סגורה של ממשיים היא בת-מנייה או מעוצמת הרצף.
קבוצה היא קבוצה מושלמת אם היא הקבוצה הנגזרת של עצמה.
בנוסח שקול, מושלמת אם ורק אם היא סגורה ואין לה נקודות מבודדות.
לכל סגורה קיימת מושלמת ו- בת-מנייה, כך ש- ו-.
ההוכחה המקורית של המשפט עושה שימוש בדרגת קנטור-בנדיקסון של הקבוצה.
אם קבוצה סגורה בישר שדרגתה אז קבוצה מושלמת.
מכך שהישר הוא מרחב מנייה שנייה נובע ש- בת-מנייה.
נציג כאן הוכחה אלמנטרית יותר.
נתייחס ל- כמרחב טופולוגי עם הטופולוגיה המושרית מהישר.
נקודת עיבוי של היא נקודה שכל סביבה שלה (ב-) אינה בת-מנייה.
תהי קבוצת נקודות העיבוי של .
הוא בסיס בן-מנייה של .
תהי קבוצת כל איברי שהן קבוצות בנות-מנייה.
כל אינה נקודת עיבוי, כי סביבה בת-מנייה, ולכן .
מצד שני, לכל יש סביבה בת-מנייה, המכילה תת-סביבה בסיסית כלשהי שהיא בת-מנייה, ולכן .
מכאן ש- בת-מנייה כאיחוד בן-מנייה של קבוצות בנות-מנייה.
נוכיח כי ל- אין נקודות מבודדות.
מכיוון ש- נקודת עיבוי אינה בת-מנייה.
בת-מנייה ולכן מכילה אינסוף נקודות.
אולם , ולכן מכילה אינסוף נקודות של , כלומר לא מבודדת ב-.
כדי להוכיח ש- מושלמת נותר להוכיח כי היא סגורה ב-.
סגורה ב- כי פתוחה ב- כאיחוד של קבוצות פתוחות.
לפי הגדרת הטופולוגיה המושרית קיימת סגורה ב- כך ש-.
לכן סגורה בישר כחיתוך של קבוצות סגורות.
כל קבוצה מושלמת היא ריקה או מעוצמת הרצף.
לכן ממשפט קנטור-בנדיקסון נובע שכל קבוצה סגורה היא בת-מנייה (במקרה ) או מעוצמת הרצף.
כל קבוצה פתוחה לא ריקה מכילה גם היא קבוצה מושלמת לא ריקה (כי היא מכילה קטע סגור שהוא מושלם).
קנטור קיווה להוכיח שכל קבוצה שאינה בת-מנייה מכילה קבוצה מושלמת ובכך להוכיח את השערת הרצף.
אם מניחים את אקסיומת הבחירה, טענה זו אינה נכונה וניתן לבנות בלכסון דוגמה נגדית.
באלגברה, משפט קולצ'ין קובע כי ניתן לשלש סימולטנית מונואיד של מטריצות אוניפוטנטיות (מעל שדה סגור אלגברית).
את המשפט ניסח והוכיח אליס קולצ'ין, שעסק רבות באלגברה דיפרנציאלית ובחבורות אלגבריות ליניאריות.
מטריצה תקרא אוניפוטנטית אם היא מטריצה נילפוטנטית.
מונואיד של מטריצות נקרא אוניפטנטי אם כל איבר אוניפטנטיים.
משפט קולצ'ין קובע כי אם מונואיד (ואפילו חבורה למחצה) אוניפטנטי של מטריצות מעל שדה סגור אלגברית, אז ניתן לשלש סימולטנית את כל איברי המונואיד.
כלומר, קיים בסיס אחד לפיו כל איברי המונואיד הם בצורה משולשית (עליונה).
זהו הניסוח הראשוני של המשפט.
למעשה, ניתן לוותר על הדרישה שהשדה יהיה סגור אלגברית, כלומר בעזרת מעבר אל הסגור האלגברי הטענה נכונה לכל שדה.
ההוכחה שתינתן בעלת רעיון חשוב שחוזר על עצמו במשפטים דומים .
ניעזר במשפט של ודרברן, הקובע כי אלגברה ממד סופי מעל השדה ובעלת בסיס נילפוטנטי היא בעצמה נילפוטנטית.
תהי חבורה למחצה, ויהי המרחב הליניארי הנפרש על ידי האיברים מהצורה , עבור .
מתקיים, ולכן זוהי תת-אלגברה בעלת בסיס נילפוטנטי, ולפי המשפט של ודרברן היא עצמה נילפוטנטית: נניח .
לכן, אם , אז לכל מתקיים , כלומר ולכן יש וקטור עצמי משותף לכל איברי תת-החבורה.
לכן, כל איבר ניתן להביא אל הצורה עבור , ומכאן ממשיכים באינדוקציה.
משפט קולצ'ין קובע תכונות מבנה של מטריצות אוניפטנטיות.
למשפט מספר הקבלות טבעיות למקרים אחרים:
משפט לי באלגברות לי פתירות
משפט אנגל באלגברות לי נילפטוניות
ישראל הרשטיין הוכיח טענה מקבילה עבור חוג עם זהויות נוצר סופית (עם יחידה).
ראשית, איבר הוא אוניפוטנט אם הוא איבר נילפוטנטי.
אזי קיים כך ש- לכל .
סקירת ההוכחה: כמו בהוכחה לעיל, יהי המרחב הנפרש על ידי .
תוך שימוש בטענות על חוגים עם זהויות ניתן להוכיח כי זוהי תת-אלגברה נילית.
כעת, בחוג נוצר סופית עם זהויות, ניתן להוכיח כי כל תת-אלגברה נילית מוכלת ברדיקל ג'ייקובסון, ולכן בעצמה נילפוטנטית.
לכן, כמו קודם, ניתן למצוא כך ש-.
עבור ההוכחה המלאה, ראו בקריאה נוספת.
בעיית קולצ'ין (the Kolchin Problem) שואלת האם ניתן להכליל את הטענה עבור מטריצות מעל חוג עם חילוק.
כלומר, האם ניתן לשלש סימולטנית תת-חבורה (או ביתר כלליות מונואיד) של מטריצות הפיכות מעל חוג עם חילוק.
Mochizuki הוכיח כי הטענה נכונה עבור תתי חבורות במאפיין אפס.
הראשונים לשאול את השאלה היו ארווינג קפלנסקי ובוריס פלוטקין.
ניסוח כללי יותר של השאלה, המתקשר גם אל איברים נילפוטנטיים וההוכחה לפי המשפט של ודרברן, הוא: נניח ש- היא תת-קבוצה של איבר נילפוטנטיים, כך שלכל מתקיים .
משפט קוקס הוא הוא הסקה של חוקי תורת ההסתברות ממערכת מסוימת של אקסיומות.
זוהי הרחבה של לוגיקה בוליאנית למצבי אי ודאות, תוך שמירה על עקרונות יסוד מסוימים (האקסיומות).
המשפט נקרא על שמו של הפיזיקאי ריצ'רד טרקלד קוקס (Richard Threlkeld Cox).
למרות שהתורה הנגזרת מפיתוח זה זהה כמעט בכל מובן לתורת ההסתברות הקלאסית, הפרשנות הניתנת בה למה מייצגת הסתברות של מאורע נתון היא בייסיאנית באופייה.
משפט קוקס מבוסס על ההנחות הבאות:
ההסתברות של נכונות טענה ניתנת לייצוג באמצעות מספר ממשי.
היא מבוססת על מידע הקשור לטענה.
שכל ישר - סבירויות ישתנו על פי השכל הישר של סבירויות המודל.
עקביות - אם יש דרכים שונות להערכת הסתברות של טענה, תוצאות כל הדרכים צריכות להיות שוות.
ההנחות הנ"ל מובאות כפי שנוסחו על ידי Arnborg וSjödin.
המשפט כפי שנוסח במקור על ידי קוקס מנוסח באופן מעט יותר פורמלי מהניסוח לעיל, אך עדיין לא באופן ריגורוזי לחלוטין.
ניתן לפרמל את ההנחות ולהוכיח את המשפט אם מוסיפים הנחות בהן השתמש קוקס באופן מרומז או באופן גלוי.
המשוואות המרכיבות את האקסיומה של קוקס
המשוואות המרכיבות את האקסיומה של קוקס הן:
ההסתברות של נכונות טענה קובעת את ההסתברות של שלילת הטענה.
כשההסתברות של הטענה גדלה, ההסתברות של שלילת הטענה קטנה.
כשההסתברות של שלילת הטענה גדלה, ההסתברות של הטענה קטנה.
המשוואה הנגזרת מכך היא: .
ההסתברות של האיחוד של שתי טענות ו- תלויה רק בהסתברות של טענה ובהסתברות של בהינתן ש- נכונה.
מזה הסיק קוקס שאיחוד של הסתברויות הוא אסוציאטיבי.
בניסוח מתמטי: כאשר היא פונקציה המבוססת על אופרציה בינארית אסוציאטיבית של ו-.
נניח ש שווה ערך ל .
אם נקבל מידע חדש ואחרי זה נקבל מידע חדש ונעדכן את כל ההסתברויות בכל פעם על פי המידע החדש, ההסתברויות המעודכנות יהיו זהות להסתברויות המעודכנות במקרה שנקבל מידע חדש ואחרי זה נקבל מידע חדש .
המשמעות היא שכפל של הסתברויות זהה לכפל של מספרים ממשיים.
משפט קוקס הפך לאחד ההצדקות של השימוש בהסתברות בייסיאנית.
בעוד על פי תפיסת הסתברות רגילה, הסתברות מתפרשת כשיטת לוגיקה פורמלית המהווה הרחבה של הלוגיקה של אריסטו למצבי אי-ודאות.
קיים ויכוח על השאלה האם משפט קוקס מוציא מכלל אפשרות מודלים אחרים להסתברות בתנאי אי-ודאות.
הוצעו גם חלופות אחרות, המתבססות על ביטול חלק מההנחות הפחות אינטואיטיביות במשפט קוקס.
מודל כזה הוצע למשל על ידי הארדי.
משפט קלרו הוא חוק פיזיקאלי המאפשר לחשב את המשיכה הכבידתית על פני השטח של ספרואיד מסתובב הנתון בשיווי משקל תחת השפעת השדה הכבידתי העצמי שלו והכוח הצנטריפוגלי.
המשפט פורסם על ידי אלכסיס קלרו ב-1743 בחיבורו Théorie de la figure de la terre, tirée des principes de l'hydrostatique (תאוריה של צורת כדור הארץ, המתבססת על עקרונות ההידרוסטטיקה), אשר עיבד עדויות פיזיקליות וגאודזיות לכדי מסקנה שכדור הארץ הוא אליפסואיד פחוס.
הנוסחה של קלרו לתאוצת הכבידה g על פני השטח של ספרואיד בקו רוחב φ, היא:
כאשר הוא הערך של תאוצת הכבידה בקו המשווה, m הוא היחס בין הכוח הצנטריפוגלי לכבידה בקו המשווה, ו-f הוא הפחיסות של חתך מרידיאני של כדור הארץ (חתך שנעשה לאורך קו אורך), שמוגדרת כ-:
(כאשר a הוא חצי הציר הראשי ו-b הוא חצי הציר המשני).
משפט קוטה-ז'וקובסקי (לעיתים: תורת קוטה ז'וקובסקי) הוא משפט יסודי באווירודינמיקה ובאופן כללי יותר במכניקת הזורמים המשמש לחישוב כוח העילוי הפועל על כנף דו-ממדית הנעה במהירות מספקת כך ששדה הזרימה סביבה הוא תמידי, למינרי וצמוד לכנף.
המשפט מקשר בין העילוי, צפיפות הזורם והסירקולציה מסביב לכנף.
התורה פותחה בראשית המאה ה-20 על ידי מרטין קוטה וניקולאי ז'וקובסקי וקרויה על שמם.
הנחת התיאוריה לפיה הזרימה למינרית על שפת הכנף מזניחה את צמיגות האוויר שגורמת להיווצרות שכבת גבול טורבולנטית דקה על שפת הכנף.
למרות זאת התורה מהווה קירוב מדויק למדי עבור תעופה במהירות גבוהה מספיק ובזווית תקיפה נמוכה מספיק.
עבור זרימה דו-ממדית מסביב לכנף קבועה, הנעה במהירות קבועה בתווך בו הצמיגות והדחיסות זניחה, כוח העילוי ליחידת אורך של מוטת הכנף מקיים: , כאשר צפיפות הזורם, מהירות הזרימה המציפה ו- היא הסירקולציה מסביב לכנף.
כוח העילוי יהיה מאונך לכיוון הזרימה המציפה.
הלולאה עליה מחושבת הסירקולציה צריכה להיות בתחום בו ניתן להניח שהזרימה היא זרימה פוטנציאלית, ולא בתחום שכבת הגבול על שפת הכנף.
הסירקולציה, תנאי קוטה וכנף ז'וקובסקי
תורת קוטה ז'וקובסקי מאפשת לחשב את העילוי בהנחה שהסירקולציה נתונה; היא לא מסבירה מדוע הסירקולציה נוצרת ולא מציגה דרך לחשב את הסירקולציה עבור צורת כנף, זווית התקפה ומהירות זרימה ידועות.
בכנף קבועה, היווצרות הסירקולציה נובעת מקיום תנאי קוטה, לפי תנאי זה, בזרימה מסביב לכנף עם קצה אחורי חד, נקודת הסטגנציה של הזרימה תהיה בקצה החד של הכנף.
המשמעות של תנאי זה הוא שזרימה העוברת תחת הכנף לא נעה מסביב לקצה הכנף כדי לזרום מעל לכנף.