%% LyX 2.1.1 created this file. For more info, see http://www.lyx.org/. %% Do not edit unless you really know what you are doing. \documentclass[english,hebrew]{article} \usepackage[T1]{fontenc} \usepackage[latin9,cp1255]{inputenc} \usepackage{amsmath} \usepackage{amssymb} \PassOptionsToPackage{normalem}{ulem} \usepackage{ulem} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. %% Because html converters don't know tabularnewline \providecommand{\tabularnewline}{\\} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. \usepackage{theorem} \theorembodyfont{\upshape} \newtheorem{theorem}{\R{משפט}}[section] \AtBeginDocument{\make@lr\thetheorem} % The following chunk fixes export with XeTeX. % It is needed because polyglossia is used by default % and \make@lr is only defined by babel. \@ifundefined{make@lr} {\def\make@lr#1{\begingroup \toks@=\expandafter{#1}% \edef\x{\endgroup \def\noexpand#1{\noexpand\@number{\the\toks@}}}% \x}}{\relax} \newtheorem{claim}[theorem]{\R{טענה}} \newenvironment{proof}% {\R{\textbf{הוכחה:}}}% {\hfill\rule{2mm}{2mm}\par\vspace{2mm}} \newtheorem{definition}[theorem]{\R{הגדרה}} \newtheorem{lemma}[theorem]{\R{למה}} \newtheorem{corollary}[theorem]{\R{מסקנה}} \newtheorem{remark}[theorem]{\R{הערה}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. \date{} \makeatother \usepackage{babel} \begin{document} \title{אי שלמות ואי כריעות בשפות פורמליות\\ ד\char`\"{}ר אסף חסון, אוניברסיטת בן-גוריון בנגב} \author{יובל אדם} \maketitle \selectlanguage{english}% \inputencoding{latin9}\begin{minipage}[t]{1\columnwidth}% \selectlanguage{english}% \begin{quote} Young man, in mathematics you don't understand things.\\ You just get used to them. \begin{quote} - John von Neumann\end{quote} \end{quote} % \end{minipage} \selectlanguage{hebrew}% \inputencoding{cp1255}\tableofcontents{} \section{פרולוג} \begin{itemize} \item מספור הקטעים תואם למספור ההרצאות. )נשאיר כתרגיל לקורא החרוץ להבין מה זה אומר על פרק זה...( \item נא להתחשב בסביבה. נא להדפיס מסמך זה רק אם הדבר הכרחי, ורק את טווח העמודים הנדרש. \item תודה לצביקה סקופינסקי על סיכומים של חלק מהשיעורים. \item הערות/טענות/בקשות - כתובת המייל שלי היא \L{$yuv.adm$} ולאחר מכן \L{$gmail.com$} \item שאו ברכה, עלו והצליחו. \end{itemize} \section{הגדרות} \begin{itemize} \item יהי \L{$\mathcal{M}$} מבנה לשפה מסדר ראשון \L{$L$}, \L{$s$} השמה ל\L{$\mathcal{M}$} ו-\L{$t$} שם עצם. אז הערך של \L{$t$} ב-\L{$\mathcal{M}$} עבור ההשמה \L{$s$} הוא: \item אם \L{$t$} קבוע אישי \L{$c$} אז \L{$Val_{\mathcal{M}}(t,s)=c^{\mathcal{M}}$} \item אם \L{$t$} משתנה אישי \L{$x$} אז \L{$Val_{\mathcal{M}}(t,s)=s(x)$} \item אם \L{$t=f(t_{1},...,t_{n})$} אז \L{$Val_{\mathcal{M}}(t,s)=f^{\mathcal{M}}(Val_{\mathcal{M}}(t_{1},s),...,Val_{\mathcal{M}}(t_{n},s))$} \item \noindent יהיו \L{$\mathcal{M}$}, \L{$L$} , ו-\L{$s$} כנ\char`\"{}ל ותהי \L{$\varphi$} נוסחה ב-\L{$L$} אז ערך האמת של )\inputencoding{latin9}\L{TRUE}\inputencoding{cp1255} או \inputencoding{latin9}\L{FALSE}\inputencoding{cp1255}( של \L{$\varphi$} ב\L{$\mathcal{M}$} עבור ההשמה \L{$s$} מוגדר באינדוקציה באופן הבא: \begin{itemize} \item \noindent אם \L{$\varphi$} נוסחה אטומית, כלומר \L{$\varphi$} מהצורה \L{$R(t_{1},...,t_{n})$} עבור הסימן יחס n-מקומי \L{$R$} ושמות עצם \L{$t_{1},...,t_{n}$} אזי \L{ \begin{eqnarray*} Val_{\mathcal{M}}(\varphi,s) & = & TRUE\iff\left\langle Val_{\mathcal{M}}(t_{1},s),...,Val_{\mathcal{M}}(t_{n},s)\right\rangle \in R^{\mathcal{M}} \end{eqnarray*} }. \item \noindent אם \L{$\varphi=\neg\psi$} עבור נוסחה \L{$\psi$} אז \L{ \begin{eqnarray*} Val_{\mathcal{M}}(\varphi,s) & = & TRUE\iff Val_{\mathcal{M}}(\psi,s)=FALSE \end{eqnarray*} } \item \noindent באופן דומה עבור יתר הקשרים הלוגיים \item \noindent אם \L{$\varphi=(\exists x)\psi$} )כלומר הנוסחה היא מסוג \char`\"{}קיים איקס\char`\"{} וההמשך הוא נוסחה קטנה יותר( אז \L{ \begin{eqnarray*} Val_{\mathcal{M}}(\varphi,s) & = & TRUE\iff(\exists a\in M)Val_{\mathcal{M}}(\psi,s\left[{x\atop a}\right])=TRUE \end{eqnarray*} } כאשר \L{$s\left[{x\atop a}\right]$} הינה ההשמה אשר נותנת לכל משתנה אישי \L{$y$} שאינו \L{$x$} את הערך \L{$s(y)$} ולמשתנה האישי \L{$x$} את הערך \L{$a$} )כלומר רק מחליפה את \L{$x$}(. הגדרה שקולה: \L{ \begin{eqnarray*} Val_{\mathcal{M}}(\varphi,s) & = & TRUE\iff max\left\{ Val_{\mathcal{M}}(\psi,s\left[{x\atop a}\right]):a\in\mathcal{M}\right\} \end{eqnarray*} } כאשר נגדיר שרירותית \L{$Fk_{1} \end{cases} \end{eqnarray*} }מכיוון ש-\L{$\Theta_{i}\in\Gamma$} לכל \L{$i$} גמרנו. \L{$\Gamma^{\prime}$} היא המועמדת שלנו לספק את הטענה ונותר להראות ש\L{$\Gamma\equiv\Gamma^{\prime}$}. מספיק להראות שאם \L{$\mathcal{M}\models\Gamma$} אז \L{$\mathcal{M}\models\Gamma^{\prime}$}. יהי \L{$\psi\in\Gamma^{\prime}$} ונניח כמו קודם \L{$\psi={\displaystyle \bigwedge_{i=1}^{k}}\varphi_{i}$} עבור \L{$\varphi_{i}\in\Gamma$} כלשהו. אזי:\L{ \begin{eqnarray*} Val_{\mathcal{M}}(\psi) & = & Val_{\mathcal{M}}(\bigwedge\varphi_{i})=t_{\wedge}(Val_{\mathcal{M}}(\varphi_{1}),...Val_{\mathcal{M}}(\varphi_{k}))=TRUE \end{eqnarray*} } מתקיים אמ\char`\"{}ם לכל \L{$1\le i\le k$} \L{$Val_{\mathcal{M}}(\varphi_{i})=TRUE$}. כיוון ש\L{$\mathcal{M}\models\Gamma$} אז \L{$\mathcal{M}\models\varphi_{i}$} לכל \L{$i$} ולכן \L{$\mathcal{M}\models\psi$}. \end{proof} \begin{definition} קבוצת פסוקים \L{$\Gamma$} נקראת ספיקה מקומית אם כל תת קבוצה סופית שלה היא ספיקה.\end{definition} \begin{theorem} )משפט הקומפקטיות - נוסח שקול( קבוצת פסוקים \L{$\Gamma$} היא ספיקה מקומית אם ורק אם היא ספיקה.\end{theorem} \begin{proof} נוכיח שמשפט הקומפקטיות גורר את הנוסח הזה. תהי \L{$\Gamma$} קבוצת פסוקים ספיקה מקומית. תהי \L{$\Gamma^{\prime}$} כמובטח בטענה, כלומר \L{$\Gamma^{\prime}\equiv\Gamma$} ו\L{$\Gamma^{\prime}$} סגורה תחת \L{$\wedge$}. מספיק להראות לפי משפט הקומפקטיות שכל פסוק ב\L{$\Gamma^{\prime}$} הוא ספיק. יהי \L{$\psi\in\Gamma^{\prime}$} אז \L{${\displaystyle \psi=\bigwedge_{i=1}^{k}\varphi_{i}}$} לאיזה \L{$\varphi_{1},...,\varphi_{k}\in\Gamma$} . לפי ההנחה \L{$\Gamma$} ספיקה מקומית. לכן \L{$\{\varphi_{1},...,\varphi_{k}\}$} קבוצת פסוקים ספיקה. לכן יש מודל \L{$\mathcal{M}\models\varphi_{i}$} לכל \L{$1\le i\le k$} לפי מה שהראנו בהוכחת הטענה \L{$\mathcal{M}\models\psi$}. לכן \L{$\Gamma^{\prime}$} סגורה תחת חיתוך וכל \L{$\psi\in\Gamma^{\prime}$} ספיק. לפי משפט הקומפקטיות עבור \L{$\Gamma^{\prime}$} יש \L{$\mathcal{M}\models\Gamma^{\prime}$} אבל \L{$\Gamma\equiv\Gamma^{\prime}$} לכן \L{$\mathcal{M}\models\Gamma^{\prime}$}. נוכיח את הכיוון השני )שהנוסח הזה גורר את משפט הקומפקטיות(. נניח \L{$\Gamma$} מקיימת את ההנחות כלומר \L{$\Gamma^{\prime}$} סגורה תחת \L{$\wedge$} וכל פסוק בה ספיק. יספיק להראות בעזרת הנוסח השקול ש\L{$\Gamma$} ספיקה מקומית. נוכיח באינדוקציה על \L{$k$} שכל קבוצת פסוקים מגודל \L{$k$} ב-\L{$\Gamma$} היא ספיקה. עבור \L{$k=1$} - נתון. נניח ש\L{$\{\varphi_{1},...,\varphi_{k}\}\subseteq\Gamma$} והראנו עבור כל קבוצת פסוקים מגודל \L{$k-1$} שהיא ספיקה. כיוון ש\L{$\Gamma$} סגורה תחת חיתוך \L{$\varphi_{1}\wedge\varphi_{2}\in\Gamma$} . \L{$\Delta=\{\varphi_{1}\wedge\varphi_{2},\varphi_{3},...,\varphi_{k}\}$} היא קבוצה בגודל \L{$k-1$} ולכן לפי הנחת האינדוקציה היא ספיקה. אם \L{$\mathcal{M}\models\Delta$} אז \L{$\mathcal{M}\models\varphi_{i}$} לכל \L{$i\ge3$} וכן \L{$\mathcal{M}\models\varphi_{1}\wedge\varphi_{2}$} . אבל \L{$\mathcal{M}\models\varphi_{1}\wedge\varphi_{2}\iff\mathcal{M}\models\varphi_{1}\wedge\mathcal{M}\models\varphi_{2}$} ולכן \L{$\mathcal{M}\models\{\varphi_{1},...,\varphi_{k}\}$} כנדרש. כלומר \L{$\Gamma$} ספיקה מקומית וע\char`\"{}ס הנוסח השקול - ספיקה.\end{proof} \begin{definition} תהי \L{$I$} קבוצה )בד\char`\"{}כ אינסופית אבל לא בהכרח(. מסנן )\inputencoding{latin9}\L{filter}\inputencoding{cp1255}( על \L{$I$} זו קבוצה \L{$F\subseteq\mathbb{P}(I)$} )כלומר אוסף של תת קבוצות של \L{$I$}( כך שמתקיים: \begin{enumerate} \item \L{$\emptyset\not\in F$} \item אם \L{$J\in F$} ו-\L{$J\subseteq J^{\prime}$} אז \L{$J^{\prime}\in F$} \item אם \L{$J,J^{\prime}\in F$} אז \L{$J\cap J^{\prime}\in F$} \end{enumerate} אם בנוסף לכל \L{$J\subseteq I$} אם \L{$J\not\in F$} אז \L{$I\backslash J\in F$} - אז \L{$F$} נקרא על מסנן. \end{definition} דוגמאות: \begin{itemize} \item תהי \L{$I$} קבוצה כלשהי. לכל \L{$a\in I$} נגדיר על מסנן \L{$F_{a}$} באופן הבא: \L{$J\subseteq I,J\in F$} אמ\char`\"{}ם \L{$a\in J$} .)הערה: על מסנן \L{$F$} על \L{$I$} נקרא ראשי אם קיים \L{$I$} כך ש-\L{$F=F_{a}$}(. \item אם \L{$I$} סופית אז כל על מסנן על \L{$I$} הוא ראשי. יהי \L{$F$} על מסנן על \L{$I$}. כיוון ש-\L{$I$} סופית גם \L{$F$} סופית ולכן באינדוקציה לפי {\beginL 3\endL}: \L{$J_{F}=\{\bigcap J:J\in F\}$} ו-\L{$J_{F}\in F$}. אם \L{$J_{F}$} יחידון - גמרנו. נניח בשלילה שזה לא המקרה. אחרת יש {\beginL 2\endL} איברים שונים ב\L{$J_{F}$} )לפחות(. ניקח \L{$J\subseteq I$} שמכילה את הראשון אבל לא את השני. לא \L{$J$} ולא המשלים של \L{$J$} יכולים להיות ב\L{$F$} כי כל קבוצה ב\L{$F$} מכילה את \L{$J_{F}$}. \item תהי \L{$I$} קבוצה אינסופית. נגדיר \L{$F=\{U\subseteq I:|I\backslash U|<\aleph_{0}(finite)\}$}. תרגיל: זהו מסנן שאינו על מסנן. \end{itemize} \begin{claim} תהי \L{$I$} קבוצה לא ריקה. \L{$F$} מסנן על \L{$I$} אזי קיים על מסנן \L{$F\subseteq F^{\prime}$}. במילים אחרות כל מסנן על \L{$I$} ניתן להרחבה לעל מסנן. )הוכחה בשיעור הבא(. \end{claim} \section{מסננים והלמה של צורן} \begin{definition} תהי \L{$I$} קבוצה )לא ריקה( אז \textbf{מסנן} \L{$F$} על \L{$I$} זה אוסף של תת קבוצות של \L{$I$} כך ש: \begin{enumerate} \item \L{$\emptyset\not\in F$} \item אם \L{$U_{1},U_{2}\in F$} אז \L{$U_{1}\wedge U_{2}\in F$} \item אם \L{$U\in F$} ו- \L{$U\subseteq V$} אז \L{$V\in F$} \end{enumerate} \L{$F$} הוא על-מסנן אם לכל \L{$V\subseteq I$} אם \L{$V\not\in F$} אז \L{$I\backslash V\in F$} . \end{definition} \begin{lemma} \uline{הלמה של צורן} - תהי \L{$(I,\le)$} קבוצה סדורה חלקית. \L{$V\subseteq I$} תקרא שרשרת אם לכל \L{$v_{1},v_{2}\in V$} או \L{$v_{1}\le v_{2}$} או \L{$v_{2}\le v_{1}$}. אז נניח שלכל שרשרת \L{$V\subseteq I$} יש חסם מלעיל, כלומר קיים \L{$w\in I$} כך ש-\L{$w\ge V$} )כלומר \L{$w\ge v$} לכל \L{$v\in V$}(. אזי ב\L{$(I,\le)$} יש איבר מירבי, כלומר קיים \L{$u\in I$} כך שלכל \L{$u\not=v\in I$} מתקיים \L{$u\not\le v$}.\end{lemma} \begin{claim} תהי \L{$I$} קבוצה לא ריקה ו- \L{$F$} מסנן על \L{$I$}. אזי קיים על-מסנן \L{$F\subseteq U$}. במילים אחרות, כל מסנן \L{$F$} על \L{$I$} ניתן להרחבה לעל-מסנן. \begin{proof} תהי \L{$\mathcal{H}$} קבוצת כל המסננים על \L{$I$}. לאינטואיציה: \L{$F\in\mathbb{P}(\mathbb{P}(I))$} אז \L{$\mathcal{H}\subseteq\mathbb{P}(\mathbb{P}(I)$} או \L{$\mathcal{H}\in\mathbb{P}(\mathbb{P}(\mathbb{P}(I)))$}. על \L{$\mathcal{H}$} אפשר להגדיר סדר חלקי ע\char`\"{}י הכלה. כלומר, ל-\L{$F_{1},F_{2}\in\mathcal{H}$} נאמר ש\L{$F_{1}\le F_{2}$} אם לכל \L{$V\in F_{1}$} מתקיים גם \L{$V\in F_{2}$}. אפשר לכתוב גם \L{$F_{1}\subseteq F_{2}$}. נרצה להשתמש בלמה של צורן, לכן עלינו להראות שאם \L{$V\subseteq\mathcal{H}$} שרשרת אז ל\L{$V$} יש חסם מלעיל ב\L{$\mathcal{H}$}. נגדיר \L{$F_{V}={\displaystyle \bigcup V}=\{U\subseteq I:U\in F,\, for\, some\, F\in V\}$}. נראה ש\L{$F_{V}$} הוא מסנן. \begin{enumerate} \item ברור כי \L{$\emptyset\not\in F_{V}$} \item נניח ש \L{$U_{1},U_{2}\in F_{V}$}. קיימים \L{$F_{1},F_{2}\in V$} כך ש \L{$U_{1}\in F_{1}$} וגם \L{$U_{2}\in F_{2}$}. כיוון ש-\L{$V$} שרשרת, ב.ה.כ \L{$F_{1}\subseteq F_{2}$} . לכן \L{$U_{1}\in F_{2}$} לכן גם \L{$U_{1}\cap U_{2}\in F_{2}$} ולכן \L{$U_{1}\cap U_{2}\in F_{V}$}. \item אם \L{$U\in F_{V}$} ו- \L{$U\subseteq W$} אז לפי הגדרה קיים איזה \L{$F\in V$} כך ש- \L{$U\in F$}. לכן גם \L{$W\in F$} ולכן \L{$W\in F_{V}$}. \end{enumerate} הראנו שלכל שרשרת ב\L{$\mathcal{H}$} יש חסם מלעיל, כי ברור \L{$F_{V}\in\mathcal{H}$} ו- \L{$F\subseteq F_{V}$} לכל \L{$F\in V$} כלומר \L{$F_{V}$} חסם מלעיל ל-\L{$V$}. לפי הלמה של צורן, ב-\L{$\mathcal{H}$} יש איבר מירבי, נסמנו \L{$\mathcal{U}$}. נראה ש\L{$\mathcal{U}$} על מסנן. נניח בשלילה שהוא לא. כיוון ש-\L{$\mathcal{U}\in\mathcal{H}$} הוא מסנן ולכן הנחת השלילה מבטיחה שיש קבוצה \L{$U\subseteq I$} כך ש- \L{$U\not\in\mathcal{U}$} ו- \L{$I\backslash U\not\in\mathcal{U}$}. נשים לב כי במקרה זה \L{$\mathcal{U}_{U}=\mathcal{U}\cup\{W\subseteq I:U\cap V\subseteq W,\, for\, some\, V\in\mathcal{U}\}$} הוא מסנן וזאת תהיה סתירה למירביות של \L{$\mathcal{U}$} כי \L{$\mathcal{U}\not\subseteq\mathcal{U}_{U}$}. מדוע \L{$\mathcal{U}_{U}$} הוא מסנן? \begin{enumerate} \item נוכיח ש\L{$\emptyset\in\mathcal{U}_{U}$}. אם \L{$\emptyset\in\mathcal{U}_{U}$} הרי שהיא מהצורה \L{$U\cap V$} לאיזה \L{$V\in\mathcal{U}$}. אבל אז \L{$V\subseteq I\backslash U$} ואז \L{$I\backslash U\in\mathcal{U}$} בסתירה. \item \L{$\mathcal{U}_{U}$} סגורה כלפי מעלה מעצם הגדרתה. \item נראה כי אם \L{$U_{1},U_{2}\in\mathcal{U}_{U}$} אז גם \L{$U_{1}\cap U_{2}\in\mathcal{U}_{U}$}. ב.ה.כ \L{$U_{1}\not\in\mathcal{U}$}. לכן \L{$U\cap V\subseteq U$} לאיזה \L{$V\in\mathcal{U}$}. לכן \L{$U\cap V\cap U_{2}\subseteq U_{2}\cap U_{1}$} עבור \L{$V$} הזו. אם \L{$U_{2}\in\mathcal{U}$} אז \L{$V\cap U_{2}\in\mathcal{U}$} ולכן \L{$U\cap(V\cap U_{2})\in\mathcal{U}_{U}$} וכך גם \L{$U_{1}\cap U_{2}$}. אחרת \L{$U\cap V_{2}\subseteq U_{2}$} לאיזה \L{$V_{2}\in\mathcal{U}$} . ואז \L{$U\cap(V\cap V_{2})\subseteq U_{1}\cap U_{2}$} וגם \L{$U\cap(V\cap V_{2})\in\mathcal{U}_{U}$}. קיבלנו \L{$\mathcal{U}_{U}\in\mathcal{H}$} ו-\L{$\mathcal{U}\not\in\mathcal{U}_{U}$} סתירה. לכן \L{$\mathcal{U}$} על מסנן. \end{enumerate} )הרחבה( אם \L{$F$} מסנן על \L{$I$} נגדיר \L{$\mathcal{H}_{F}\subseteq\mathcal{H}$} אוסף המסננים המכילים את \L{$F$}. באופן טריויאלי לכל שרשרת ב-\L{$\mathcal{H}_{F}$} יש חסם מלעיל ב-\L{$\mathcal{H_{F}}$})כי כל שרשרת כזו היא שרשרת של איברים שגדולים מ-\L{$F$} ולכן אם יש לה חסם ב\L{$\mathcal{H}$} הרי שהוא חסם ב\L{$\mathcal{H}_{F}$}. לכן \L{$\mathcal{H}_{F}$}מקיימת את הלמה של צורן, לכן יש איבר מירבי גם ב\L{$\mathcal{H}$}וראינו שאלו על מסננים. \end{proof} \begin{corollary} לכל קבוצה אינסופית \L{$I$} יש על מסנן \L{$F$} על \L{$I$} כך שאם \L{$|I\backslash U|<\aleph_{0}$} אז \L{$U\in F$}.\end{corollary} \begin{definition} \uline{מכפלות}: תהי \L{$\Gamma$}קבוצה לא ריקה כלשהי ו-\L{$\{M_{\gamma}\}_{\gamma\in\Gamma}$} אוסף של קבוצות לא ריקות. אז המכפלה \L{${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$} זה אוסף כל הפונקציות \L{$f:\Gamma\rightarrow{\displaystyle \bigcup_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$} המקיימות \L{$f(\gamma)\in\mathcal{M}_{\gamma}$}. הערה: אם \L{$\Gamma=\{1,...,n\}$} ו-\L{$\mathcal{M}_{i}=\mathcal{M}_{j}$} לכל \L{$i,j$} אז \L{${\displaystyle \prod_{i=1}^{n}\mathcal{M}=\mathcal{M}^{n}}$}.\end{definition} \begin{theorem} \uline{אקסיומת הבחירה}: אם \L{$\Gamma$}לא ריקה ו-\L{$\mathcal{M}_{\gamma}\not=\emptyset$} לכל \L{$\gamma\in\Gamma$} אז \L{${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}\not=\emptyset}$}. \end{theorem} \section{מכפלות} \end{claim} \begin{definition} \uline{מכפלות}: תהי \L{$\Gamma$} קבוצה לא ריקה כלשהי ו-\L{$\{M_{\gamma}\}_{\gamma\in\Gamma}$} אוסף של קבוצות לא ריקות. אז המכפלה \L{${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$} זה אוסף כל הפונקציות \L{$f:\Gamma\rightarrow{\displaystyle \bigcup_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$} המקיימות \L{$f(\gamma)\in\mathcal{M}_{\gamma}$}. הערה: אם \L{$\Gamma=\{1,...,n\}$} ו-\L{$\mathcal{M}_{i}=\mathcal{M}_{j}$} לכל \L{$i,j$} אז \L{${\displaystyle \prod_{i=1}^{n}\mathcal{M}=\mathcal{M}^{n}}$}. דוגמה: אם \L{$\mathcal{M}_{\gamma}=\mathcal{M}$} לכל \L{$\mathcal{M}$} אז \L{${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}=M^{\Gamma}}$}זה פשוט אוסף כל הפונקציות מ\L{$\Gamma$} ל\L{$\mathcal{M}$}. \end{definition} ~ \begin{definition} אם \L{$\Gamma$}לא ריקה ו-\L{$\mathcal{M}_{\gamma}\not=\emptyset$} לכל \L{$\gamma\in\Gamma$}. תהי \L{$\mathcal{M}=\prod\mathcal{M}_{\gamma}$}. ל\L{$\bar{x},\bar{y}\in\mathcal{M}$} נגדיר \L{$x\sim_{F}y$} עבור על מסנן \L{$F$} על \L{$\Gamma$} אם \L{$\{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{y}(\gamma)\}\in F$}. \end{definition} \begin{claim} בסימונים של ההגדרה האחרונה \L{$\sim_{F}$} הוא יחס שקילות. \end{claim} \begin{proof} ~ \begin{enumerate} \item \L{$\{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{y}(\gamma)\}=\Gamma\in F$} \begin{enumerate} \item \L{$\{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{y}(\gamma)\}=\{\gamma\in\Gamma:\bar{y}(\gamma)=\bar{x}(\gamma)\}$} \item נניח ש\L{$x\sim_{F}y$} ו-\L{$y\sim_{F}z$} אז \L{ \begin{eqnarray*} U & = & \{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{y}(\gamma)\}\in F \end{eqnarray*} } וגם \L{ \begin{eqnarray*} V & = & \{\gamma\in\Gamma:\bar{y}(\gamma)=\bar{z}(\gamma)\}\in F \end{eqnarray*} } לכן \L{$U\cap V\in F$} אבל \L{$U\cap V\subseteq\{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{z}(\gamma)\}\in F$}. \end{enumerate} \end{enumerate} \end{proof} \begin{definition} תהי \L{$\Gamma$} קבוצה לא ריקה ולכל \L{$\gamma\in\Gamma$} יהי \L{$\mathcal{M}_{\gamma}$} מבנה לשפה \L{$\mathcal{L}$}. יהי \L{$F$} על מסנן )לא ראשי( על \L{$\Gamma$} אז העל מכפלה של \L{$\{\mathcal{M}_{\gamma}\}_{\gamma\in\Gamma}$} ביחס ל\L{$F$} שתסומן \L{$\mathcal{M=}({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})/F$} היא המבנה המוגדר כלהלן: \end{definition} \begin{enumerate} \item העולם של העל מכפלה הוא \L{$({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})/\sim_{F}$} כלומר אוסף מחלקות השקילות של היחס \L{$\sim_{F}$} על המכפלה \L{$({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})$} \item לכל קבוע אישי \L{$c\in\mathcal{L}$} נפרש \L{$[(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}]$} מחלקת השקילות של הסדרה \L{$(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}$} ביחס ל \L{$\sim_{F}$}. \item לכל סימן יחס n-מקומי \L{$R\in\mathcal{L}$} . נאמר ש\L{$[\bar{a_{1}},...,\bar{a_{n}}]\in R^{\mathcal{M}}$} אם \L{$\{\gamma\in\Gamma:(\bar{a_{1}}(\gamma),...,\bar{a_{n}}(\gamma))\in R^{\mathcal{M}_{\gamma}}$} . \item לכל סימן פונקציה n-מקומי \L{$F$}נאמר ש\L{$F^{\mathcal{M}}[(\bar{a_{1}},...,\bar{a_{n})}]=[b]$} אם \L{$\{\gamma\in\Gamma:F^{\mathcal{M}_{\gamma}}(\bar{a_{1}}(\gamma),...,\bar{a_{n}}(\gamma))=b(\gamma)\}\in F$} . הערה: הנ\char`\"{}ל מוגדר היטב. כלומר אם \L{$[b]=[d]$} אז \L{ \begin{eqnarray*} & & \underset{\in F}{\underbrace{\underset{\in F}{\underbrace{\{\gamma\in\Gamma:F^{\mathcal{M}_{\gamma}}(\bar{a_{1}}(\gamma),...,\bar{a_{n}}(\gamma))=b(\gamma)\}}}\cap\underset{\in F}{\underbrace{\{\gamma\in\Gamma:d(\gamma)=b(\gamma)\}}}}}\\ & \subseteq & \underset{\in F}{\underbrace{\{\gamma\in\Gamma:F^{\mathcal{M}_{\gamma}}(\bar{a_{1}},...,\bar{a_{n}}(\gamma))=d(\gamma)\}}} \end{eqnarray*} } כי \L{$[b]=[d]$} כלומר \L{$b\sim_{F}d$} וזאת בדיוק ההגדרה. \end{enumerate} \begin{theorem} יהיו \L{$\mathcal{M}=({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})/F$} ו-\L{$\varphi(x_{1},...,x_{n})$} נוסחה ו-\L{$s$} השמה ל\L{$\mathcal{M}$}. אזי מתקיים \L{$Val_{\mathcal{M}}(\varphi,s)=TRUE$} אם ורק אם לכל השמות \L{$(s_{\gamma})_{\gamma\in\Gamma}$} )עם \L{$s_{\gamma}$} השמה ל\L{$\mathcal{M}_{\gamma}$}( כך ש \L{$[(s_{\gamma})_{\gamma\in\Gamma}]\sim_{F}[s]$} מתקיים ש \L{$\{\gamma\in\Gamma:Val_{\mathcal{M}}(\varphi,s_{\gamma})=TRUE\}\in F$}.\end{theorem} \begin{proof} באינדוקציה על יצירת הנוסחאות. נתחיל משמות עצם: \begin{itemize} \item עבור \L{$t$} קבוע אישי \L{$c$} מתקיים \L{$Val_{\mathcal{M}}(c,s)=c^{\mathcal{M}}=[(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}]=[Val_{\mathcal{M}_{\gamma}}(c,s)_{\gamma\in\Gamma}]$}. לשם נוחות נקבע השמה \L{$s_{0}$} ל-\L{${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$} כך ש-\L{$[s_{0}]=s$}. כלומר לכל משתנה אישי \L{$x$} מתקיים \L{$[s_{0}(x)]=s(x)$}. \item עבור \L{$t$} משתנה אישי \L{$x$} : \L{$Val_{\mathcal{M}}(x,s)=\underset{=[s_{\gamma}(x)]}{\underbrace{[s_{0}(x)]}}=s(x)$} \item עבור \L{$t$} פונקציה \L{$t=F(t_{1},...,t_{n})$} אז \L{ \begin{eqnarray*} Val_{\mathcal{M}}(F(t_{1},...,t_{n}),s) & = & F{}^{\mathcal{M}}(Val_{\mathcal{M}}(t_{1},s),...,Val_{\mathcal{M}}(t_{n},s))\\ & = & F^{\mathcal{M}}([Val_{\mathcal{M}_{\gamma}}(t_{1},s_{\gamma})],...,[Val_{\mathcal{M}_{\gamma}}(t_{n},s_{\gamma})])\\ & = & [F^{\mathcal{M}_{\gamma}}(Val_{\mathcal{M}_{\gamma}}(t_{1},s_{\gamma}),...Val_{\mathcal{M}_{\gamma}}(t_{n},s_{\gamma})] \end{eqnarray*} }עתה נתחיל בהוכחה עבור נוסחאות:\end{itemize} \begin{enumerate} \item אם \L{$\varphi$} נוסחה אטומית \L{$R(t_{1}(x_{1},...,x_{n}),...,t_{m}(x_{1},...,x_{n}))$} אז אם ורק אם \L{ \begin{eqnarray*} Val_{\mathcal{M}}(R(t_{1},...,t_{n}),s) & = & TRUE\\ & \iff & (Val_{\mathcal{M}}(t_{1},s),...Val_{\mathcal{M}}(t_{m},s))\in R^{\mathcal{M}}\\ & \iff & \{\gamma\in\Gamma:(Val_{\mathcal{M}}(t_{1},s)(\gamma),...,Val_{\mathcal{M}}(t_{n},s)(\gamma))\in R^{\mathcal{M}_{\gamma}}\}\in F \end{eqnarray*} } אם ורק אם לפי מה שהראנו עבור שמות עצם \L{$[Val_{\mathcal{M}}(t_{i},s)]=[(Val_{\mathcal{M}}(t_{i},s_{\gamma})(\gamma))_{\gamma\in\Gamma}]$} לכל \L{$1\le i\le m$}. לכן, \L{ \begin{eqnarray*} \{\gamma & \in & \Gamma:(Val_{\mathcal{M}}(t_{1},s_{\gamma}),...,Val_{\mathcal{M}}(t_{m},s_{\gamma}))\in R^{\mathcal{M}_{\gamma}}\}\in F\\ & & \iff\{\gamma\in\Gamma:(Val_{\mathcal{M}_{\gamma}}(t_{1},s_{\gamma}),...,Val_{\mathcal{M}_{\gamma}}(t_{m},s_{\gamma}))\in R^{\mathcal{M}_{\gamma}}\}\in F \end{eqnarray*} } וזה מה שהיינו צריכים . \end{enumerate} \end{proof} \section{משפט \L{Los} והוכחת קומפקטיות} \begin{theorem} \uline{משפט }\inputencoding{latin9}\L{\uline{Los}}\inputencoding{cp1255} תהי \L{$\mathcal{L}$} שפה לתחשיב הפסוקים, \L{$\Gamma$} קבוצה לא ריקה, לכל \L{$\gamma\in\Gamma$} מבנה \L{$\mathcal{M}_{\gamma}$} לשפה \L{$\mathcal{L}$}. יהי \L{$F$} על מסנן על \L{$\Gamma$} ו-\L{$s$} השמה עבור \L{$\mathcal{M}=({\displaystyle \prod_{\gamma}\mathcal{M}_{\gamma}}/F)$} ו- \L{$\varphi(x)$} נוסחה ב\L{$\mathcal{L}$}. אזי \L{$Val_{\mathcal{M}}(\varphi,\bar{s})=TRUE$}אם ורק אם לכל השמה \L{$s$} ל-\L{${\displaystyle \prod_{\gamma}\mathcal{M}_{\gamma}}$} המקיימת \L{$\bar{s}(x)=[s(x)]$} מתקיים: \L{ \begin{eqnarray*} \{\gamma & \in & \Gamma:Val_{\mathcal{M}_{\gamma}}(\mathcal{M}_{\gamma},s(\gamma))=TRUE\}\in F \end{eqnarray*} } )כאשר \L{$s(\gamma)(x)$} זה הקואורדינטה ה\L{$\gamma$} של \L{$s(x)$}(. \end{theorem} תזכורת: כיצד מגדירין )\char`\"{}לכבוד פסח\char`\"{} - א. חסון, חג שמח( מבנה לשפה \L{$\mathcal{L}$} על \L{${\displaystyle (\prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}/F)$}? \begin{itemize} \item עבור קבוע אישי \L{$c$} פשוט לוקחים את \L{$[(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}]$}. \item עבור סימן יחס n-מקומי \L{$R$} נקבע ש-\L{$\left\langle \bar{a}_{1},...,\bar{a}_{n}\right\rangle \in R^{\mathcal{M}}$} אם קיימים \L{$a_{1},...,a_{n}\in{\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$} כך ש \L{$[a_{1}]=\bar{a_{1}},...,[a_{n}]=\bar{a_{n}}$} כך ש-\L{ \begin{eqnarray*} \{\gamma & \in & \Gamma:(a_{1}(\gamma),...a_{n}(\gamma))\in R^{\mathcal{M}_{\gamma}}\}\in F \end{eqnarray*} } \item עבור סימן פונקציה n-מקומי \L{$F^{\mathcal{M}}(\bar{a}_{1},...,\bar{a}_{n})=b$} אם קיימים \L{$b,a_{1},...,a_{n}\in{\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$} כך ש \L{$[a_{1}]=\bar{a_{1}},...,[a_{n}]=\bar{a_{n}},[b]=b$} כך ש \L{ \begin{eqnarray*} \{\gamma & \in & \Gamma:F^{\mathcal{M}}(a_{1}(\gamma),...a_{n}(\gamma))=b(\gamma)\}\in F \end{eqnarray*} }. \end{itemize} \uline{תרגיל:} \begin{enumerate} \item להוכיח כי זה מוגדר היטב, כלומר \L{$F^{\mathcal{M}}$} היא אכן פונקציה. ז\char`\"{}א עבור \L{$\bar{a_{1}},...,\bar{a_{n}}\in\mathcal{M}$} קיים \L{$b$} יחיד כך ש\L{$F^{\mathcal{M}}(\bar{a_{1},}...,\bar{a_{n}})=b$}. \item אם \L{$[a_{1}]=\bar{a_{1}},...,[a_{n}]=\bar{a_{n}}$} אז \L{$F^{\mathcal{M}}(\bar{a_{1}},...,\bar{a_{n}})=[F^{\mathcal{M}}(a_{1}(\gamma),...,a_{n}(\gamma))_{\gamma\in\Gamma}]$}\end{enumerate} \begin{proof} ראשית נראה: אם \L{$t$} שם עצם ב\L{$\mathcal{L}$}, \L{$\bar{s},s$} השמות כבניסוח המשפט אז \L{$Val_{\mathcal{M}}(t,\bar{s})=[(Val_{\mathcal{M}_{\gamma}}(t,s(\gamma)))_{\gamma\in\Gamma}]$} באינדוקציה על יציאת \L{$t$}. \begin{itemize} \item עבור \L{$t$} קבוע אישי \L{$c$}: \L{$Val_{\mathcal{M}}(t,\bar{s})=[(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}]=[(Val_{\mathcal{M}_{\gamma}}(c,s(\gamma)))_{\gamma\in\Gamma}]$} \item עבור \L{$t$} משתנה אישי \L{$x$}: \L{$Val_{\mathcal{M}}(t,s)=\bar{s}(x)=[s(\gamma)(x)_{\gamma\in\Gamma}]=[(Val_{\mathcal{M}_{\gamma}}(t,s(\gamma)))_{\gamma\in\Gamma}]$} \item עבור \L{$t=F(t_{1},...,t_{n})$}: \L{ \begin{eqnarray*} Val_{\mathcal{M}}(f(t_{1},...t_{n}),\bar{s})\\ & = & F^{\mathcal{M}}(Val_{\mathcal{M}}(t_{1},s),...,Val_{\mathcal{M}}(t_{n},s))\\ & = & F^{\mathcal{M}}([(Val_{\mathcal{M}_{\gamma}}(t_{1},s(\gamma)))_{\gamma\in\Gamma}],...,[(Val_{\mathcal{M}_{\gamma}}(t_{n},s(\gamma)))_{\gamma\in\Gamma}]\\ & = & [F^{\mathcal{M}}(Val_{\mathcal{M}_{\gamma}}(t_{1},s(\gamma)),...,(Val_{\mathcal{M}_{\gamma}}(t_{n},s(\gamma))] \end{eqnarray*} } \end{itemize} הוכחנו עבור שמות עצם. כעת נוכיח את המשפט באינדוקציה על יצירת הנוסחה. \begin{itemize} \item עבור \L{$\varphi$} נוסחה אטומית \L{$R(t_{1},...,t_{n})$} מתקיים \L{ \begin{eqnarray*} Val_{\mathcal{M}}(R(t_{1},...t_{n}),\bar{s}) & = & TRUE\iff(Val_{\mathcal{M}}(t_{1},\bar{s}),...Val_{\mathcal{M}}(t_{n},\bar{s}))\in R^{\mathcal{M}} \end{eqnarray*} } אם ורק אם קיימים נציגים ל-\L{$Val_{\mathcal{M}}(t,\bar{s})$} נסמנם \L{$a_{1},...,a_{n}$} כך ש\L{$\{\gamma\in\Gamma:(a_{1}(\gamma),...,a_{n}(\gamma))\in R^{\mathcal{M}_{\gamma}}\}\in F$}. את מי נבחר כנציגים? לפי מה שהראנו עבור שמות עצם אפשר לבחור את \L{$(Val_{\mathcal{M}_{\gamma}}(t_{i},s(\gamma)))_{\gamma\in\Gamma}$} בתור נציגים לכל \L{$i$}. ז\char`\"{}א \L{ \begin{eqnarray*} Val_{\mathcal{M}}(\varphi,s) & = & TRUE\\ & & \iff\{\gamma\in\Gamma:(Val_{\mathcal{M}_{\gamma}}(t_{1},s(\gamma)),...,Val_{\mathcal{M}_{\gamma}}(t_{n},s(\gamma))\in R^{\mathcal{M}_{\gamma}}\} \end{eqnarray*} } )וזה בדיוק מה שמשפט \inputencoding{latin9}\L{Los}\inputencoding{cp1255} אומר(. \item עבור \L{$\varphi=\neg\psi$} מתקיים \L{ \begin{eqnarray*} Val_{\mathcal{M}}(\psi,\bar{s}) & = & TRUE\\ & \iff & \{\gamma\in\Gamma:Val_{\mathcal{M}_{\gamma}}(\psi,s(\gamma))=TRUE\}\in F\\ & \iff & \{\gamma\in\Gamma:Val_{\mathcal{M}_{\gamma}}(\psi,s(\gamma))=FALSE\}\not\in F\\ & \iff & \{\gamma\in\Gamma:Val_{\mathcal{M}_{\gamma}}(\neg\psi,s(\gamma))=TRUE\}\not\in F \end{eqnarray*} } וזה מתקיים אם ורק אם \L{ \begin{eqnarray*} Val_{\mathcal{M}}(\neg\psi,\bar{s}) & = & FALSE\iff Val_{\mathcal{M}}(\varphi,\bar{s})=FALSE \end{eqnarray*} }. \item המקרים של \L{$\varphi=\psi_{1}\square\psi_{2}$} דומים מאוד )משתמשים בתכונות של על מסנן(. \item נותר המקרה \L{$\varphi=\exists x\psi(x)$} )המקרה של \L{$\forall x$} נובע מהמקרה הנ\char`\"{}ל וממה שעבר עשינו ע\char`\"{}י השקילות הלוגית \L{$\forall x\psi(x)=\neg\exists x\neg\psi(x)$}(. \begin{itemize} \item כיוון אחד: נניח כי \L{$(\mathcal{M},s)\models(\exists x)\psi(x)$} ז\char`\"{}א שקיים \L{$\bar{a}\in\mathcal{M}$} כך ש\L{$(\mathcal{M},s)\models\psi(\bar{a})$}. נוסיף לשפה קבוע אישי חדש \L{$c$} ונרשום \L{$\psi(c)$} הנוסחה המתקבלת מ\L{$\psi$}ע\char`\"{}י החלפת של מופע חופשי של \L{$x$} בנוסחה \L{$\psi$} ב\L{$c$} . נרחב את \L{$\mathcal{M}$}למבנה לשפה המועשרת ע\char`\"{}י כך שנגדיר \L{$c^{\mathcal{M}}=\bar{a}$}. אזי \L{$Val_{\mathcal{M}}(\psi,\bar{s}[{x\atop \bar{a}}])=Val_{\mathcal{M}}(\psi(c),s)$}. אז לפי הנחת האינדוקציה: \L{ \begin{eqnarray*} Val_{\mathcal{M}}(\psi(c),\bar{s}) & = & TRUE\\ & \iff & \{\gamma\in\Gamma:Val_{\mathcal{M}_{\gamma}}(\psi(c),s(\gamma))=TRUE\}\in F\\ & \iff & \{\gamma\in\Gamma:Val_{\mathcal{M}_{\gamma}}(\psi(x),s(\gamma)([{x\atop c^{\mathcal{M}_{\gamma}}}]))=TRUE\}\in F\\ & \Rightarrow & \{\gamma\in\Gamma:Val_{\mathcal{M}_{\gamma}}(\exists x\psi(x),s(\gamma))=TRUE\}\in F \end{eqnarray*} } \item כיוון שני: נניח כי \L{$\{\gamma\in\Gamma:(M_{\gamma},s)\models(\exists x)\psi(x)\}\in F$}. נגדיר איבר \L{$a\in{\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$} באופן הבא: לכל \L{$\gamma\in\Gamma$} אם \L{$(\mathcal{M}_{\gamma},s)\models\exists x\psi(x)$} אז נבחר \L{$a_{\gamma}$} שמעיד על כך. אם \L{$(\mathcal{M}_{\gamma},s)\not\models\exists x\psi(x)$} נבחר \L{$a_{\gamma}\in\mathcal{M}_{\gamma}$} שרירותי. נגדיר \L{$\bar{a}=[a]$} . מההנחה שלנו \L{ \begin{eqnarray*} \{\gamma & \in & \Gamma:(\mathcal{M}_{\gamma},s(\gamma)[{x\atop a_{\gamma}}])\models\psi(x)\}\in F\\ & & \iff(\mathcal{M},\bar{s}[{x\atop \bar{a}}])\models\psi(x)\\ & & \iff(\mathcal{M},\bar{s})\models(\exists x)\psi(x) \end{eqnarray*} }. \end{itemize} \end{itemize} \end{proof} \begin{corollary} נניח ש\L{$\Gamma$} לא ריקה ו\L{$\mathcal{M}_{\gamma}$}מבנים לשפה \L{$\mathcal{L}$} לכל \L{$\gamma\in\Gamma$} ו-\L{$F$} על מסנן על \L{$\Gamma$}, אזי לכל פסוק \L{$\psi$} ב\L{$\mathcal{L}$} מתקיים \L{$({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})/F\models\psi$} אם ורק אם \L{$\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\in F$}. \begin{corollary} \uline{משפט הקומפקטיות}: תהי \L{$\Gamma$} קבוצה פסוקים בשפה \L{$\mathcal{L}$}. נניח שלכל \L{$\psi_{1},\psi_{2}\in\Gamma$} גם \L{$\psi_{1}\wedge\psi_{2}\in\Gamma$} ולכל \L{$\psi\in\Gamma$} קיים מודל \L{$\mathcal{M}_{\psi}\models\psi$} אזי \L{$\Gamma$} ספיקה כלומר קיים \L{$\mathcal{M}\models\Gamma$}. \end{corollary} \begin{proof} לכל \L{$\psi\in\Gamma$} נבחר מבנה \L{$\mathcal{M}_{\psi}\models\psi$}. תהי \L{$\mathcal{U}\subseteq\mathbb{P}(\Gamma)$} הקבוצה המקיימת קיים \L{$\psi\in\Gamma$}כך ש: \L{$V\in\mathcal{U}\iff\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\subseteq V$}. \end{proof} \end{corollary} \begin{claim} \L{$\mathcal{U}$} מסנן על \L{$\Gamma$} .\end{claim} \begin{proof} לכל \L{$\psi\in\Gamma$} מהנחתנו \L{$\mathcal{M}_{\psi}\models\psi$} לכן \L{$\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\not=\emptyset$}. לכן \L{$\mathcal{U}\not=\emptyset$}. ברור ש\L{$\mathcal{U}$} סגורה כלפי מעלה. נניח ש\L{$v_{1},v_{2}\in\mathcal{U}$} אזי קיימים \L{$\psi_{1},\psi_{2}\in\Gamma$} כך ש-\L{$\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi_{i}\}\subseteq V_{i}$} וזה גורר..... \L{$V_{1}\cap V_{2}\in\mathcal{U}$}. \end{proof} יהי \L{$F$} על מסנן שמרחיב את \L{$\mathcal{U}$} . לפי המסקנה מתקיים \L{$({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma})}/F\models\psi$} אם ורק אם \L{$\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\in F$}. אבל מהגדרת \L{$\mathcal{U}$} לכל \L{$\psi\in\Gamma$} הקבוצה \L{$\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\in\mathcal{U}$} ולכן ל-\L{$F$}. מש\char`\"{}ל. \section{עקביות} \begin{theorem} תהי \L{$(P,\le)$} קס\char`\"{}ח, אזי קיים יחס \L{$R$} על \L{$P$} )דו-מקומי( כך ש-\end{theorem} \begin{enumerate} \item \L{$R$} יחס סדר קווי \begin{enumerate} \item לכל \L{$a,b\in P$} אם \L{$a\le b$} אז \L{$R(a,b)$}. \end{enumerate} במילים אחרות, קיים סדר קווי \L{$R$} על \L{$P$} שמרחיב את \L{$\le$}. \end{enumerate} \begin{theorem} \uline{הערה:} המשפט עבור קבוצה סופית \L{$P$} איננו קשה. ההוכחה באינדוקציה על \L{$|P|$}. עבור \L{$|P|=1$} אין מה להוכיח. נניח שהוכחנו עבור כל \L{$P$} עם \L{$|P|=n$} ונוכיח עבור \L{$n+1$}: תהי \L{$(P,\le)$} קס\char`\"{}ח עם \L{$n+1$} איברים. כיוון ש\L{$P$} סופית יש לה איבר מינימלי \L{$a$}. תהי \L{$Q=P\backslash\{a\}$}. אז \L{$(Q,\le)$} קס\char`\"{}ח עם \L{$n$} איברים ולפי הנחת האינדוקציה יש \L{$R$} סדר קווי על \L{$Q$} שמרחיב את \L{$\le$} על \L{$Q$}. עתה לא קשה לבדוק שאם נגדיר \L{$R(a,b)$} לכל \L{$b\in Q$} נקבל את המבוקש.\end{theorem} \begin{proof} )מקרה כללי( תהי \L{$L$} שפה לתחשיב היחסים שבה: \begin{enumerate} \item לכל \L{$p\in P$} יש קבוע אישי \L{$c_{p}$} \item יחס דו מקומי \L{$R$} \end{enumerate} \uline{בלבד.} נגדיר קבוצת פסוקים \L{$T_{P}$} ב\L{$L$} באופן הבא: \begin{enumerate} \item \L{$c_{p}\not=c_{q}$} לכל \L{$p\not=q\in P$} \item \L{$R$} יחס סדר קווי \item לכל \L{$p,q\in P$} אם \L{$p\le q$} אזי יהיה פסוק \L{$R(c_{p},c_{q})$}.\end{enumerate} \begin{claim} \L{$T_{P}$} ספיקה )מקומית(. \begin{proof} ממשפט הקומפקטיות יספיק להוכיח ש\L{$T_{P}$} ספיקה מקומית. תהי \L{$T_{0}\subseteq T_{P}$} סופית. בה\char`\"{}כ האקסיומה ){\beginL 2\endL}( \char`\"{}\L{$R$} יחס סדרי קווי\char`\"{} שייכת ל\L{$T_{0}$}. בנוסף נשים לב שב\L{$T_{0}$} מופיעים רק מספר סופי של קבועים, נאמר: \L{$c_{P_{1}},...,c_{p_{n}}$}. נביט בקבוצה \L{$P_{0}=\{p_{1},...,p_{n}\}\subseteq P$}. אז \L{$(P_{0},\le)$} קס\char`\"{}ח סופית. לכן לפי ההערה יש יחס \L{$R^{P_{0}}$} שהוא סדר קווי על \L{$P_{0}$} המרחיב את \L{$\le$} על \L{$P_{0}$}. ברור שאם נפרש את \L{$R$} ב\L{$P_{0}$} ע\char`\"{}י \L{$R^{P_{0}}$} כנ\char`\"{}ל ו-\L{$c_{p_{i}}$} ע\char`\"{}י \L{$p_{i}$} אז נקבל מודל של \L{$T_{0}$}. \end{proof} \end{claim} יהי \L{$\mathcal{M}\models T_{P}$}, בפרט \L{$R^{\mathcal{M}}$} סדר קווי על \L{$\mathcal{M}$}. יהי \L{$\mathcal{N}\le\mathcal{M}$} המבנה שעולמו הוא הקבועים של \L{$\mathcal{M}$} )כלומר \L{$a\in\mathcal{N}\iff a=c_{p}^{\mathcal{M}}$} לאיזה \L{$p\in P$}(. נגדיר יחס סדר חלקי \L{$\le^{\mathcal{N}}$}על \L{$\mathcal{N}$} ע\char`\"{}י \L{$p\le q\iff c_{p}^{\mathcal{N}}\le c_{q}^{\mathcal{N}}$} לכל \L{$p,q\in P$} . אז \L{$(P,\le)\cong(N,\le^{\mathcal{N}})$} פשוט ע\char`\"{}י \L{$p\mapsto c_{p}^{\mathcal{N}}$}. לכן בה\char`\"{}כ \L{$(P,\le)=(N,\le^{\mathcal{N}})$}. עתה \L{$R^{\mathcal{M}}|\mathcal{N}$} )צמצום( סדר קווי על \L{$\mathcal{N}$}. )לפי \L{$\mathcal{M}\models(2)$} מתקיים כי\L{$R^{\mathcal{M}}$} סדר קווי וצמצום של כזה הוא נשאר קווי(. כיוון ש-\L{$\mathcal{M}\models(3)$} אז אם \L{$p\le q$} אזי \L{$p(c_{p},c_{q})$} היא אקסיומה ב){\beginL 3\endL}( ולכן \L{$\mathcal{M}\models R(c_{p},c_{q})$} ולכן \L{$\mathcal{N}\models R(c_{p},c_{q})$}. \end{proof} \begin{theorem} תהי \L{$L=\{G\}$} עבור יחס דו מקומי \L{$G$}. \L{$T_{G}$} התורה שאומרת כי העולם הוא גרף. אזי אין פסוק \L{$\psi$} ב\L{$L$} כך ש\L{$\mathcal{M}\models\psi$} אם ורק אם \L{$\mathcal{M}$} גרף קשיר.\end{theorem} \begin{proof} נניח בשלילה שיש פסוק \L{$\psi$} כזה. נוסיף לשפה קבועים אישיים חדשים \L{$c_{1},c_{2}$}. יהי \L{$\varphi_{n}$} הפסור שאומר שאין מסילה באורך קטן מ\L{$n$} בין \L{$c_{1}$} ל\L{$c_{2}$}:\L{ \[ \neg(\exists x_{1},...,x_{n})[G(c_{1},x_{1})\wedge\bigwedge_{i=1}^{n-1}(G(x_{i},x_{i+1})\vee x_{i}=x_{i+1})\wedge G(c_{2},x_{n})] \] } נשים לב ש\L{$\Gamma=\{c_{1},c_{2}\}\cup\psi\cup\{\varphi_{n}\}_{n=1}^{\infty}$} עיקבית מקומית. אם \L{$\Gamma_{0}$} קבוצה סופית של פסוקים מן הקבוצה הנ\char`\"{}ל יש \L{$n$} מירבי כך ש\L{$\varphi_{n}\in\Gamma_{0}$}. ברור שאם נמצא \L{$\mathcal{M}\models\varphi_{n}\wedge\psi\wedge(c_{1}\not=c_{2})$} אז \L{$\mathcal{M}\models\Gamma_{0}$}. אבל ברור שלכל \L{$n$} יש גרך המקיים את \L{$\varphi_{n}\wedge\psi\wedge(c_{1}\not=c_{2})$} )פחות מ\L{$n$} קודקודים, בפרט אין מסילה מ\L{$c_{1}$}ל\L{$c_{2}$}(. ולכן \L{$\Gamma$} ספיקה סופית. לפי קומפקטיות \L{$\Gamma$} עקבית. אבל זה לא ייתכן: אם \L{$\mathcal{M}\models\Gamma$} אז \L{$\mathcal{M}\models\psi$} ולכן בין \L{$c_{1}$} ל\L{$c_{2}$} יש מסילה ובהכרח אורכה סופי, נאמר \L{$n$}. מצד שני \L{$\mathcal{M}\models\varphi_{n}$} ולכן אין מסילה באורך \L{$n$} בין \L{$c_{1}$} ל\L{$c_{2}$} וזוהי סתירה להנחת השלילה. \end{proof} \uline{הערה:} \begin{enumerate} \item באופן דומה אפשר להוכיח כי אין פסוק \L{$\psi$} בשפה \L{$L=\{\le\}$} כך ש\L{$\mathcal{M}\models\psi$} אם ורק אם \L{$\{\le\}$} סדר טוב )כלומר \L{$\le$} סדר שווי בלי סדרה אינסופית יורדת(. \item אותה הוכחה בדיוק תעבוד אם ננסה למצוא קבוצת פסוקים \L{$\Gamma$} כך ש\L{$\mathcal{M}\models\Gamma$} אם ורק אם \L{$\mathcal{M}$} גרף קשיר/\L{$\mathcal{M}$} סדור היטב )סדר טוב(. \end{enumerate} \uline{תזכורת:} אם \L{$\Gamma$} קבוצת פסוקים אז \L{$\Gamma\models\psi$} אם לכל מבנה \L{$\mathcal{M}$}: אם \L{$\mathcal{M}\models\Gamma$} אז \L{$\mathcal{M}\models\psi$} . \begin{corollary} אם \L{$\Gamma\models\psi$} אז קיימת קבוצת פסוקים \L{$\Gamma_{0}\subseteq\Gamma$} סופית כך ש\L{$\Gamma_{0}\models\psi$}. \end{corollary} \begin{proof} נביט בקבוצה \L{$\Gamma\cup\{\neg\psi\}$} . מהנחתנו קבוצה זו איננה ספיקה. מקומפקטיות יש \L{$\Gamma_{1}\subseteq\Gamma\cup\{\neg\psi\}$} סופית כך ש\L{$\Gamma_{1}$} איננה ספיקה. ברור ש\L{$\neg\psi\in\Gamma_{1}$} כי אחרת \L{$\Gamma_{1}\subseteq\Gamma$} ו\L{$\Gamma$} עקבית. )אם \L{$\Gamma$} איננה עקבית מקומפקטיות יש \L{$\Gamma_{0}\subseteq\Gamma$} שאינה ספיקה ו\L{$\Gamma_{0}\models\varphi$} לכל פסוק \L{$\varphi$}(. לכן \L{$\Gamma\supseteq\Gamma_{0}=\Gamma_{1}\backslash\{\neg\psi\}$} סופית ומקיימת \L{$\Gamma_{0}\models\psi$} )כי אחרת יש מודל \L{$\mathcal{M}\models\Gamma_{0}$} ו-\L{$\mathcal{M}\not\models\psi$} כלומר \L{$\mathcal{M}\models\neg\psi$} כלומר \L{$\mathcal{M}\models\Gamma_{1}$} בסתירה לבחירת \L{$\Gamma_{1}$}(. במילים אחרות ליחס \L{$\models$} יש טבע סופי. \end{proof} \uline{שאלה מרכזית}: בהינתן שפה \L{$L$} וקבוצת פסוקים \L{$\Gamma$} ב\L{$L$}, כיצד אפשר לדעת/לבדוק ביחס לפסוק \L{$\psi$} כלשהו האם \L{$\Gamma\models\psi$}? בתור התחלה נשים לב שאם \L{$\psi\in\Gamma$} אז בוודאי \L{$\Gamma\models\psi$}. ולכן רצוי שנוכל לענות על השאלה האם \L{$\psi\in\Gamma$}? נניח שהגדרנו מתי קבוצת פסוקים \L{$\Gamma$} היא חשיבה, כלומר ניתן לענות על השאלה מתי פסוק \L{$\psi$} שייך ל\L{$\Gamma$}. נניח ש\L{$\Gamma$} קבוצת פסוקים חשיבה ונניח ש\L{$\psi_{1},\psi_{2}\in\Gamma$} אז \L{$\Gamma\models\psi_{1}\wedge\psi_{2}$}. נניח ש\L{$\psi_{1}\in\Gamma$} ו\L{$\Gamma\models\psi_{1}\rightarrow\psi_{2}$} אז \L{$\Gamma\models\psi_{2}$}. באופן כללי יותר אם הראנו למשל \L{$\psi_{1}$} ו-\L{$\psi_{1}\rightarrow\psi_{2}$} נגררים לוגית ע\char`\"{}י \L{$\Gamma$} אז ניתן להראות \L{$\Gamma\models\psi_{2}$}. \section{מערכות היסק ויכיחות} \uline{בעיה מרכזית:} נתונה קבוצת פסוקים \L{$\Gamma$} ורוצים לדעת עבור פסוק \L{$\psi$} האם \L{$\Gamma\models\psi$}. מקרה פרטי: \L{$\Gamma=\emptyset$}, כלומר רוצים לדעת האם פסוק \L{$\psi$} אמיתי לוגית או לא. המקרה הפרטי מנביע את המקרה הכללי. מדוע? בהינתן קבוצת פסוקים \L{$\Gamma$} ו\L{$\psi$} כלשהו, אם \L{$\Gamma\models\psi$} אז יש \L{$\Gamma_{0}\subseteq\Gamma$} סופית כך ש\L{$\Gamma_{0}\models\psi$} )משפט הקומפקטיות( ולכן \L{$({\displaystyle \bigwedge_{\varphi\in\Gamma_{0}}\varphi})\rightarrow\psi$} אמיתי לוגית ואת זה אנחנו יודעים לבדוק. \uline{שאלה}: מתי פסוק הוא אמיתי לוגית? \begin{enumerate} \item אנחנו יודעים שכל טאוטולוגיה היא אמיתית לוגית. \item אם \L{$\varphi$} אמיתי לוגית אז \L{$\forall x\varphi$} אמיתי לוגית. אפשר לרשום גם: \L{$\varphi\rightarrow\forall x\varphi$} אמיתי לוגית. \item אם \L{$\forall x\varphi(x)$} אמיתי לוגית אז \L{$\varphi(t)$} אמיתי לוגית לכל שם עצם \L{$t$}. אפשר לרשום גם: \L{$\forall x\varphi(x)\rightarrow\varphi(t)$} אמיתי לוגית. \item \textbf{אם \L{$\varphi\rightarrow\psi$} אמיתי לוגית ו\L{$\varphi$} אמיתי לוגית אז \L{$\psi$} אמיתי לוגית. })בכל מערכות ההיסק שנעבוד איתן זה יהיה כלל ההיסק היחיד. זה נקרא \uline{כלל הניתוק} או \inputencoding{latin9}\L{Modus Poneus}\inputencoding{cp1255}( \end{enumerate} \uline{סימון:} בהינתן שפה \L{$\mathcal{L}$} מסדר ראשון נסמן \L{$Def(\mathcal{L})$} אוסף הנוסחאות בשפה \L{$\mathcal{L}$}. \begin{definition} מערכת היסק )לשפה \L{$\mathcal{L}$}( זה זוג סדור \L{$\left\langle \mathcal{A},\mathcal{I}\right\rangle $}כאשר: \end{definition} \begin{enumerate} \item \L{$\mathcal{A}\subseteq Def(\mathcal{L})$} )אולי ריקה( שנקראת קבוצת האקסיומות הלוגיות \item \L{${\displaystyle \mathcal{I}\subseteq{\displaystyle \bigcup}_{i=1}^{\infty}F_{i}}$} כאשר \L{$F_{n}$} זה אוסף הפונקציות \L{$f:Def^{n}(\mathcal{L})\rightarrow Def(\mathcal{L})$} ו-\L{$\mathcal{I}$} נקראת אוסף כללי ההיסק. \end{enumerate} \uline{הערה:} תמיד נדרוש כי: \begin{enumerate} \item אם \L{$\varphi\in\mathcal{A}$} אז \L{$\varphi$} אמיתי לוגית. במקרה זה נאמר כי האקסיומות הלוגיות \uline{תקפות}. \item אם \L{$f\in\mathcal{I}$} ו- \L{$\{\varphi_{1},...,\varphi_{n}\}\in dom(f)$} אז \L{$\{\varphi_{1},...,\varphi_{n}\}\models f(\varphi_{1},...,\varphi_{n})$}. במקרה זה נאמר כי כללי ההיסק \uline{נאותים}. \end{enumerate} \uline{סימון}: אם נרצה לומר ש\L{$\psi$}מתקבל מ\L{$\psi_{1},...,\psi_{n}$} על ידי אחד מכללי ההיסק נרשום \L{$\frac{\psi_{1},...,\psi_{n}}{\psi}$} ולא צריך יהיה להסביר באיזה כלל היסק מדובר. \begin{definition} בהינתן מערכת היסק \L{$\left\langle \mathcal{A},\mathcal{I}\right\rangle $} וקבוצת נוסחאות \L{$\Gamma$} נאמר שנוסחה \L{$\psi$} \textbf{יכיחה} )כלומר, ניתנת להוכחה( מ\L{$\Gamma$} ,ונסמן \L{$\Gamma\vdash\psi$}, אם קיימת סדרת נוסחאות \L{$\varphi_{1},...,\varphi_{k}$} לאיזה \L{$k\in\mathbb{N}$} כך ש:\end{definition} \begin{enumerate} \item \L{$\psi=\varphi_{k}$} \item לכל \L{$1\le i\le k$} או: \begin{enumerate} \item \L{$\varphi_{i}$} אקסיומה לוגית. או: \item \L{$\varphi_{i}\in\Gamma$}. או: \item \L{$\varphi_{i}$} מתקבל מנוסחאות קודמות בסדרה ע\char`\"{}י אחד מכללי ההיסק. במקרה שלנו יש \L{$j_{1},j_{2}0$} מתקיים \L{$m_{i}=m_{i-1}^{(T)}$}. \end{enumerate} \item ריצה של מ\char`\"{}ט \L{$T$} נקראת \textbf{סופית} )או מסתיימת( אם היא מהצורה \L{$m_{0},m_{1},...,m_{n}$} לאיזה \L{$n\in\mathbb{N}$} ו-\L{$M_{n}^{(T)}$} אינו מוגדר. \end{enumerate} ~ \begin{definition} בהינתן מ\char`\"{}ט \L{$T$} ומספר טבעי \L{$n$} נגדיר פונקציה )חלקית( \L{$f_{T}^{n}=\mathbb{N}^{n}\rightarrow\mathbb{N}$} באופן הבא: \L{$n=0$}, \L{$q=q_{0}$} , והסרט נראה כך: \L{ \begin{eqnarray*} ...BB\underset{1+x_{1}}{\underbrace{1...1}}B\underset{1+x_{2}}{\underbrace{1...1}}B...B\underset{1+x_{n}}{\underbrace{1...1}}BB... \end{eqnarray*} }מתקיים \L{$m=f_{T}^{n}(x_{1},...,x_{n})$} אם ריצה של \L{$T$} עם המצב ההתחלתי הנ\char`\"{}ח מסתיימת )אחרת לא מוגדר( ו-\L{$m$} היא מספר האחדות על הסרט בתום הריצה. \end{definition} \end{definition} ~ \begin{definition} פונקציה \L{$f:\mathbb{N}^{n}\rightarrow\mathbb{N}$} נקראת \textbf{חשיבה ע\char`\"{}י מ\char`\"{}ט }אם קיימת מ\char`\"{}ט \L{$T$} כך ש\L{$f_{T}^{n}=f$}, כלומר \L{$f$} מוגדרת בדיוק באותו התחום בו \L{$f_{T}^{n}$} מוגדרת ובכל מקום שהן מוגדרות \L{$f_{T}^{n}(x_{1},...,x_{n})=f(x_{1},...,x_{n})$}. \end{definition} \section{מכונות טיורינג - המשך} \begin{definition} תהי \L{$f:\mathbb{N}^{k}\rightarrow\mathbb{N}$} פונקציה \L{$f$} נקראת \textbf{חשיבה} )ע\char`\"{}י מכונת טיורינג( אם קיימת מכונה \L{$T$} כך שלכל \L{$(n_{1},...,n_{k})\in\mathbb{N}^{k}$} הריצה של \L{$T$} על סרט מהצורה \L{ \begin{eqnarray*} ...BB\underset{1+n_{1}}{\underbrace{1...1}}B\underset{1+n_{2}}{\underbrace{1...1}}B...B\underset{1+n_{k}}{\underbrace{1...1}}BB... \end{eqnarray*} } מסתיימת אם ורק אם \L{$f(n_{1},...,n_{k})$} מוגדר ובמקרה זה מספר האחדות על הסרט בתום הריצה הוא \L{$f(n_{1},...,n_{k})$}. \uline{תזכורת}: סימנו, בהינתן מ\char`\"{}ט \L{$T$} את הפונקציה \L{$f_{T}^{n}$} להיות הפונקציה שעבור קלט כנ\char`\"{}ל מחזירה את מספר האחדות בריצה סופית של המכונה )על הקלט(.\end{definition} \begin{claim} לכל מכונת טיורינג \L{$T$} יש מכונת טיורינג \L{$T^{*}$} כך ש: \begin{enumerate} \item \L{$f_{T}^{n}=f_{T^{*}}^{n}$} לכל \L{$n$} \item בא\char`\"{}ב של \L{$T^{*}$} יש שני תווים מיוחדים \L{$S,E$} כך שבכל ריצה מסתיימת של \L{$T^{*}$} )על קלט תקני( הסרט לאחר הריצה נראה כך: \L{$...BBS111...1EBB...$} \item המכונה מעולם לא עברה במהלך הריצה את התא המסומן ב\L{$S$} שמאלה \item פרט ל\L{$S,E$} ל-\L{$T^{*}$} יש רק את התווים \L{$\{1,B\}$}. \end{enumerate} \end{claim} \begin{proof} ~ \begin{enumerate} \item ~ \item לכל מצב פנימי \L{$q\in Q(T)$} יהיה במכונה \L{$T^{*}$} מצב פנימי \L{$q^{*}$}. כל פקודה \L{$rqxq^{\prime}\in I(T)$} נחליף בפקודה \L{$rq^{*}x(q^{\prime})^{*}$}. נוסיף ל\L{$T^{*}$} את הפקודות הבאות: \begin{itemize} \item כותב \L{$S$} משמאל לקלט וחוזר ימינה \begin{itemize} \item \L{$Bq_{0}Lq_{1}$} \item \L{$1q_{0}Lq_{1}$} \item \L{$Bq_{1}Sq_{2}$} \item \L{$Bq_{2}Lq_{3}$} \end{itemize} \item מטפל בהגעה לסוף הקלט, כותב \L{$E$} וחוזר להתחלה \begin{itemize} \item \L{$Bq_{3}Rq_{4}$} \item \L{$Bq_{4}Lq_{5}$} \item \L{$Bq_{5}Eq_{r}$} \item \L{$*q_{r}Lq_{r}$} )\L{$*$} זה או \L{$B$} או \L{$1$}( \item \L{$Sq_{r}Rq_{0}^{*}$} \item שלב הסריקה \begin{itemize} \item \L{$1q_{3}Rq_{3}$} \item \L{$1q_{4}Rq_{3}$} \end{itemize} \end{itemize} \end{itemize} נותר להבטיח שכל האחדות צמודות ושהמכונה יודעת מה לעשות במקרה שהיא נתקלת ב\L{$S$} או ב\L{$E$} בשלב הריצה. נטפל קודם בחלק השני, לכל מצב פנימי \L{$q^{*}$} נוסיף פקודות: \begin{itemize} \item \L{$Sq^{*}B\tilde{q_{1}}$} \item \L{$B\tilde{q_{1}}L\tilde{q_{2}}$} \item \L{$B\tilde{q_{2}}S\tilde{q_{3}}$} \item \L{$S\tilde{q_{3}}Rq^{*}$} \item באופן אנלוגי מטפלים ב\L{$E$} \end{itemize} נטפל כעט בלהבטיח שכל האחדות צמודות. נניח שכל ריצה מסתיימת של \L{$T$} מסתיימת במצב פנימי \L{$\hat{q}$} )שאינו מופיע במהלך הריצה של \L{$T$}(. נוסיף פקודות: \begin{itemize} \item \L{$*\hat{q}R\hat{q}$} )כאשר \L{$*$} הינו כל תו שאינו \L{$E$}( \item \L{$E\hat{q}Bq_{w}$} \item \L{$Bq_{w}Lq_{w}^{1}$} \item \L{$*q_{w}^{1}E\hat{q}$} )כאשר \L{$*$} הינו כל תו שאינו \L{$1$} ואינו \L{$S$}( \item נטפל במקרה שראינו \L{$S$}אחרי שמחקנו את \L{$E$}: \begin{itemize} \item \L{$Sq_{w}^{1}Eq_{w}^{s}$} \item \L{$Eq_{w}^{s}Lq_{w}^{s_{1}}$} \item \L{$Bq_{w}^{s_{1}}Sq_{w}^{s_{2}}$} - מצב סופי \end{itemize} \item וגם: \begin{itemize} \item \L{$1q_{w}^{1}Eq_{w}^{d}$} \item \L{$1q_{w}^{d}Lq_{w}^{d}$} \item \L{$*q_{w}^{d}1\hat{q}$} )כאשר\L{$*$}- כל תו שאינו \L{$S$} או \L{$1$}( \item \L{$Sq_{w}^{d}1q_{w}^{s}$} \item \L{$1q_{w}^{s}Lq_{w}^{s_{1}}$} \end{itemize} \end{itemize} \item הטיפול דומה לזה של הסעיף הקודם, פרט לטיפול במה קורה כאשר פוגשים \L{$S$}. כל פעם שהמכונה פוגשת \L{$S$} היא תיכנס ל\char`\"{}תת מכונה\char`\"{} שמזיזה את כל הסרט שעד \L{$E$} ימינה בתו אחד, כותבת \L{$B$} במקום הראשון שמימין ל-\L{$S$} וחוזרת לריצה של \L{$T$}. הדבר היחיד שצריך להשתכנע: יש מכונה \L{$Sh$} שבהינתן קלט מן הצורה \L{$...BBS...EBBB...$} מעתיקה את כל הקלט בהזזה של תא אחד ימינה. נוסיף לא\char`\"{}ב שלנו תו מיוחד \L{$B^{*}$} , המכונה תרוץ באופן הבא: \begin{enumerate} \item תסרוק עד שתגיע ל\L{$E$} \item לכל תו \L{$\alpha$} בא\char`\"{}ב המקורי )כלומר שאינו \L{$B^{*}$}( יהיה מצב פנימי \L{$q_{\alpha}$}. סדרת הפקודות: \begin{itemize} \item \L{$\alpha q_{w}B^{*}q_{\alpha}$} \item \L{$Bq_{\alpha}Lq_{\alpha}^{1}$} \item \L{$B^{*}q_{\alpha}^{1}\alpha q_{w}$} \end{itemize} מעתיקה את התו \L{$\alpha$} תו אחד מימין למקומו המקורי. צריך טיפול נפרד בתווים \L{$S,E$} אבל אין בעיה. \end{enumerate} \item אם בא\char`\"{}ב שלנו יש \L{$n$} תווים נבנה מכונה \L{$T^{*}$} שבה התו ה-\L{$i$} בא\char`\"{}ב של \L{$T$} ייוצג ע\char`\"{}י \L{$n$}-יה של תאים \L{$\underset{i}{\underbrace{11...1}}\underset{n-i}{\underbrace{BB...B}}$} . קל לבדוק שכל פקודה מהצורה \char`\"{}זוז ימינה\char`\"{} או \char`\"{}זוז שמאלה\char`\"{} ב\L{$T$} ניתן לתרגם בקלות לפקודה \char`\"{}זוז \L{$n$} תווים ימינה/שמאלה\char`\"{} ב\L{$T^{*}$}. פקודה מהצורה \char`\"{}כתוב את התו ה\L{$i$} בא\char`\"{}ב בתא הנוכחי\char`\"{} תתרגם לסדרה של \L{$n$} פקודות כתיבה \char`\"{}כתוב במקום ה\L{$n$}-יה שאתה נמצא בתחילתה את ה\L{$n$}-יה \L{$\underset{i}{\underbrace{11...1}}\underset{n-i}{\underbrace{BB...B}}$}. כנ\char`\"{}ל לגבי הקריאה. לא קשה לבדוק: אם נייצג את התו \L{$1$} בא\char`\"{}ב של \L{$T$} ע\char`\"{}י \L{$\underset{n-1}{1\underbrace{BB...B}}$}אז \L{$f_{T^{*}}^{n}=f_{T}^{n}$} לכל \L{$n$}. \end{enumerate} \end{proof} מעכשיו נניח שכל מכונת טיורינג שנעבוד איתה מקיימת את התנאים {\beginL 2,3,4\endL} . לפי {\beginL 1\endL} אם מה שמעניין אותנו זה מחלקת הפונקציות הניתנות לחישוב ע\char`\"{}י מכונת טיורינג הרי שהנחה זו אינה משנה את המחלקה. בנוסף נניח שלכל מכונת טיורינג יש מצב מסיים יחיד שאינו מופיע במהלך הריצה. עוד אפשר להניח שבסיום הריצה הראש הקורא נמצא תו אחד מימין ל-\L{$S$}. \begin{claim} נניח ש-\L{$f:\mathbb{N}\rightarrow\mathbb{N}$} ו- \L{$g:\mathbb{N}\rightarrow\mathbb{N}$} חשיבות טיורינג אז גם \L{$f\circ g$} חשיבה טיורינג.\end{claim} \begin{proof} תהינה \L{$T_{f},T_{g}$} מכונות כך ש\L{$f_{T_{f}}^{\prime}=f$} וגם \L{$g_{T_{g}}^{\prime}=g$} . לכל מצב פנימי של \L{$f$} במכונה החדשה יהיה מצב פנימי \L{$q^{*}$}. אז המכונה של ההרכבה תהיה: \begin{enumerate} \item רשימת הפקודות של \L{$T_{g}$}. \item מוחקים את \L{$S$}, וכותבים במקומו \L{$1$}, מוחקים את \L{$E$}, חוזר להתחלה ועובר למצב פנימי \L{$q_{0}^{*}$} \item רשימת הפקודות של \L{$T_{f}$} עם השינוי שכל פקודה מהצורה \L{$*q\star q_{1}$} משתנה לפקודה מהצורה \L{$*q^{*}\star q_{1}^{*}$}. \end{enumerate} \end{proof} \begin{claim} משפחת הפונקציות החשיבות טיורינג סגורה תחת אופרטור \char`\"{}מיזער\char`\"{}: \L{ \begin{eqnarray*} \mu_{x_{1}}(g(x_{1},...,x_{n})) & = & \begin{cases} a & (*)\\ undefined & else \end{cases} \end{eqnarray*} } כאשר {*} הינו תנאי שנגדיר בשיעור הבא.... \end{claim} \section{פונקציות חשיבות} ראינו שהפונקציות הבאות חשיבות טיורינג: \begin{itemize} \item \L{$1$} - הפונקציה הקבועה {\beginL 1\endL} \item \L{$0$} - הפונקציה הקבועה {\beginL 0\endL} \item \L{$x+y$} - חיבור \item קל לוודא ש\L{$\Pi_{k}^{n}(x_{1},...,x_{n})=x_{k}$} עבור \L{$k0)\\ undefined & else \end{cases} \end{eqnarray*} } אזי אם \L{$g$} חשיבה טיורינג גם \L{$h$} חשיבה טיורינג. \L{$\mu$} נקרא אופרטור ה\char`\"{}מיזער\char`\"{}.\end{claim} \begin{proof} )רעיון( תהי \L{$T$} מכונת טיורינג המחשבת את \L{$g$} )כלומר \L{$f_{T}^{k}=g$}(. \char`\"{}מטה רעיון\char`\"{} - נריץ את \L{$T$} על הקלט \L{$0,x_{2},...,x_{k}$}. אם המכונה לא עוצרת זה אומר ש\L{$g$} לא מוגדרת ב\L{$(0,x_{2},...,x_{k})$} ולכן גם \L{$h(x_{2},...,x_{k})$} לא מוגדרת כנדרש. אם הריצה מסתיימת נבדוק האם היא הסתיימה ב\L{$0$}. אם כן, נחזיר \L{$0$} ואז \L{$h(0,x_{2},...,x_{k})=0$} כנדרש. אם לא, נחזור על אותה פעולה עם הקלט \L{$1,x_{2},...,x_{k}$} וכו'. אם המכונה הנ\char`\"{}ל תעצור אי פעם, זה יהיה הטבעי הקטן ביותר \L{$t$} עבורו \L{$g(t,x_{2},...,x_{k})=0$}, בפרט \L{$g(t^{\prime},x_{2},...,x_{k})$} מוגדרת לכל \L{$t^{\prime}0$} לכל \L{$t^{\prime}0$} לכל \L{$t$}. ואילו במקומות בהם \L{$h$} לא מוגדרת כך שקיבלנו שיוויון. \end{enumerate} ביתר פירוט: נבנה מכונה הפועלת באופן הבא. המכונה מסמנת את סוף הקלט ב\L{$S$}. בשלב הראשון המכונה \L{$T^{*}$} תעתיק את הקלט \L{$x_{2},...,x_{k}$} מימין ל\L{$S$} ותוסיף \L{$1B$} בהתחלה. בשלב הבא \L{$T^{*}$} תחקה את הריצה של \L{$T$} על \L{$0,x_{2},...,x_{k}$} כאשר היא מקפידה )וזה הרי \L{$T$} עושה ממילא( לא לזוז משמאל ל\L{$S$}. אם השלב הזה בריצה הסתיים במקום כלשהו על הסרט מימין ל\L{$S$} יהיה כתוב \L{$E$} )כי כך \L{$T$} עובדת(. אם בין \L{$S$} ל\L{$E$} לא מופיע התו \L{$1$}, אז \L{$T^{*}$} תחזור עד להתחלת הקלט של \L{$T^{*}$} )משמאל ל\L{$S$}( תמחק את כל הקלט ותעצור. אם בין \L{$S$} ל\L{$E$} מופיע התו \L{$1$} המכונה תחזור לתחילת הקלט של \L{$T^{*}$}, תכתוב \L{$1$} לפני ה\L{$B$} הראשון ותתחיל מההתחלה. \end{proof} \begin{definition} פונקציה \L{$f:\mathbb{N}^{k}\rightarrow\mathbb{N}^{m}$} תיקרא חשיבה/רקורסיבית אם היא מתקבלת מן הפונקציות \L{$\{x+y,x\cdot y,C_{<}(x,y),\Pi_{k}^{n}(x_{1},...,x_{n}),1,0\}$} על ידי מספר סופי של הרכבות והפעלה של האופרטור \L{$\mu_{x}$}. במילים אחרות, משפחת הפונקציות החשיבות זו המשפחה/אוסף הקטנ/ה ביותר של פונקציות מ\L{$\mathbb{N}^{k}$} ל\L{$\mathbb{N}^{m}$} שמכיל/ה את הפונקציות הנ\char`\"{}ל וסגור/ה תחת הרכבה והאופרטור \L{$\mu_{x}$}. \end{definition} \begin{theorem} פונקציה \L{$f:\mathbb{N}^{k}\rightarrow\mathbb{N}^{m}$} חשיבה אם ורק אם היא חשיבה טיורינג. הוכחנו שכל פונקציה חשיבה היא חשיבה טיורינג. \uline{תרגיל:} הפונקציה \L{$n\mapsto n!$} היא חשיבה טיורינג. הוכח שהפונקציה חשיבה. שאלה כמעט זהה: מדוע הפונקציה \L{$f(m)=\begin{cases} n & m=2^{n}\\ 0 & m=1\, or\, else \end{cases}$} חשיבה?\end{theorem} \begin{definition} תהי \L{$A\subseteq\mathbb{N}^{m}$} אזי \L{$\chi_{A}=\mathbb{N}^{m}\rightarrow\mathbb{N}$} זו הפונקציה המוגדרת על ידי \L{ \begin{eqnarray*} \chi_{A}(x) & = & \begin{cases} 1 & x\in A\\ 0 & else \end{cases} \end{eqnarray*} }. \L{$\chi_{A}$} נקראת \textbf{הפונקציה המציינת} של \L{$A$}. \begin{definition} יחס \L{$A\subseteq\mathbb{N}^{m}$} נקרא \textbf{חשיב} אם \L{$\chi_{A}$} פונקציה חשיבה.\end{definition} \begin{claim} משפחת היחסים החשיבים סגורה תחת פעולות בוליאניות, כלומר תחת איחודים, חיתוכים והשלמה. \end{claim} \end{definition} \begin{proof} ~ \begin{itemize} \item אם \L{$A$} חשיבה אז \L{$\chi_{A}(x)=C_{<}(\chi_{A}(x),1)$}. \item אם \L{$A,B$} חשיבות אז \L{$\chi_{A\cap B}(x)=\chi_{A}(x)\cdot\chi_{B}(x)$}. \item \L{$\chi_{A\cup B}(x)=C_{<}(0,\chi_{A}(x)+\chi_{B}(x))$} או לפי דה-מורגן. \end{itemize} יוצא, למשל, כי היחס \L{$A(x,y)=(x\le y)$} חשיב. זה פשוט איחוד היחסים החשיבים \L{$C_{<}(x,y)$} ו-\L{$x=y$}. \end{proof} \begin{claim} )הגדרה לפי מקרים(: תהיינה \L{$f_{1},...,f_{n}$} פונקציות חשיבות \L{$k$}-מקומיות, ו-\L{$A_{1},...,A_{n}\subseteq\mathbb{N}^{k}$} זרות וחשיבות, כך ש\L{$\bigcup_{i=1}^{n}A_{i}=\mathbb{N}^{k}$}. אזי הפונקציה \L{ \begin{eqnarray*} f(x) & = & \begin{cases} f_{1}(x) & x\in A_{1}\\ \vdots & \vdots\\ f_{n}(x) & x\in A_{n} \end{cases} \end{eqnarray*} } חשיבה. \end{claim} \begin{proof} \L{$\sum_{i=1}^{n}f_{i}(x)\cdot\chi_{A_{i}}(x)$} וזו פונקציה חשיבה כי \L{$\chi_{A_{i}}$} חשיבות, \L{$f_{i}$} חשיבות והחיבור והכפל חשיבים. \end{proof} \section{פונקציות חשיבות - המשך} \begin{definition} יהי \L{$A\subseteq\mathbb{N}^{k+1}$} יחס חשיב, \L{$k+1$} מקומי. נגדיר אופרטור: \L{ \begin{eqnarray*} \mu_{xb_{2}$}( לכל \L{$1\le i\le n$}. לכן \L{$b_{1}-b_{2}$} מחלק את המכפלה המשותפת הקטנה ביותר של ה\L{$m_{i}$}. כיוון שה\L{$m_{i}$} זרים בזוגות המכפלה המשותפת הקטנה ביותר היא \L{$d$}. אבל \L{$b_{1}-b_{2}j$}. לכן: \L{$p|(i-j)\cdot(n!)$} . כיוון ש\L{$p$} ראשוני הוא מחלק או את \L{$i-j$} או את \L{$n!$}. כיוון ש\L{$i-jn$} כלשהו ונבחר \L{$y=k!$}. לפי טענת עזר {\beginL 3\endL} קיים \L{$z$} כך ש\L{$\gamma(z,y,i)=a_{i}$} לכל \L{$i\le n$}. \item )טכני( \L{$\gamma(z,y,i)\le z$} לכל \L{$z,y,i$}. \end{enumerate} \end{claim} הפונקציה \L{$\beta(b,i)$} המבוקשת תהיה \L{$\gamma(Pr^{L}(b),Pr^{R}(b),i)$} כאשר \L{$Pr^{L}(b)=\Pi_{1}(Pr^{-1}(b))$} ו-\L{$Pr^{R}(b)=\Pi_{2}(Pr^{-1}(b))$}. הדבר היחיד שנותר לוודא \L{$Pr^{L},Pr^{R}$} הן פונקציות חשיבות. \section{הצפנות} \uline{חזרה:} אם \L{$A(x,y)$} יחס חשיב אז \L{$(\exists x3$} ל\L{$i>1$} אז \L{$p$} פקודה מהצורה \L{$\beta(x,i-1)\beta(x,i)**$}. במילים אחרות אם \L{$p$} היא הרביעייה \L{$\left\langle \alpha,q,\alpha^{\prime},q^{\prime}\right\rangle $} אז \L{$x$} רלוונטי ל\L{$p$} אם \L{$\beta(x,i-1)=\alpha,\beta(x,i)=q$}. נסמן זאת \L{$\varphi_{p}(x)$}. לומר ש\L{$y$} עוקב של \L{$x$} לפי \L{$p$} זה לומר \L{$\varphi(x),\varphi(y)$}. \L{$\varphi_{p}(x)$} עכשיו מתחלק לפי מהות הפקודה \L{$p$}. נטפל למשל במקרה ש\L{$p=\left\langle \alpha,q,\alpha^{\prime},q^{\prime}\right\rangle $} כאשר \L{$\alpha^{\prime}\in\{0,1\}$}. מתי \L{$y$} יתקבל מ\L{$x$} ע\char`\"{}י הפקודה \L{$p$}? אם \L{$x=\left\langle \alpha_{1},...,\alpha_{i},q,\alpha_{i+1},...,\alpha_{k}\right\rangle ,y=\left\langle \alpha_{1},...,\alpha_{i},q^{\prime},\alpha_{i+1},...,\alpha_{k}\right\rangle $}. פשוט צריך לדרוש: \begin{enumerate} \item נסמן \L{$i_{0}$} להיות ה\L{$i$} היחיד כך ש\L{$i\le\beta(x,0)$} ו-\L{$\beta(x,i_{0})\in\{4,...,k\}$}. \item נדרוש ש\L{$\beta(y,i_{0})=q^{\prime},\beta(y,i_{0}-1)=\alpha^{\prime}$} ובכל מקרה אחר \L{$\beta(y,j)=\beta(x,j)$}. \end{enumerate} הטיפול בפקודות של תזוזה הוא דומה. זה מקרה ש\L{$\varphi_{p}(x,y)$} חשיבה. לומר ש\L{$y$} עוקב של \L{$x$} זה פשוט \L{${\displaystyle \varphi(x)\wedge\varphi(y)\wedge\bigvee_{p\in I}\varphi_{p}(x,y)}$} . \end{proof} \begin{claim} ){\beginL 4\endL}( היחס \L{$\rho(x)$} האומר \char`\"{}\L{$x$} מקודד ריצה מסתיימת של \L{$T$}\char`\"{} הוא חשיב.\end{claim} \begin{proof} ~ \begin{enumerate} \item \L{$\theta(x)$} - \L{$x$} מצפין סדרה. \item \L{$\varphi_{S}(\beta(x,1))$} כלומר האיבר הראשון בסדרה ש\L{$x$} מצפין הוא מצב התחלתי של \L{$T$}. \item \L{$\varphi_{E}(\beta(x,\beta(x,0)))$} - האיבר האחרון בסדרה הוא מצב סופי של \L{$T$}. \item לכל \L{$1\le i<\beta(x,0)$} מתקיים \L{$\varphi(\beta(x,i),\beta(x,i+1))$} כלומר כל איבר בסדרה הוא מצב עוקב של המצב המוצפן ע\char`\"{}י האיבר הקודם לו. \end{enumerate} \end{proof} \begin{claim} ){\beginL 5\endL}( \L{$f_{E}(x)=n$} זו הפונקציה שמחזירה \L{$n$} אם \L{$x$} מצפין מצב סופי של \L{$T$} ו\L{$n$} הפלט של המכונה במצב זה. {\beginL 0\endL} אחרת. זו פונקציה חשיבה: \L{$\chi_{\varphi_{E}}(x)\cdot(\beta(x,0)-3)$} . \end{claim} \section{חשיבות} היינו בעיצומה של ההוכחה שכל פונקציה חשיבה טיורינג היא חשיבה. \begin{claim} ){\beginL 1\endL}( היחס \L{$\varphi(x)$} האומר \char`\"{}\L{$x$} מצפין מצב של המכונה \L{$T$}\char`\"{} חשיב. \end{claim} ~ \begin{claim} ){\beginL 2\endL}( היחסים \L{$\varphi_{s}(x)$}, \char`\"{}\L{$x$} מצפין מצב התחלתי של \L{$T$}\char`\"{}, \char`\"{}\L{$x$} מצפין מצב סופי של \L{$T$}\char`\"{} - כולם חשיבים. \end{claim} ~ \begin{claim} ){\beginL 3\endL}( היחס \L{$\varphi(x,y)$} האומר \char`\"{}\L{$x,y$} מייצגים מצבים של \L{$T$} ו\L{$y$} המצב העוקב של \L{$x$} לפי \L{$T$}\char`\"{} הוא יחס חשיב. \end{claim} ~ \begin{claim} ){\beginL 4\endL}( היחס \L{$\rho(x)$} האומר \char`\"{}\L{$x$} מקודד ריצה מסתיימת של \L{$T$}\char`\"{} הוא חשיב. \end{claim} ~ \begin{claim} ){\beginL 5\endL}( \L{$\varphi_{E}(x)=n$} זו הפונקציה שמחזירה \L{$n$} אם \L{$x$} מצפין מצב סופי של \L{$T$} ו\L{$n-1$} הפלט של המכונה במצב זה. {\beginL 0\endL} אחרת. זו פונקציה חשיבה: \L{$\chi_{\varphi_{E}}(x)\cdot(\beta(x,0)-3)$} . נדרוש ש\L{$\varphi_{E}(x)=0$} אחרת. \end{claim} ~ \begin{claim} היחס \char`\"{}\L{$x$} מקודד מצב התחלתי של \L{$T$} שבו הקלט הוא \L{$x_{1},...,x_{n}$}\char`\"{} הוא יחס חשיב. נסמן זאת \L{$\varphi_{s}(x,x_{1},...,x_{n})$}. \end{claim} כדי להוכיח את המשפט עלינו להראות ש\L{$f_{T}^{n}(x_{1},...,x_{n})$} פונקציה חשיבה. נגדיר פונקציה חשיבה באופן הבא: \L{ \begin{eqnarray*} f(x_{1},...,x_{n}) & = & \varphi_{E}(\mu_{x}^{*}(\rho(x)\wedge\varphi_{s}(\varphi_{s,0}(x),x_{1},...,x_{n}))) \end{eqnarray*} } כאשר \L{$\varphi_{s,0}(x)=\beta(x,1)$} - האיבר הראשון בסדרה ש\L{$x$} מקודד, וכאשר \L{$\mu_{x}^{*}(A(x,y))$} זה ה\L{$x$} המזערי עבורו \L{$\chi_{A}(x,y)=1$}. \begin{claim} \L{$f(x_{1},...,x_{n})=f_{T}^{n}(x_{1},...,x_{n})$} ובפרט \L{$f$} מוגדרת אם ורק אם ריצת \L{$T$} על \L{$x_{1},...,x_{n}$} עוצרת.\end{claim} \begin{proof} ראשית נבדוק שתחומי ההגדרה של שתי הפונקציות זהים. אם \L{$T$} עוצרת על \L{$x_{1},...,x_{n}$} אז קיים \L{$x$} כך ש\L{$\rho(x)\wedge\varphi_{s}(\varphi_{s,0}(x_{1},...,x_{n}))$} - כלומר קיים \L{$x$} המקודד ריצה מסתיימת של \L{$T$} המתחילה בקלט \L{$x_{1},...,x_{n}$}. אם נבחר \L{$x_{0}$} הקטן ביותר המקיים זאת אז \L{ \begin{eqnarray*} x_{0} & = & \mu_{x}^{*}(\rho(x)\wedge\varphi_{s}(\varphi_{s,0}(x),x_{1},...,x_{n})) \end{eqnarray*} } כי לכל \L{$x^{\prime}n$}. בנוסף, אם ב-\L{$\varphi$} מופיע סימן פונקציה, סימן יחס, קבוע אישי או משתנה עם אינדקס \L{$i>n$} אז )באינדוקציה( \L{$g(\varphi)>n$}. לכן השאלה האם \L{$n$} מספר גדל של נוסחה שקולה לשאלה האם קיימת נוסחה \L{$\varphi$} באורך קטן-שווה ל-\L{$n$}, שכל הסימנים הלא-לוגיים המופיעים בה הם עם אינדקס קטן או שווה ל-\L{$n$}. ומספר גדל של \L{$\varphi$} הוא \L{$n$}. אבל קבוצת הנוסחאות \L{$\varphi$} מאורך קטן-שווה ל-\L{$n$} , שכל הסימנים בה עם אינדקס קטן-שווה ל-\L{$n$} היא סופית, כלומר זהו כימות חסום. לכן מספיק לבדוק שהפונקציה ששולחת נוסחה למספר גדל שלה היא חשיבה טיורינג. )זה עסק מייגע, אבל לא קשה.(\end{proof} \begin{definition} ~ \begin{enumerate} \item תהי \L{$f:\mathbb{N}\rightarrow\mathbb{N}$} , נאמר שתורה \L{$T$} בשפה המרחיבה את \L{$(0,s)$} מייצגת )חלש( את \L{$f$} אם קיימת נוסחה \L{$\varphi(x,y)$} בשפה \L{$\mathcal{L}$} כל שלכל \L{$n\in Dom(f)$} מתקיים \L{$T\vdash(\forall y)(\varphi(\underline{n},y)\iff\underline{f(n)})$} כאשר הסימון \L{$\underline{n}:=s^{n}(0)$} עבור \L{$s$} פונקציית העוקב. \item יחס \L{$A\subseteq\mathbb{N}$} \uline{מיוצג} ב-\L{$T$} אם \L{$\chi_{A}$} מיוצגת ב\L{$T$}. \end{enumerate} \end{definition} ~ \begin{definition} \uline{תורת פיאנו} \inputencoding{latin9}\L{(Peano Arithmetic)}\inputencoding{cp1255} זו קבוצת הפסוקים הבאה בשפה \L{$\mathcal{L}=\{0,+,\cdot,s)$}: \begin{enumerate} \item \L{$(\forall x)(s(x)\not=0)$} \item \L{$(\forall x\forall y)(s(x)=s(y)\rightarrow x=y)$} \item \L{$(\forall x)(x+0=x)$} \item \L{$(\forall x\forall y)(x+s(y)=s(x+y))$} \item \L{$(\forall x)(x\cdot0=0)$} \item \L{$(\forall x\forall y)(x\cdot s(y)=x\cdot y+x)$} \item \uline{סכימת האינדוקציה:} לכל נוסחה \L{$\varphi(x,y)$} אקסיומה מהצורה:\L{ \[ (\forall x)[\varphi(\bar{x},0)\wedge\forall y(\varphi(\bar{x},y)\rightarrow\varphi(\bar{x},s(y))\rightarrow\forall y(\varphi(\bar{x},y))] \] } \end{enumerate} \end{definition} \begin{theorem} כל פונקציה חשיבה ניתנת לייצוג ב-\L{$PA$}. יתר על כן, קיימת תורה \L{$N$} סופית כך ש-\L{$PA\vdash N$} וכל פונקציה חשיבה מיוצגת ב-\L{$N$}. \end{theorem} \uline{תרגיל}: אם \L{$f:\mathbb{N}\rightarrow\mathbb{N}$} שלמה ומיוצגת ב-\L{$PA$} אז \L{$f$} חשיבה. \begin{corollary} התורה \L{$N$} שמובטחת במשפט, אינה כריעה.\end{corollary} \begin{proof} תהי \L{$\varphi(e,z,n)$} הנוסחה האומרת שמ\char`\"{}ט \L{$T_{e}$} )שהקוד שלה הוא \L{$e$}( עוצרת על הקלט \L{$n$} אחרי \L{$z$} צעדים. היחס \L{$\varphi(e,z,n)$} חשיב {]}הוכחנו{[}, לכן לפי המשפט מיוצג ב-\L{$N$}. כלומר אם \L{$T_{e}(n)$} \uline{לא עוצרת} אז לכל \L{$z$} מתקיים \L{$N\vdash\neg\varphi(e,z,n)$}. מצד שני, אם \L{$T_{e}(n)$} \uline{עוצרת} אז \L{$N\vdash\varphi(e,z,n)$} לאיזה \L{$z$}. נניח בשלילה ש-\L{$N$} כריעה אז \L{$N\vdash(\exists z)\varphi(e,z,n)$} אם ורק אם \L{$T_{e}(n)$} עוצרת. אבל מכריעות נקבל שלכל זוג \L{$\left\langle e,n\right\rangle $} אפשר לדעם האם \L{$N\vdash(\exists z)\varphi(e,z,n)$} או \L{$N\vdash(\neg\exists z)\varphi(e,z,n)$}. כלומר אפשר להכריע האם \L{$T_{e}(n)$} עוצרת או לא. אבל לפי משפט רייס זו איננה קבוצה חשיבה. סתירה. \end{proof} \uline{הערה}: אם \L{$N\subseteq T$} )\L{$N$} התורה המובטחת במשפט( אז: \begin{enumerate} \item כל פונקציה חשיבה ניתנת לייצוג ב-\L{$T$} \item לכן, \L{$T$} איננה כריעה, כי אותה ההוכחה ש-\L{$N$} אינה כריעה תעבוד עבור \L{$T$}. \end{enumerate} \uline{הערה}: אם תורה \L{$T$} היא חשיבה ושלמה אז \L{$T$} כריעה. להלן אלגוריתם הכרעה: נראה בהמשך שאם \L{$T$} חשיבה אז \L{$C_{T}:=\{g(\varphi):T\vdash\varphi\}$} נל\char`\"{}ח. כיוון ש-\L{$T$} שלמה, כדי לבדוק האם \L{$T\vdash\varphi$} נפעיל את המכונה המונה את \L{$C_{T}$}. בכל שלב נבדוק האם האיבר שהמכונה פלטה הוא הוכחה של \L{$\varphi$} או הוכחה של \L{$\neg\varphi$} . השלמות מבטיחה לנו שאחד מהם יתקבל בזמן סופי. אם מתקבל \L{$\varphi$} - ניצחנו. אם מתקבל \L{$\neg\varphi$} - גם ניצחנו. \begin{corollary} כל תורה \L{$T$} כך ש-\L{$N\subseteq T\subseteq PA$} מהמסקנה הקודמת אינה כריעה. )למשל תורת המספרים איננה כריעה(. \end{corollary} \section{פונקציות יציגות} \uline{תזכורת:} פונקציה \L{$f:\mathbb{N}^{k}\rightarrow\mathbb{N}$} תקרא מיוצגת )חלש( בתורה \L{$T$} )בשפה עם סימן קבוע {\beginL 0\endL} וסימן פונקציה חד מקומי \L{$s$}( אם קיימת נוסחה \L{$\varphi(x,y)$} כך שלכל \L{$\bar{n}\in Dom(f)$} מתקיים\L{ \begin{eqnarray*} T & \vdash & (\forall y)(\varphi(\underline{\bar{n}},y)\iff\underline{f(n)}=y) \end{eqnarray*} }כאשר \L{$\underline{n}=s^{n}(0)$}. \begin{theorem} כל פונקציה חשיבה יציגה בתורת פאנו ואפילו יש תת-תורה סופית של \L{$PA$} שבה כל פונקציה חשיבה יציגה.\end{theorem} \begin{corollary} תהי \L{$N\subseteq PA$} כמובטח במשפט. אזי \L{$N$} אינה כריעה. \end{corollary} \begin{proof} יהי \L{$\varphi(e,n,z)$} היחס האומר \char`\"{}המכונה שהקוד שלה \L{$e$} עצרה על הקלט \L{$n$} אחרי לכל היותר \L{$z$} מהלכים\char`\"{}. אז ברור ש-\L{$\varphi(e,n,z)$} הוא יחס חשיב. מהמשפט נובע שלכל שלשה \L{$\left\langle e,n,z\right\rangle \in\mathbb{N}^{3}$} מתקיים \L{$N\vdash\varphi(e,n,z)$} אם ורק אם \L{$\left\langle e,n,z\right\rangle $} עומדת ביחס, כלומר המכונה \L{$e$} עוצרת על \L{$n$} אחרי לא יותר מ\L{$z$} צעדים. לכן אם \L{$\left\langle e,n\right\rangle $} עוצרת יש \L{$z_{0}$} כך ש\L{$N\vdash\varphi(\underline{e},\underline{n},\underline{z_{0}})$}. לכן אם \L{$\left\langle e,n\right\rangle $} עוצרת אז \L{$N\vdash(\exists z)\varphi(\underline{e},\underline{n},z)$}. מצד שני, אם \L{$\left\langle e,n\right\rangle $} לא עוצרת אז \L{$N\not\vdash\varphi(\underline{e},\underline{n},\underline{z_{0}})$} לכל \L{$\underline{z_{0}}$}. אבל \L{$\mathbb{N}\models PA$} ולכן \L{$\mathbb{N}\models N$} . לכן לא ייתכן ש\L{$N\vdash(\exists z)\varphi(\underline{e},\underline{n},z)$} אבל מהנחתנו זה לא מתקיים. יוצא \L{$N\vdash(\exists z)\varphi(\underline{e},\underline{n},z)$} אם ורק אם \L{$\left\langle e,n\right\rangle $} עוצרת. לכן אילו הייתה \L{$N$} כריעה היינו יכולים להכריע את בעיית העצירה: בהינתן זוג \L{$\left\langle e,n\right\rangle $} היינו פשוט שואלים אם \L{$N\vdash(\exists z)(\underline{e},\underline{n},z)$}. אם כן - \L{$\left\langle e,n\right\rangle $} עוצרת, ואם לא אז \L{$\left\langle e,n\right\rangle $} לא עוצרת.\end{proof} \begin{corollary} כל תורה \L{$N\subseteq T\subseteq PA$} מהמסקנה הקודמת אינה כריעה. ניגש להוכחת המשפט עצמו. \end{corollary} תהי \L{$N\subseteq PA$} התורה הבאה: \begin{itemize} \item \L{$PA(1)-PA(6)$} \item \L{$(N7)$}: \L{$(\forall x)(\neg x<0)$} \item \L{$(N8)$}: \L{$(\forall x\forall y)(xn$}, הבניה במקרה ב' תייצר \L{$2_{e,k}$} - הכרזה. )ובתנאי שבשלב ה-\L{$i$} כבר נכנסו ל-\L{$A$} כל האיברים שבהם נעשה שימוש חיובי בחישוב של \L{$T_{e}^{A}(k)$}. אבל מהדיון הקודם, כל תנאי יכול לייצר לכל היותר מספר סופי של הכרזות. אז האחרונה מביניהן שהכרח לא תשתנה, ז\char`\"{}א תהיה קבועה. עד עתה: בנינו את \L{$A$}, הראנו ש-\L{$A$} מקיימת את התנאים \L{$1_{e}$} ואת \L{$2_{e,k}$} )לפי א' הנ\char`\"{}ל( וברור שהבניה חשיבה. כיוון ש-\L{$A$} מקיימת את \L{$1_{e}$} לכל \L{$e$}, ברור ש-\L{$A$} אינה חשיבה. כיוון שהבניה חשיבה, אם נגדיר \L{$s(n)$} להיות הקבוצה \L{$A_{n}$} שהתקבלה בשלב ה-\L{$n$} של הבנייה נקבל ש-\L{$A$} נל\char`\"{}ח, כי \L{$s(n)$} חשיבה. נותר לוודא ש-\L{$deg(A^{*})\le0$}. ראינו בתרגיל {\beginL 11\endL} טענה שאומרת שאם \L{$A^{*}=dim(B_{i})$} עבור \L{$i\in\mathbb{N}$} כך ש-\L{$B_{i}$} חשיבה מ{\beginL -\endL}\L{$A$} אז \L{$deg(A^{*})\le0^{\prime}$}. נגדיר \L{$\left\langle e,k\right\rangle \in B_{i}$}אם ורק אם בשלב ה-\L{$i$} של הבנייה יש \L{$2_{e,k}$} - הכרזה שאיננה פצועה. כיוון שהבניה חשיבה \L{$B_{i}$} יחס חשיב. לפי )א( הנ\char`\"{}ל \L{$T_{e}^{A}(k)(\iff\left\langle e,k\right\rangle \in B_{i})$} עוצרת אם ורק אם \L{$dim\chi_{B_{i}}(\left\langle e,k\right\rangle )=1$}.\end{proof} \begin{theorem} לכל דרגה \L{$0^{\prime}\le a$} קיימת דרגה \L{$b$} כך ש-\L{$b^{\prime}=0^{\prime}\cup b=a$}. \end{theorem} \uline{רעיון ההוכחה}: נבחר \L{$g:\mathbb{N}\rightarrow\mathbb{N}$} כך ש-\L{$deg(g)=a$}, אפשר לבחור \L{$g$} כזו שלמה. נרצה לבנות \L{$f:\mathbb{N}\rightarrow\mathbb{N}$} כך ש-\L{$f^{*}$} חשיבה מ-\L{$0^{\prime}\cup deg(f)$} ו-\L{$g$} חשיבה מ-\L{$f^{*}$}. נרצה להגשים שני סוגים תנאים: \begin{itemize} \item \L{$1_{e,k}$} - להחליט האם \L{$T_{e}^{f}(k)$} עוצרת \item \L{$2_{n}$} - לוודא ש-\L{$f(m)=g(n)$} לאיזה \L{$m\in\mathbb{N}$}. \end{itemize} כרגיל נמספר את התנאים \L{$\{c_{i}\}$}, ובשלב ה-\L{$i$} אם אנו בתנאי \L{$1_{e,k}$} ויש \L{$\sigma:\mathbb{N}\rightarrow\mathbb{N}$} סופית שמתיישבת עם \L{$f_{i-1}$} כך ש-\L{$T_{e}^{\sigma}(k)$} עוצרת, נגדיר \L{$f_{i}=f_{i-1}\cup\sigma$} ואחרת נגדיר \L{$f_{i}=f_{i-1}$}. ואם בשלב ה-\L{$i$} אנו בתנאי \L{$2_{n}$} אז נבחר \L{$m$} מזערי כך שאינו בתחום של \L{$f_{i-1}$} ונגדיר \L{$f_{i}(m)=g(n)$}. לסיכום: יוצא שהבניה חשיבה מ-\L{$0^{\prime}\cup a=a$} וחשיבה גם מ-\L{$0^{\prime}\cup b$}. ~ \begin{proof} תהי \L{$g$} כנ\char`\"{}ל ונמצא פונקציה \L{$f$} כך ש-\L{$deg(f)$} תענה על הדרישות. \L{$b\cup b^{\prime}\le b^{\prime}$} ולכן יספיק למצוא \L{$b$} כך ש-\L{$b^{\prime}\le a\le b$}. מזה נבטיח שיש שיוויונות לכל אורך הדרך. אז צריך למצוא \L{$b$} כך ש-\L{$b^{\prime}$} חשיבה מ-\L{$b$} ומ-\L{$0^{\prime}$}. כרגיל נמספר את התנאים )כולם ביחד( במספור חשיב \L{$\{e_{i}\}_{i=0}^{\infty}$} ונניח שלכל \L{$i\le n$} בנינו פונקציה \L{$f_{i}$} )עם תחום סופי( כך ש-\L{$f_{i}\subseteq f_{j}$} אם \L{$i\le j$}. \uline{בניית \L{$f_{n+1}$}:} \begin{itemize} \item אם \L{$e_{n+1}$} הוא תנאי מסוג \L{$1_{e,k}$}: נבדוק האם יש \L{$\sigma$} סופית שמתיישבת עם \L{$f_{n}$} כך ש-\L{$T_{e}^{\sigma}(k)$} עוצרת. אם כן, נגדיר \L{$f_{n+1}=f_{n}\cup\sigma$} אחרת נגדיר \L{$f_{n+1}=f_{n}$}. \item אם \L{$e_{n+1}$} הוא תנאי מסוג \L{$2_{k}$} אז נמצא \L{$m$} מזערי שאיננו בתחום של \L{$f_{n}$} ונגדיר \L{$f_{n+1}=f_{n}\cup\left\langle m,g(k)\right\rangle $}. נגדיר \L{$f={\displaystyle \bigcup_{i=0}^{\infty}}f_{i}$} ואז \L{$f$} פונקציה שלמה. \end{itemize} כדי לממש את הבניה: \begin{itemize} \item אם אנחנו בתנאי \L{$1_{e,k}$} צריך לדעת האם קיים \L{$\sigma$} כזה. כדי לענות על השאלה הזו אנו יכולים מ-\L{$0^{\prime}$}. \item אם אנחנו בתנאי מסוג \L{$2_{k}$}, אין בעיה למצוא את \L{$m$}. כל מה שצריך זה לחשב את \L{$g(k)$} ואת זה אפשר לעשות מ-\L{$g$}. \end{itemize} נשאר להראות כי את \L{$b^{\prime}$} ניתן לחשב מ-\L{$b$} ומ-\L{$0^{\prime}$} אבל \L{$b^{\prime}=deg(f^{*})$} ו-\L{$f^{*}$} זהו האוב שעונה לכל שאלה מהצורה \char`\"{}האם \L{$T_{e}^{f}(k)$} עוצרת?\char`\"{}. ראשית אם אנו יודעים את הבניה של \L{$t$} אז אנו יודעים לענות על כל השאלות מהצורה הנ\char`\"{}ל. אבל הבניה חשיבה גם מ-\L{$0^{\prime}$} וגם מ-\L{$b^{\prime}$} )ביחד( ולכן \L{$b^{\prime}\le b\cup0^{\prime}$} כנדרש. \end{proof} \begin{corollary} הפונקציה \L{$a\rightarrow a^{\prime}$} איננה חח\char`\"{}ע.\end{corollary} \end{document}