 |
בוא ונראה, משפט רמזי אומר כי לכל n,k קיים m כך שלכל צביעה ב-k צבעים של קשתות הגרף המלא על m קודקודים (K_m), יש תת-קבוצה של הקודקודים בגודל n לפחות כך שכל הקשתות ביניהם צבועות באותו הצבע.
עכשיו בוא נניח שכשאנחנו מסתכלים על K_m הקודקודים ממוספרים מ-1 עד m. נקרא לתת-קבוצה של הקודקודים מהוללת אם גודל הקבוצה גדול ממספרו של הקטן בקודקודיה. משפט פריס-הרינגטון (Paris-Harrington) אומר כי לכל n,k קיים m כך שלכל צביעה ב-k צבעים של קשתות הגרף המלא (והממוספר) על m קודקודים (K_m), יש תת-קבוצה מהוללה של הקודקודים בגודל n לפחות כך שכל הקשתות ביניהם צבועות באותו הצבע.
המשפט הזה הוא נכון (אולי אתן תמצית ההוכחה אח"כ) אבל אינו יכיח מאקסיומות פאנו, כי הוא גורר את עקביותן.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש