מבנה יצירה

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

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

דיון פורמלי

מבנה יצירה הוא מערכת בעלת המרכיבים הבאים:

א. קבוצה לא ריקה K (המכונה "העולם של המבנה", אבריה מכונים "עצמים").

ב. קבוצה $D\subseteq K$ (איבריה מכונים "היוצרים של המבנה").

ג. קבוצה יחסים על K שכל אחד מהם דו-מקומי לפחות (מכונים בקיצור "היחסים").

נגדיר גם:

1. פונקציה במבנה – כינוי ליחס n+1 מקומי במבנה, אשר הוא פונקציה n-מקומית.

2. פעולה במבנה – פונקציה במבנה המוגדרת על כל העולם של המבנה.

3. עץ בניה במבנה – עץ G המיושב באברים של K, בו כל $x\in G$ מקיים:

א. אם x עלה, אז ב-x יושב איבר של D.

ב. אם ל-x יש n>0 בנים, ב-x יושב עצם a, ובבן ה-i-י יושב עצם $\ b_{i}$ - אז קיים במבנה יחס R כך ש-$(b_{1},b_{2},...,b_{i},a)\in R$.

4. עצם נוצר – איבר של K שיש לו עץ-בנייה.

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

אם כל יחס במבנה יצירה הוא פעולה, אומרים שמבנה היצירה הוא אלגברת יצירה, ואם גם כל עצם הנוצר במבנה הוא בעצמו יוצר, או שקיימים: מספר טבעי יחיד n>0, עצמים נוצרים יחידים $(b_{1},b_{2},...,b_{n})$ ופעולה n-מקומית יחידה F במבנה, שעבורם $(a=F(b_{1},b_{2},...,b_{n}$ - אז אלגברת היצירה מכונה אלגברת יצירה חופשית.

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

דוגמאות

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

• מבנה יצירה של המספרים הטבעיים מ-0 – הוא מבנה שעולמו קבוצת כל המספרים הממשיים, יש לו רק יוצר אחד, שהוא 0, וקבוצת היחסים בו כוללת רק פעולה אחת, והיא פעולת העוקב: S(x)=x+1. מבנה זה הוא אלגברת-יצירה חופשית.

• מבנה היוצר תת-מרחב וקטורי – הוא מבנה שעולמו הוא מרחב-וקטורי n ממדי, יש בו k יוצרים שהם וקטורים במרחב, ופעולותיו הם: פעולה דו-מקומית שהיא חיבור וקטורי, ופעולה חד-מקומית לכל מספר a בשדה מעליו מוגדר המרחב, שהיא הכפל ב-a. מבנה זה הוא אלגברת-יצירה-חופשית אם ורק אם הווקטורים הינם בלתי-תלויים לינארית במרחב.

ראו גם

• לוגיקה מתמטית
• שפה פורמלית