88-101 חשיבה מתמטית - כמתים

זהו החלק השני של המבוא לחשיבה מתמטית.

כמתים

פסוקים עם כמתים

הכמתים, המציינים תחולה של משתנה, הם תוספת חיונית למערך הקשרים שלנו. יש שני כמתים: "לכל", המסומן באות [math]\displaystyle{ \forall }[/math] (זוהי A הפוכה, קיצור של המלה All); ו"קיים", המסומן באות [math]\displaystyle{ \exists }[/math] (E הפוכה, קיצור של Exists). כשבונים פסוק עם כמתים, מותר לקחת פסוק קיים (הכולל פרדיקטים, שבהם x הוא משתנה), ולבנות:

• [math]\displaystyle{ \forall x : P(x) }[/math] - מקבל ערך אמת T אם הפסוק [math]\displaystyle{ P(x) }[/math] מקבל ערך אמת T לכל הצבה של x.
• [math]\displaystyle{ \exists x: P(x) }[/math] - מקבל ערך אמת T אם יש הצבה של x כך שהפסוק [math]\displaystyle{ P(x) }[/math] מקבל ערך אמת T.

הערה. יש דרכים רבות לכתוב פסוקים כגון אלו. מקובל למשל [math]\displaystyle{ \forall x P(x) }[/math] או [math]\displaystyle{ (\forall x)P(x) }[/math] . כל הסגנונות חוקיים, בתנאי שהפסוק ניתן לקריאה באופן חד-משמעי.

דוגמא. את הפסוק "אין מספר גדול ביותר" אפשר להצרין באופן פשטני, כך: [math]\displaystyle{ \neg\exists x: L(x) }[/math] , כאשר [math]\displaystyle{ L(x) }[/math] הוא הפרדיקט "x הוא מספר גדול ביותר". הצרנה מעט יותר מתוחכמת תגדיר את הפרדיקט [math]\displaystyle{ P(x,y) }[/math] שפירושו "x<y", ותצרין ל- [math]\displaystyle{ \forall x:\exists y: P(x,y) }[/math] , כלומר, לכל מספר יש מספר הגדול ממנו.

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

דוגמא. נצרין את הטענה הבאה:

לכל משוואה ריבועית [math]\displaystyle{ ax^2+bx+c=0 }[/math] כך ש- [math]\displaystyle{ b^2-4ac\ge0 }[/math] יש לפחות פתרון אחד.

[math]\displaystyle{ \forall a\forall b\forall c\Big[(b^2-4ac\ge0)\to\big(\exists x(ax^2+bx+c=0)\big)\Big] }[/math]

תרגיל. הצרינו את הטענה הבאה:

לכל משוואה ריבועית [math]\displaystyle{ ax^2+bx+c=0 }[/math] כך ש- [math]\displaystyle{ b^2-4ac=0 }[/math] קיים בדיוק פתרון אחד.

תרגיל

הצרינו את הטענות הבאות:

• למספר שלילי אין שורש ריבועי

תשובה: [math]\displaystyle{ \forall x(x\lt 0\to\forall y(y^2\ne x)) }[/math]

• למספר חיובי יש שורש חיובי ושורש זה אינו יחיד

