מכפלה קרטזית

שעור תשיעי - מכפלה קרטזית

המושג הבא שנפגוש מבוסס על רעיון גאומטרי פשוט: כדי לתאר מלבן מישורי, שצלעותיו ניצבות לצירים, יש לתאר כל קואורדינטה בנפרד. למשל, כדי לבדוק אם אנחנו נמצאים בקבוצת הבלוקים במנהטן הנמצאים בין הרחוב ה-18 לרחוב ה-23 ובין השדרה ה-7-ית לשדרה ה-9-ית, עלינו לבדוק - בנפרד! - האם אנחנו ברחוב שבין 18 ל-23, והאם אנחנו בשדרה שבין ה-7-ית ל-9-ית. כמובן, המפתח להגדרה הוא הזוג הסדור שבנינו בשעור הקודם.

הגדרה. המכפלה הקרטזית של הקבוצות A ו-B היא הקבוצה $\ A\times B$ שאבריה הם כל הזוגות הסדורים $\ (a,b)$ עם $\ a\in A$ ו- $\ b\in B$.

דוגמא. $\ \{1\}\times \{2,6,7\}=\{(1,2),(1,6),(1,7)\}$, ו- $\ \{0,2\}\times \{0,3\}=\{(0,0),(0,3),(2,0),(2,3)\}$.

תרגיל. הוכח שהמכפלה הקרטזית $\ A\times B$ היא הקבוצה הריקה אם ורק אם אחד הגורמים A או B הוא הקבוצה הריקה.

אם בקבוצה A יש n אברים ובקבוצה B יש m אברים, אז במכפלה הקרטזית $\ A\times B$ יש nm אברים (בדוק טענה זו עבור ערכים קטנים של n ו-m). את העובדה הזו אפשר להוכיח באינדוקציה. אפשר גם להיפך - להגדיר את המכפלה של שני מספרים טבעיים, כמספר הזוגות הסדורים במכפלה קרטזית של קבוצות בגודל המתאים. דיון בהבדל שבין שתי הגישות (והקשר שלהן למערכת פאנו ואריתמטיקה של סודרים) נמצא מחוץ לגבולות הקורס הקצר שלנו.

תרגיל. הוכח שהזוג הסדור $\ (a,b)$ (שהוא, כזכור, הקבוצה $\ \{\{a\},\{a,b\}\}$) מוכל בקבוצת החזקה $\ P(\{a,b\})$, ושייך לקבוצת החזקה שלה, $\ P(P(\{a,b\}))$.

טענה. לכל שתי קבוצות A,B, המכפלה הקרטזית $\ A\times B$ מוכלת בקבוצת החזקה $\ P(A\cup B)$, ושייכת לקבוצת החזקה שלה, $\ P(P(A\cup B))$.

הוכחה. כדי להוכיח ש- $\ A\times B\subseteq P(A\cup B)$ עלינו לבדוק שכל זוג סדור $\ (a,b)\in A\times B$ שייך לקבוצה $\ P(A\cup B)$; אבל לפי התרגיל הקודם, הזוג הסדור שייך ל- $\ P(\{a,b\})$ המוכלת ב- $\ P(A\cup B)$ משום ש- $\ \{a,b\}\subseteq A\cup B$. כתת-קבוצה של $\ P(A\cup B)$, ברור ש- $\ A\times B\in P(P(A\cup B))$.

<< השיעור הקודם - זוגות סדורים

דף הקורס - תורת הקבוצות

השיעור הבא - פונקציות >>