תשובה: [math]\displaystyle{ \forall x(x\gt 0\to(\exists y(y^2=x)\and\exists z((z\ne y)\and (z^2=x))) }[/math]

פסוקים אמיתיים

לפסוקים שיש בהם כמתים אי אפשר לבנות טבלאות אמת, משום שלצד האטומים המקבלים רק שני ערכי אמת אפשריים, יש בהם משתנים העשויים לעבור על-פני מספר אינסופי של אפשרויות. לכן הלוגיקה המטפלת בפסוקים עם כמתים (הנקראת "לוגיקה מסדר ראשון") מורכבת יותר מן הלוגיקה הפסוקית, ויש לה יכולת ביטוי רחבה יותר. גם בלוגיקה זו אומרים ששני פסוקים [math]\displaystyle{ \varphi,\psi }[/math] הם שקולים אם [math]\displaystyle{ \varphi\leftrightarrow\psi }[/math] מקבל ערך אמת לכל הצבה של המשתנים המעורבים.

פסוק אמיתי הוא כזה שמתקיים לכל בחירה של הפרדיקטים ולכל הצבה במשתנים. כל הטאוטולוגיות הן פסוקים אמיתיים, אבל ההיפך אינו נכון. לא נכנס כאן לפרטים, שמהם מתפרנסים חוקרי הלוגיקה המתמטית.

כיצד מוכיחים. זוהי דרך המלך להוכחה או סתירה של טענות:

• כדי להוכיח שהפסוק [math]\displaystyle{ \forall x:P(x) }[/math] אמיתי, יש להראות שהטענה P נכונה לכל ערך אפשרי של x.
• כדי להוכיח שהפסוק [math]\displaystyle{ \exists x:P(x) }[/math] אמיתי, יש למצוא ערך של x שעבורו הטענה נכונה ("דוגמא").
• כדי להוכיח שהפסוק [math]\displaystyle{ \forall x:P(x) }[/math] שקרי, יש למצוא ערך של x שעבורו הטענה אינה נכונה ("דוגמא נגדית").
• כדי להוכיח שהפסוק [math]\displaystyle{ \exists x:P(x) }[/math] שקרי, יש להראות שהטענה P אינה נכונה לכל ערך אפשרי של x.

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

תרגיל. קבע אלו מהפסוקים הבאים הם אמיתיים, כאשר הסימנים "לכל" ו"קיים" פירושם "לכל מספר שלם" ו"קיים מספר שלם". אם הפסוק אינו אמיתי, בחר פרדיקטים ומשתנים המדגימים זאת.

• [math]\displaystyle{ \forall x P(x)\implies\exists x P(x) }[/math] .
• [math]\displaystyle{ \forall z:P(z)\to\forall x,y:P(x^2+y^2) }[/math] .
• [math]\displaystyle{ \exists z:P(z)\to\exists x,y:P(x^2+y^2) }[/math] .
• [math]\displaystyle{ (\forall x:P(x)\and\forall x:Q(x))\to\forall x:(P(x)\and Q(x)) }[/math] .
• [math]\displaystyle{ \forall x:(P(x)\and Q(x))\to(\forall x:P(x)\and\forall x:Q(x)) }[/math] .
• [math]\displaystyle{ (\exists x:P(x)\and\exists x: Q(x))\to\exists x:(P(x)\and Q(x)) }[/math] .
  • פתרון: יש מספר שלם ריבועי ויש מספר שלם בין 70 ל-80; אבל אין מספר שלם ריבועי שהוא בין 70 ל-80.
• [math]\displaystyle{ \exists x:(P(x)\and Q(x))\to(\exists x:P(x)\and\exists x:Q(x)) }[/math] .
• [math]\displaystyle{ (\exists x:P(x)\or\exists x:Q(x))\to\exists x:(P(x)\or Q(x)) }[/math] .

תרגיל. שכנע את עצמך באמיתיות הפסוק הבא:

• [math]\displaystyle{ (\forall x:P(x)\to Q(x))\to(\forall x:P(x)\to\forall x:Q(x)) }[/math] .

תרגיל. נניח ש-c הוא קבוע, A תכונה אטומית, ו-P פרידקט עם משתנה אחד. הוכח את השקילות של הפסוקים הבאים:

• [math]\displaystyle{ \ (\forall x: P(x)) \leftrightarrow A }[/math] (השמש זורחת אם ורק אם כל התרנגולים קוראים),
• [math]\displaystyle{ \ (P(c) \rightarrow A) \wedge (A \rightarrow \forall x: P(x)) }[/math] (כשהתרנגול קוקי קורא השמש זורחת, וכשהשמש זורחת כל התרנגולים קוראים).
• האם הפסוק [math]\displaystyle{ \ (\forall x: P(x)) \leftrightarrow A }[/math] שקול לפסוק [math]\displaystyle{ \ \forall x: (P(x) \leftrightarrow A) }[/math] (כל תרנגול, בנפרד, קורא אם ורק אם השמש זורחת)?

משתנים ותחולתם

אנו מגיעים לנקודה חשובה ביותר הנוגעת לשמות המשתנים. לכל כמת יש אזור תחולה. אם נכתוב למשל [math]\displaystyle{ \ \forall x : (P(x) \rightarrow Q(x)) \rightarrow \exists y : P(y) }[/math], אזור התחולה של הכמת הראשון הוא תת-הפסוק [math]\displaystyle{ \ P(x) \rightarrow Q(x) }[/math], ואזור התחולה של הכמת השני הוא ההופעה השניה. בתוך אזור התחולה הזה, אין כל חשיבות לשם המשתנה - אין שום הבדל בין "לכל נורה x יש מתג y כך ש-y מפעיל את x" (הצרן את הפסוק הזה), לבין "לכל נורה z יש מתג y כך ש-y מפעיל את z": השני מתקבל מהחלפת המשתנה x במשתנה z. לעומת זאת, הפסוק "לכל נורה x יש מתג y כך ש-y מפעיל את z" הוא בעל משמעות שונה (יש לו "משתנה חופשי", z, שההצבה בו תקבע את ערך האמת); הצבה לא זהירה ושגויה משנה את משמעות הפסוק.

נתבונן בפרדיקט בן שני משתנים, [math]\displaystyle{ \ P(x,y) }[/math] (למשל x אוהב את y). ערך האמת שלו תלוי בהצבה של x ו-y. נשווה זאת לפסוק [math]\displaystyle{ \ \forall x : P(x,y) }[/math] (כל x אוהב את y). בפסוק זה אי אפשר להציב את x: הפסוק למעשה אומר "כולם אוהבים את y", והתפקיד של x הוא פורמלי לחלוטין - לסמן את המשתנה העובר על כל האפשרויות. הפסוק [math]\displaystyle{ \ \forall z : P(z,y) }[/math] שקול לגמרי לקודם. כדי להדגיש זאת, אפשר לכתוב [math]\displaystyle{ \ \phi(y) = \forall x: P(x,y) }[/math], שבו יש משתנה חופשי יחיד, y.

שימו לב לתפקיד הרגיש של x בפסוק כזה. אם נכתוב למשל [math]\displaystyle{ \ \forall x : P(x,x) }[/math] ("כל אחד אוהב את עצמו"), נקבל פסוק בעל משמעות שונה לחלוטין. אם רוצים להציב ב-[math]\displaystyle{ \ \phi }[/math] את x דווקא, מוכרחים להחליף לפני כן את המשתנה. לא נכתוב [math]\displaystyle{ \ \phi(x) = \forall x: P(x,x) }[/math], אלא [math]\displaystyle{ \ \phi(x) = \forall z: P(z,x) }[/math].

נתבונן בדוגמא נוספת. אם ידועה תכונה Q הנכונה לכל x ולכל y, כותבים [math]\displaystyle{ \ \forall x : \forall y : Q(x,y) }[/math] (ולפעמים, בקיצור, [math]\displaystyle{ \ \forall x,y: Q(x,y) }[/math]). מכיוון שהטענה נכונה לכל x ולכל y, אפשר להציב בה ערכים בכל דרך שנרצה - כמובן שלכל x ו-y מתקיים [math]\displaystyle{ \ Q(x,y) }[/math], אבל גם [math]\displaystyle{ \ Q(y,x) }[/math] או [math]\displaystyle{ \ Q(x,x) }[/math].

לעומת זאת, הטענה [math]\displaystyle{ \ \exists x,y: Q(x,y) }[/math] אומרת שקיימים x,y המקיימים את התכונה (מישהו נשך מישהו אחר במרפק). אנחנו לא יכולים לבחור את x,y - וגם לא להניח שיש קשר מסויים ביניהם. בפרט, לא נובע מההנחה ש- [math]\displaystyle{ \ \exists x: Q(x,x) }[/math] (מישהו נשך את עצמו במרפק).

קל לטעות, ולעבור מ"קיים חתול שאוהב שניצלים" ל"הנה חתול; מכאן שהוא אוהב שניצלים". להלן דוגמא מבחינה של סטודנט. כידוע, מספר טבעי a הוא ראשוני אם בכל פירוק שלו a=bc, אחד הגורמים הוא 1. (היינו, לכל b,c, אם a=bc אז b=1 או c=1). נניח ש-a אינו ראשוני, ונניח ש-a=bc; "אז b,c שונים מ-1, משום שאם אחד מהם היה שווה בהכרח ל-1, הרי ש-a היה ראשוני". שימו לב לשימוש המבלבל במלה "בהכרח". אם מהפירוק a=bc נובע *בהכרח* ש-b=1 או c=1 (כלומר, *בכל* פירוק אחד הגורמים הוא 1), הרי ש-a ראשוני; ואם ידוע ש-a אינו ראשוני, הרי שהתכונה "אחד הגורמים הוא 1" אינה *הכרחית*; אבל זה לא אומר שהיא אינה *נכונה*. הרי אין שום רבותא בכך שמספר לא ראשוני נכתב כמכפלה של גורמים שאחד מהם שווה ל-1 (הנה: 9=1*9).

להלן דוגמא נוספת. נניח ש-a,b מספרים שלמים. אומרים ש-d הוא מחלק משותף מקסימלי אם הוא מחלק את a ו-b, ומתחלק בכל מחלק משותף שלהם. כלומר, כאשר d מחלק משותף מקסימלי, לכל n כך ש-n|a,b מתקיים n|d. מה שגוי בגרסה "מכיוון ש-d מחלק משותף מקסימלי של a,b, אם יש n כך ש-n|a,b אז יש n כך ש-n|d", הלקוחה גם היא מבחינה של סטודנט? (תשובה: טענה זו שקולה לטענה "אם יש n כך ש-n|a,b אז יש m כך ש-m|d"; ומה זה אומר בכלל על d).

דוגמא נוספת: הפתרון הכללי למשוואה דיפרנציאלית מסויימת הוא הפונקציה [math]\displaystyle{ \ y(x) = e^x+C }[/math] כאשר C הוא קבוע (אין צורך לדעת מהי משוואה דיפרנציאלית כדי להצרין את הטענה הזו: קיים, מן הסתם, פרדיקט P המקבל ערך אמת T רק על פונקציות הפותרות את המשוואה, ואם כך הפסוק קובע ש"לכל y, אם [math]\displaystyle{ \ P(y) }[/math] אז קיים C כך ש- [math]\displaystyle{ \ y = e^x + C }[/math]"). קושיה שהעלה סטודנט: האם נכון לומר שהפתרון הכללי לאותה משוואה הוא [math]\displaystyle{ \ y(x) = e^x+2C }[/math]? ומה אם התהיה היתה לגבי הפתרון [math]\displaystyle{ \ y(x) = e^x+1/C }[/math]?

משפט ואן-דר-ורדן הוא אחד המשפטים היסודיים בקומבינטוריקה אינסופית. הוא קובע שבכל חלוקה של המספרים השלמים למספר סופי של קבוצות, ולכל k, אחד החלקים כולל סדרות חשבוניות ([math]\displaystyle{ \ a, a+d, a+2d, \dots,a+(k-1)d }[/math]) מאורך k. (א) הסבירו את ההבדל בין טענה זו לטענה "בכל חלוקה של השלמים למספר סופי של קבוצות, לכל k, אחד החלקים מכיל סדרה חשבונית באורך k", והראו שהן שקולות זו לזו למרות ההבדל. (ב) הראו שאפשר לחלק את השלמים לשתי קבוצות שאף אחת מהן אינה כוללת סדרה חשבונית אינסופית.

וריאציות וכימות יחסי

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

• [math]\displaystyle{ \exists x : (P(x) \wedge \forall y : (P(y) \rightarrow x=y)) }[/math] -- "קיים x המקיים את התכונה P, ובנוסף, כל y המקיים את התכונה P שווה ל-x". כלומר: "קיים x יחיד המקיים את התכונה P". לפעמים מקצרים את הפסוק הזה וכותבים [math]\displaystyle{ \ \exists! x: P(x) }[/math]. אפשר לראות בצירוף "[math]\displaystyle{ \ \exists ! }[/math]" כמת שלישי, למרות שכאמור לעיל ניתן להגדיר אותו באמצעות שני הכמתים האחרים (בנוכחות פרדיקט השוויון).

לפעמים רוצים לומר שיש אינסוף מספרים המקיימים תכונה מסויימת. אפשר לעשות זאת כך:

• [math]\displaystyle{ \ \forall n : \exists x : ((x\gt n) \wedge P(x)) }[/math]: "לכל n יש x גדול ממנו המקיים את התכונה". אם היה רק מספר סופי של מספרים המקיימים את התכונה המדוברת, אז הפסוק היה שקרי משום שאפשר היה לבחור בתור n את המספר הגדול ביותר.

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

• [math]\displaystyle{ \ \forall x\gt 0: \exists y\gt 0: y\lt x }[/math] - "לכל מספר חיובי x יש מספר חיובי y הקטן ממנו", כלומר "אין מספר חיובי קטן ביותר", בתור קיצור לכתיבה המלאה [math]\displaystyle{ \ \forall x: ((x\gt 0) \rightarrow (\exists y: ((y\gt 0) \wedge (y\lt x)))) }[/math] - "לכל מספר x, אם הוא חיובי, אז קיים מספר y שהוא חיובי וקטן מ-x".

תרגיל. הגדרה: חסם מלעיל של קבוצת מספרים, הינו איבר הגדול מכל איברי הקבוצה (בין אם הוא שייך בעצמו לקבוצה ובין אם לאו). לדוגמא, 0 ו-1 הם חסמים מלעיל של קבוצת המספרים השליליים.

• הצרן את הטענה "a הוא חסם מלעיל של A" (אם ברצונך להתייחס לאיברים מהקבוצה A, אפשר להשתמש בכמתים באופן [math]\displaystyle{ \forall a\in A, \exists a\in A }[/math])

הגדרה: חסם עליון הוא חסם מלעיל, הקטן מכל חסם מלעיל אחר.

• הצרן את המושג חסם עליון (כלומר, את הפסוק "a הוא חסם עליון של הקבוצה A").

a הוא חסם עליון של הקבוצה A אם מתקיים: [math]\displaystyle{ (\forall b \in A : b\lt a)\and (\forall c: \forall b \in A: (b\lt c)\rightarrow c\lt a) }[/math]

• הצרן את השלילה של הטענה "a הוא חסם מלעיל של A".
• הצרן את הטענה "אם יש לקבוצה חסם עליון, אז הוא יחיד".

תרגיל.

• באחד התרגילים הקודמים היית אמור לאשר שהפסוק [math]\displaystyle{ \ \forall x P(x) \implies \exists x P(x) }[/math] הוא אמיתי, אם הכמתים מתייחסים לקבוצת המספרים השלמים. מצא מרחב אוניברסלי לכמתים שעבורו הפסוק אינו אמיתי (חשוב על הפסוק "כל פיל מעופף יודע קרוא וכתוב; מכאן שיש פיל מעופף היודע קרוא וכתוב").

יש טענות שאפשר לנסח באופן ישיר, אבל קל יותר לנסח באופן יחסי:

תרגיל. נניח שהיכרות היא פרדיקט סימטרי P בשני משתנים (כלומר, [math]\displaystyle{ \ \forall x,y: P(x,y) \leftrightarrow P(y,x) }[/math]).

• נסח את הפסוק: מבין כל ששה אנשים, או שיש שלושה המכירים זה את זה, או שיש שלושה שאף אחד מהם אינו מכיר אף אחד אחר.

פתרון חלקי. הפתרון הישיר הוא מהצורה [math]\displaystyle{ \ \forall x_1,x_2,x_3,x_4,x_5,x_6: P(x_1,x_2,x_3,x_4,x_5,x_6) }[/math] כאשר P הוא פסוק ארוך מאד בן ששה משתנים, שאין בו כמתים. יעיל יותר לפתור כך: [math]\displaystyle{ \ x_1,\dots,x_6 }[/math] שונים, וקיימים y,z,u מתוך הערכים [math]\displaystyle{ \ x_1,\dots,x_6 }[/math], המקיימים תנאי מסויים.

בשלב זה קשה לכתוב "קיימים y,z,u מתוך" קבוצה מסויימת; כדי לעשות זאת היטב יש ללמוד מעט תורת הקבוצות.

שלילת כמתים

כמו לפסוקים המורכבים מקשרים בלבד, גם לאחר הוספת הכמתים יש לכל פסוק "פעולה אחרונה": הקשר האחרון או הכמת האחרון שהופעל כדי ליצור את הפסוק. לדוגמא:

• הפעולה האחרונה ב- [math]\displaystyle{ \ \forall x: ((x\lt y) \rightarrow (x\lt 0)) }[/math] ("לכל x, אם x קטן מ-y אז x שלילי") היא הכמת הכולל על x; לעומת זאת הפעולה האחרונה ב- [math]\displaystyle{ \ (\forall x: (x\lt y)) \rightarrow (y\lt 0)) }[/math] ("אם כל x הוא קטן מ-y, אז y שלילי") היא הקשר "אם-אז".

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

• "לא כל תפוח הוא צהוב" שקול לכך ש"קיים תפוח שאינו צהוב".
• "לא קיים תפוח צהוב" שקול לכך ש"כל תפוח אינו צהוב".

אכן, לכל פרדיקט P,

• [math]\displaystyle{ \ \neg \forall x: P(x) \equiv \exists x: \neg P(x) }[/math], וכך גם
• [math]\displaystyle{ \ \neg \exists x: P(x) \equiv \forall x: \neg P(x) }[/math].

זו הזדמנות לשוב ולעיין בדרכים להוכיח ולהפריך טענות מכומתות שהובאו בראש אחד הסעיפים הקודמים. שימו לב שאת הטענות [math]\displaystyle{ \ \forall x: \neg P(x) }[/math] ו-[math]\displaystyle{ \ \neg \exists x: P(x) }[/math] מוכיחים למעשה באותה דרך (מראים ש*לכל* x, הטענה P אינה מתקיימת), וגם את [math]\displaystyle{ \ \neg \forall x: P(x) }[/math], ו-[math]\displaystyle{ \ \exists x: \neg P(x) }[/math] מוכיחים באותה דרך (מראים ש*קיים* x שעבורו P אינה נכונה).

אפשר "לחסוך" ולכתוב כל פסוק רק באמצעות אחד משני הכמתים:

• [math]\displaystyle{ \ \exists x: P(x) \equiv \neg \forall x: \neg P(x) }[/math] ("קיים סוס שחור" = "אין זה נכון שכל הסוסים אינם שחורים").

באופן הזה אפשר להחליף כל מופע של הכמת "קיים" במופע אחד של הכמת "לכל"; כמובן, גם ההיפך אפשרי:

• [math]\displaystyle{ \ \forall x: P(x) \equiv \neg \exists x: \neg P(x) }[/math] ("כל הסוסים שחורים" = "אין אף סוס שאינו שחור").

בפועל, שני הכמתים נמצאים בשימוש מתמטי שגרתי.

תרגיל.

• נסח את שלילתו של הפסוק שהופיע קודם לכן, "מבין כל ששה אנשים, או שיש שלושה המכירים זה את זה, או שיש שלושה שאף אחד מהם אינו מכיר אף אחד אחר", עם חמישה אנשים במקום ששה.
• (נסה להוכיח ששתי הטענות נכונות: מכל ששה אנשים יש שלושה מכרים או שלושה זרים, אבל לא מכל חמישה).

תרגיל. נניח שלכל ספר יש נושא מוגדר, וכל ספריה כוללת אגף אחד או יותר. אגף של ספריה הוא שלם, אם לכל נושא יש מדף שכל הספרים בו עוסקים בנושא זה. ספריה מוצלחת היא ספריה שיש בה אגף שלם.

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

על מה מכמתים

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

דוגמא. הפסוק [math]\displaystyle{ \ (\exists x: x=x) \wedge (\forall x,y: x=y) }[/math] מקבל ערך אמת אם במרחב הכימות יש בדיוק ערך אחד. תרגיל. כתוב פסוק שיקבל ערך אמת רק אם מרחב הכימות הוא בן שני ערכים. תרגיל. כתוב פסוק שיקבל ערך אמת רק אם מרחב הכימות הוא בן שלושה ערכים.

התרגיל הבא יהיה, בשלב זה, קשה מאד לפתרון: תרגיל. נסה לתכנן פסוק שיקבל ערך אמת רק אם מרחב הכימות הוא סופי.

הבעיה היא שעד כה הרשינו לכתוב [math]\displaystyle{ \ \forall x_1,x_2,x_3 }[/math] בתור קיצור ל-[math]\displaystyle{ \ \forall x_1 \forall x_2 \forall x_3 }[/math], ובקלות אפשר לנחש למה הכוונה גם בביטוי כמו [math]\displaystyle{ \ \forall x_1,\dots,x_{100} }[/math] (למרות שלא נעים לכתוב אותו במפורש). אבל איננו יכולים לכתוב [math]\displaystyle{ \ \exists n: \forall x_1,\dots,x_n: Q(x_1,\dots,x_n) }[/math] (זה אינו קיצור של שום דבר). כשנרכוש נסיון מסויים בתורת הקבוצות נראה שאפשר לעקוף את הבעיה הזו די בקלות (הרעיון הוא שאפשר לכמת על אובייקט אחד - פונקציה המוגדרת על המספרים הטבעיים - במקום על מספר לא ידוע של אובייקטים). מאידך, כימות של פונקציה (או אובייקטים דומים לזה) הוא דבר מסובך בפני עצמו: הוא גורם שהפסוק כבר לא יהיה שייך ל"שפה מסדר ראשון". על כך - בקורס בלוגיקה מתמטית, ולא כאן.

ניתן דוגמא נוספת שבה נחוץ לכמת על משתנים שמספרם אינו ידוע מראש. תרגיל. אחת הדרכים להגדיר את המבנה הקומבינטורי החשוב גרף היא לחשוב עליו כעל פרדיקט סימטרי P בשני משתנים (את הסימטריה הגדרנו קודם לכן). גרפים אפשר לצייר, על-ידי מתיחת קשת בין שני קודקודים x,y בדיוק כאשר הפרדיקט [math]\displaystyle{ \ P(x,y) }[/math] מקבל ערך אמת T.

• נסח את הפסוק "בגרף אין משולשים".
• גרף שאין בו לולאות נקרא עץ. נסח את הפסוק "גרף זה הוא עץ", עבור הגרף P.

תרגיל. אומרים שקבוצת וקטורים A היא תלויה לינארית אם יש בה אברים [math]\displaystyle{ \ v_1,...,v_n }[/math], כך שקיימים קבועים [math]\displaystyle{ \,a_1,...,a_n }[/math] שלא כולם אפס, כך ש-[math]\displaystyle{ a_1v_1+...+a_nv_n=0 }[/math]. כתוב במפורש את הטענה "הוקטורים [math]\displaystyle{ \ v_1,v_2,v_3 }[/math] אינם תלויים לינארית".

תרגיל. כתוב את שלילת הטענה הבאה: לכל [math]\displaystyle{ a\in A }[/math] קיים [math]\displaystyle{ b \in B }[/math] כך ש [math]\displaystyle{ b\notin A \setminus \{a\} }[/math] וגם הקבוצה [math]\displaystyle{ (A\setminus\{a\})\cup \{b\} }[/math] בלתי תלויה לינארית.

פתרון: קיים [math]\displaystyle{ a\in A }[/math] כך שלכל [math]\displaystyle{ b \in B }[/math] מתקיים [math]\displaystyle{ b\in A \setminus \{a\} }[/math] או [math]\displaystyle{ (A\setminus\{a\})\cup \{b\} }[/math] תלויה לינארית.

• המשיכו לחלק השלישי.