From 4e8805e241c93f306016a51872362e35ffe13866 Mon Sep 17 00:00:00 2001 From: Yuval Adam Date: Sun, 26 Oct 2014 17:43:34 +0200 Subject: Initial Lyx, LaTeX and PDF files --- notes.lyx | 19565 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 19565 insertions(+) create mode 100644 notes.lyx (limited to 'notes.lyx') diff --git a/notes.lyx b/notes.lyx new file mode 100644 index 0000000..99e5308 --- /dev/null +++ b/notes.lyx @@ -0,0 +1,19565 @@ +#LyX 2.1 created this file. For more info see http://www.lyx.org/ +\lyxformat 474 +\begin_document +\begin_header +\textclass heb-article +\begin_preamble +\date{} +\end_preamble +\use_default_options true +\maintain_unincluded_children false +\language hebrew +\language_package default +\inputencoding auto +\fontencoding global +\font_roman default +\font_sans default +\font_typewriter default +\font_math auto +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_osf false +\font_sf_scale 100 +\font_tt_scale 100 +\graphics default +\default_output_format default +\output_sync 0 +\bibtex_command default +\index_command default +\paperfontsize default +\spacing single +\use_hyperref false +\papersize default +\use_geometry false +\use_package amsmath 1 +\use_package amssymb 1 +\use_package cancel 1 +\use_package esint 1 +\use_package mathdots 0 +\use_package mathtools 1 +\use_package mhchem 1 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 +\cite_engine basic +\cite_engine_type default +\biblio_style plain +\use_bibtopic false +\use_indices false +\paperorientation portrait +\suppress_date false +\justification true +\use_refstyle 0 +\index אינדקס +\shortcut idx +\color #008000 +\end_index +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\paragraph_indentation default +\quotes_language english +\papercolumns 1 +\papersides 1 +\paperpagestyle default +\tracking_changes false +\output_changes false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\end_header + +\begin_body + +\begin_layout Title +אי שלמות ואי כריעות בשפות פורמליות +\begin_inset Newline newline +\end_inset + +ד"ר אסף חסון, אוניברסיטת בן-גוריון בנגב +\end_layout + +\begin_layout Author +יובל אדם +\end_layout + +\begin_layout Standard + +\lang english +\begin_inset Box Frameless +position "t" +hor_pos "c" +has_inner_box 1 +inner_pos "t" +use_parbox 0 +use_makebox 0 +width "100col%" +special "none" +height "1in" +height_special "totalheight" +status open + +\begin_layout Quote + +\lang english +Young man, in mathematics you don't understand things. +\begin_inset Newline newline +\end_inset + +You just get used to them. +\end_layout + +\begin_deeper +\begin_layout Quote + +\lang english +- John von Neumann +\end_layout + +\end_deeper +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset CommandInset toc +LatexCommand tableofcontents + +\end_inset + + +\end_layout + +\begin_layout Section +פרולוג +\end_layout + +\begin_layout Itemize +מספור הקטעים תואם למספור ההרצאות. + )נשאיר כתרגיל לקורא החרוץ להבין מה זה אומר על פרק זה...( +\end_layout + +\begin_layout Itemize +נא להתחשב בסביבה. + נא להדפיס מסמך זה רק אם הדבר הכרחי, ורק את טווח העמודים הנדרש. +\end_layout + +\begin_layout Itemize +תודה לצביקה סקופינסקי על סיכומים של חלק מהשיעורים. +\end_layout + +\begin_layout Itemize +הערות/טענות/בקשות - כתובת המייל שלי היא +\begin_inset Formula $yuv.adm$ +\end_inset + + ולאחר מכן +\begin_inset Formula $gmail.com$ +\end_inset + + +\end_layout + +\begin_layout Itemize +שאו ברכה, עלו והצליחו. +\end_layout + +\begin_layout Section +הגדרות +\end_layout + +\begin_layout Itemize +יהי +\begin_inset Formula $\mathcal{M}$ +\end_inset + + מבנה לשפה מסדר ראשון +\begin_inset Formula $L$ +\end_inset + +, +\begin_inset Formula $s$ +\end_inset + + השמה ל +\begin_inset Formula $\mathcal{M}$ +\end_inset + + ו- +\begin_inset Formula $t$ +\end_inset + + שם עצם. + אז הערך של +\begin_inset Formula $t$ +\end_inset + + ב- +\begin_inset Formula $\mathcal{M}$ +\end_inset + + עבור ההשמה +\begin_inset Formula $s$ +\end_inset + + הוא: +\end_layout + +\begin_layout Itemize +אם +\begin_inset Formula $t$ +\end_inset + + קבוע אישי +\begin_inset Formula $c$ +\end_inset + + אז +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit + +\begin_inset Formula $Val_{\mathcal{M}}(t,s)=c^{\mathcal{M}}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +אם +\begin_inset Formula $t$ +\end_inset + + משתנה אישי +\begin_inset Formula $x$ +\end_inset + + אז +\begin_inset Formula $Val_{\mathcal{M}}(t,s)=s(x)$ +\end_inset + + +\end_layout + +\begin_layout Itemize +אם +\begin_inset Formula $t=f(t_{1},...,t_{n})$ +\end_inset + + אז +\begin_inset Formula $Val_{\mathcal{M}}(t,s)=f^{\mathcal{M}}(Val_{\mathcal{M}}(t_{1},s),...,Val_{\mathcal{M}}(t_{n},s))$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\noindent +יהיו +\begin_inset Formula $\mathcal{M}$ +\end_inset + +, +\begin_inset Formula $L$ +\end_inset + + , ו- +\begin_inset Formula $s$ +\end_inset + + כנ"ל ותהי +\begin_inset Formula $\varphi$ +\end_inset + + נוסחה ב- +\begin_inset Formula $L$ +\end_inset + + אז ערך האמת של ) +\lang english +TRUE +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +\lang hebrew + או +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +\lang english +FALSE +\lang hebrew +( של +\begin_inset Formula $\varphi$ +\end_inset + + ב +\begin_inset Formula $\mathcal{M}$ +\end_inset + + עבור ההשמה +\begin_inset Formula $s$ +\end_inset + + מוגדר באינדוקציה באופן הבא: +\end_layout + +\begin_deeper +\begin_layout Itemize +\noindent +אם +\begin_inset Formula $\varphi$ +\end_inset + + נוסחה אטומית, כלומר +\begin_inset Formula $\varphi$ +\end_inset + + מהצורה +\begin_inset Formula $R(t_{1},...,t_{n})$ +\end_inset + + עבור הסימן יחס n-מקומי +\begin_inset Formula $R$ +\end_inset + + ושמות עצם +\begin_inset Formula $t_{1},...,t_{n}$ +\end_inset + + אזי +\begin_inset Formula +\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*} + +\end_inset + +. +\end_layout + +\begin_layout Itemize +\noindent +אם +\begin_inset Formula $\varphi=\neg\psi$ +\end_inset + + עבור נוסחה +\begin_inset Formula $\psi$ +\end_inset + + אז +\begin_inset Formula +\begin{eqnarray*} +Val_{\mathcal{M}}(\varphi,s) & = & TRUE\iff Val_{\mathcal{M}}(\psi,s)=FALSE +\end{eqnarray*} + +\end_inset + + +\end_layout + +\begin_layout Itemize +\noindent +באופן דומה עבור יתר הקשרים הלוגיים +\end_layout + +\begin_layout Itemize +\noindent +אם +\begin_inset Formula $\varphi=(\exists x)\psi$ +\end_inset + + )כלומר הנוסחה היא מסוג "קיים איקס" וההמשך הוא נוסחה קטנה יותר( אז +\begin_inset Formula +\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*} + +\end_inset + + כאשר +\begin_inset Formula $s\left[{x\atop a}\right]$ +\end_inset + + הינה ההשמה אשר נותנת לכל משתנה אישי +\begin_inset Formula $y$ +\end_inset + + שאינו +\begin_inset Formula $x$ +\end_inset + + את הערך +\begin_inset Formula $s(y)$ +\end_inset + + ולמשתנה האישי +\begin_inset Formula $x$ +\end_inset + + את הערך +\begin_inset Formula $a$ +\end_inset + + )כלומר רק מחליפה את +\begin_inset Formula $x$ +\end_inset + +(. + הגדרה שקולה: +\begin_inset Formula +\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*} + +\end_inset + + כאשר נגדיר שרירותית +\begin_inset Formula $Fk_{1} +\end{cases} +\end{eqnarray*} + +\end_inset + +מכיוון ש- +\begin_inset Formula $\Theta_{i}\in\Gamma$ +\end_inset + + לכל +\begin_inset Formula $i$ +\end_inset + + גמרנו. + +\begin_inset Formula $\Gamma^{\prime}$ +\end_inset + + היא המועמדת שלנו לספק את הטענה ונותר להראות ש +\begin_inset Formula $\Gamma\equiv\Gamma^{\prime}$ +\end_inset + +. + מספיק להראות שאם +\begin_inset Formula $\mathcal{M}\models\Gamma$ +\end_inset + + אז +\begin_inset Formula $\mathcal{M}\models\Gamma^{\prime}$ +\end_inset + +. + יהי +\begin_inset Formula $\psi\in\Gamma^{\prime}$ +\end_inset + + ונניח כמו קודם +\begin_inset Formula $\psi={\displaystyle \bigwedge_{i=1}^{k}}\varphi_{i}$ +\end_inset + + עבור +\begin_inset Formula $\varphi_{i}\in\Gamma$ +\end_inset + + כלשהו. +\end_layout + +\begin_layout Proof +אזי: +\begin_inset Formula +\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*} + +\end_inset + + מתקיים אמ"ם לכל +\begin_inset Formula $1\le i\le k$ +\end_inset + + +\begin_inset Formula $Val_{\mathcal{M}}(\varphi_{i})=TRUE$ +\end_inset + +. + כיוון ש +\begin_inset Formula $\mathcal{M}\models\Gamma$ +\end_inset + + אז +\begin_inset Formula $\mathcal{M}\models\varphi_{i}$ +\end_inset + + לכל +\begin_inset Formula $i$ +\end_inset + + ולכן +\begin_inset Formula $\mathcal{M}\models\psi$ +\end_inset + +. + +\end_layout + +\begin_layout Definition +קבוצת פסוקים +\begin_inset Formula $\Gamma$ +\end_inset + + נקראת ספיקה מקומית אם כל תת קבוצה סופית שלה היא ספיקה. +\end_layout + +\begin_layout Theorem +)משפט הקומפקטיות - נוסח שקול( קבוצת פסוקים +\begin_inset Formula $\Gamma$ +\end_inset + + היא ספיקה מקומית אם ורק אם היא ספיקה. +\end_layout + +\begin_layout Proof +נוכיח שמשפט הקומפקטיות גורר את הנוסח הזה. + תהי +\begin_inset Formula $\Gamma$ +\end_inset + + קבוצת פסוקים ספיקה מקומית. + תהי +\begin_inset Formula $\Gamma^{\prime}$ +\end_inset + + כמובטח בטענה, כלומר +\begin_inset Formula $\Gamma^{\prime}\equiv\Gamma$ +\end_inset + + ו +\begin_inset Formula $\Gamma^{\prime}$ +\end_inset + + סגורה תחת +\begin_inset Formula $\wedge$ +\end_inset + +. + מספיק להראות לפי משפט הקומפקטיות שכל פסוק ב +\begin_inset Formula $\Gamma^{\prime}$ +\end_inset + + הוא ספיק. + יהי +\begin_inset Formula $\psi\in\Gamma^{\prime}$ +\end_inset + + אז +\begin_inset Formula ${\displaystyle \psi=\bigwedge_{i=1}^{k}\varphi_{i}}$ +\end_inset + + לאיזה +\begin_inset Formula $\varphi_{1},...,\varphi_{k}\in\Gamma$ +\end_inset + + . + לפי ההנחה +\begin_inset Formula $\Gamma$ +\end_inset + + ספיקה מקומית. + לכן +\begin_inset Formula $\{\varphi_{1},...,\varphi_{k}\}$ +\end_inset + + קבוצת פסוקים ספיקה. + לכן יש מודל +\begin_inset Formula $\mathcal{M}\models\varphi_{i}$ +\end_inset + + לכל +\begin_inset Formula $1\le i\le k$ +\end_inset + + לפי מה שהראנו בהוכחת הטענה +\begin_inset Formula $\mathcal{M}\models\psi$ +\end_inset + +. + לכן +\begin_inset Formula $\Gamma^{\prime}$ +\end_inset + + סגורה תחת חיתוך וכל +\begin_inset Formula $\psi\in\Gamma^{\prime}$ +\end_inset + + ספיק. + לפי משפט הקומפקטיות עבור +\begin_inset Formula $\Gamma^{\prime}$ +\end_inset + + יש +\begin_inset Formula $\mathcal{M}\models\Gamma^{\prime}$ +\end_inset + + אבל +\begin_inset Formula $\Gamma\equiv\Gamma^{\prime}$ +\end_inset + + לכן +\begin_inset Formula $\mathcal{M}\models\Gamma^{\prime}$ +\end_inset + +. + +\end_layout + +\begin_layout Proof +נוכיח את הכיוון השני )שהנוסח הזה גורר את משפט הקומפקטיות(. + נניח +\begin_inset Formula $\Gamma$ +\end_inset + + מקיימת את ההנחות כלומר +\begin_inset Formula $\Gamma^{\prime}$ +\end_inset + + סגורה תחת +\begin_inset Formula $\wedge$ +\end_inset + + וכל פסוק בה ספיק. + יספיק להראות בעזרת הנוסח השקול ש +\begin_inset Formula $\Gamma$ +\end_inset + + ספיקה מקומית. + נוכיח באינדוקציה על +\begin_inset Formula $k$ +\end_inset + + שכל קבוצת פסוקים מגודל +\begin_inset Formula $k$ +\end_inset + + ב- +\begin_inset Formula $\Gamma$ +\end_inset + + היא ספיקה. + עבור +\begin_inset Formula $k=1$ +\end_inset + + - נתון. + נניח ש +\begin_inset Formula $\{\varphi_{1},...,\varphi_{k}\}\subseteq\Gamma$ +\end_inset + + והראנו עבור כל קבוצת פסוקים מגודל +\begin_inset Formula $k-1$ +\end_inset + + שהיא ספיקה. + כיוון ש +\begin_inset Formula $\Gamma$ +\end_inset + + סגורה תחת חיתוך +\begin_inset Formula $\varphi_{1}\wedge\varphi_{2}\in\Gamma$ +\end_inset + + . + +\begin_inset Formula $\Delta=\{\varphi_{1}\wedge\varphi_{2},\varphi_{3},...,\varphi_{k}\}$ +\end_inset + + היא קבוצה בגודל +\begin_inset Formula $k-1$ +\end_inset + + ולכן לפי הנחת האינדוקציה היא ספיקה. + אם +\begin_inset Formula $\mathcal{M}\models\Delta$ +\end_inset + + אז +\begin_inset Formula $\mathcal{M}\models\varphi_{i}$ +\end_inset + + לכל +\begin_inset Formula $i\ge3$ +\end_inset + + וכן +\begin_inset Formula $\mathcal{M}\models\varphi_{1}\wedge\varphi_{2}$ +\end_inset + + . + אבל +\begin_inset Formula $\mathcal{M}\models\varphi_{1}\wedge\varphi_{2}\iff\mathcal{M}\models\varphi_{1}\wedge\mathcal{M}\models\varphi_{2}$ +\end_inset + + ולכן +\begin_inset Formula $\mathcal{M}\models\{\varphi_{1},...,\varphi_{k}\}$ +\end_inset + + כנדרש. + כלומר +\begin_inset Formula $\Gamma$ +\end_inset + + ספיקה מקומית וע"ס הנוסח השקול - ספיקה. +\end_layout + +\begin_layout Definition +תהי +\begin_inset Formula $I$ +\end_inset + + קבוצה )בד"כ אינסופית אבל לא בהכרח(. + מסנן ) +\lang english +filter +\lang hebrew +( על +\begin_inset Formula $I$ +\end_inset + + זו קבוצה +\begin_inset Formula $F\subseteq\mathbb{P}(I)$ +\end_inset + + )כלומר אוסף של תת קבוצות של +\begin_inset Formula $I$ +\end_inset + +( כך שמתקיים: +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $\emptyset\not\in F$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $J\in F$ +\end_inset + + ו- +\begin_inset Formula $J\subseteq J^{\prime}$ +\end_inset + + אז +\begin_inset Formula $J^{\prime}\in F$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $J,J^{\prime}\in F$ +\end_inset + + אז +\begin_inset Formula $J\cap J^{\prime}\in F$ +\end_inset + + +\end_layout + +\begin_layout Standard +אם בנוסף לכל +\begin_inset Formula $J\subseteq I$ +\end_inset + + אם +\begin_inset Formula $J\not\in F$ +\end_inset + + אז +\begin_inset Formula $I\backslash J\in F$ +\end_inset + + - אז +\begin_inset Formula $F$ +\end_inset + + נקרא על מסנן. +\end_layout + +\end_deeper +\begin_layout Standard +דוגמאות: +\end_layout + +\begin_layout Itemize +תהי +\begin_inset Formula $I$ +\end_inset + + קבוצה כלשהי. + לכל +\begin_inset Formula $a\in I$ +\end_inset + + נגדיר על מסנן +\begin_inset Formula $F_{a}$ +\end_inset + + באופן הבא: +\begin_inset Formula $J\subseteq I,J\in F$ +\end_inset + + אמ"ם +\begin_inset Formula $a\in J$ +\end_inset + + .)הערה: על מסנן +\begin_inset Formula $F$ +\end_inset + + על +\begin_inset Formula $I$ +\end_inset + + נקרא ראשי אם קיים +\begin_inset Formula $I$ +\end_inset + + כך ש- +\begin_inset Formula $F=F_{a}$ +\end_inset + +(. +\end_layout + +\begin_layout Itemize +אם +\begin_inset Formula $I$ +\end_inset + + סופית אז כל על מסנן על +\begin_inset Formula $I$ +\end_inset + + הוא ראשי. + יהי +\begin_inset Formula $F$ +\end_inset + + על מסנן על +\begin_inset Formula $I$ +\end_inset + +. + כיוון ש- +\begin_inset Formula $I$ +\end_inset + + סופית גם +\begin_inset Formula $F$ +\end_inset + + סופית ולכן באינדוקציה לפי +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +3 +\numeric off +: +\begin_inset Formula $J_{F}=\{\bigcap J:J\in F\}$ +\end_inset + + ו- +\begin_inset Formula $J_{F}\in F$ +\end_inset + +. + אם +\begin_inset Formula $J_{F}$ +\end_inset + + יחידון - גמרנו. + נניח בשלילה שזה לא המקרה. + אחרת יש +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +2 +\family roman +\series medium +\shape up +\size normal +\emph off +\numeric off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +איברים שונים ב +\begin_inset Formula $J_{F}$ +\end_inset + + )לפחות(. + ניקח +\begin_inset Formula $J\subseteq I$ +\end_inset + + שמכילה את הראשון אבל לא את השני. + לא +\begin_inset Formula $J$ +\end_inset + + ולא המשלים של +\begin_inset Formula $J$ +\end_inset + + יכולים להיות ב +\begin_inset Formula $F$ +\end_inset + + כי כל קבוצה ב +\begin_inset Formula $F$ +\end_inset + + מכילה את +\begin_inset Formula $J_{F}$ +\end_inset + +. + +\end_layout + +\begin_layout Itemize +תהי +\begin_inset Formula $I$ +\end_inset + + קבוצה אינסופית. + נגדיר +\begin_inset Formula $F=\{U\subseteq I:|I\backslash U|<\aleph_{0}(finite)\}$ +\end_inset + +. + תרגיל: זהו מסנן שאינו על מסנן. + +\end_layout + +\begin_layout Claim +תהי +\begin_inset Formula $I$ +\end_inset + + קבוצה לא ריקה. + +\begin_inset Formula $F$ +\end_inset + + מסנן על +\begin_inset Formula $I$ +\end_inset + + אזי קיים על מסנן +\begin_inset Formula $F\subseteq F^{\prime}$ +\end_inset + +. + במילים אחרות כל מסנן על +\begin_inset Formula $I$ +\end_inset + + ניתן להרחבה לעל מסנן. + )הוכחה בשיעור הבא(. +\end_layout + +\begin_layout Section +מסננים והלמה של צורן +\end_layout + +\begin_layout Definition +תהי +\begin_inset Formula $I$ +\end_inset + + קבוצה )לא ריקה( אז +\series bold +מסנן +\series default + +\begin_inset Formula $F$ +\end_inset + + על +\begin_inset Formula $I$ +\end_inset + + זה אוסף של תת קבוצות של +\begin_inset Formula $I$ +\end_inset + + כך ש: +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $\emptyset\not\in F$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $U_{1},U_{2}\in F$ +\end_inset + + אז +\begin_inset Formula $U_{1}\wedge U_{2}\in F$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $U\in F$ +\end_inset + + ו- +\begin_inset Formula $U\subseteq V$ +\end_inset + + אז +\begin_inset Formula $V\in F$ +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Formula $F$ +\end_inset + + הוא על-מסנן אם לכל +\begin_inset Formula $V\subseteq I$ +\end_inset + + אם +\begin_inset Formula $V\not\in F$ +\end_inset + + אז +\begin_inset Formula $I\backslash V\in F$ +\end_inset + + . +\end_layout + +\end_deeper +\begin_layout Lemma + +\bar under +הלמה של צורן +\bar default + - תהי +\begin_inset Formula $(I,\le)$ +\end_inset + + קבוצה סדורה חלקית. + +\begin_inset Formula $V\subseteq I$ +\end_inset + + תקרא שרשרת אם לכל +\begin_inset Formula $v_{1},v_{2}\in V$ +\end_inset + + או +\begin_inset Formula $v_{1}\le v_{2}$ +\end_inset + + או +\begin_inset Formula $v_{2}\le v_{1}$ +\end_inset + +. + אז נניח שלכל שרשרת +\begin_inset Formula $V\subseteq I$ +\end_inset + + יש חסם מלעיל, כלומר קיים +\begin_inset Formula $w\in I$ +\end_inset + + כך ש- +\begin_inset Formula $w\ge V$ +\end_inset + + )כלומר +\begin_inset Formula $w\ge v$ +\end_inset + + לכל +\begin_inset Formula $v\in V$ +\end_inset + +(. + אזי ב +\begin_inset Formula $(I,\le)$ +\end_inset + + יש איבר מירבי, כלומר קיים +\begin_inset Formula $u\in I$ +\end_inset + + כך שלכל +\begin_inset Formula $u\not=v\in I$ +\end_inset + + מתקיים +\begin_inset Formula $u\not\le v$ +\end_inset + +. +\end_layout + +\begin_layout Claim +תהי +\begin_inset Formula $I$ +\end_inset + + קבוצה לא ריקה ו- +\begin_inset Formula $F$ +\end_inset + + מסנן על +\begin_inset Formula $I$ +\end_inset + +. + אזי קיים על-מסנן +\begin_inset Formula $F\subseteq U$ +\end_inset + +. + במילים אחרות, כל מסנן +\begin_inset Formula $F$ +\end_inset + + על +\begin_inset Formula $I$ +\end_inset + + ניתן להרחבה לעל-מסנן. +\end_layout + +\begin_deeper +\begin_layout Proof +תהי +\begin_inset Formula $\mathcal{H}$ +\end_inset + + קבוצת כל המסננים על +\begin_inset Formula $I$ +\end_inset + +. + לאינטואיציה: +\begin_inset Formula $F\in\mathbb{P}(\mathbb{P}(I))$ +\end_inset + + אז +\begin_inset Formula $\mathcal{H}\subseteq\mathbb{P}(\mathbb{P}(I)$ +\end_inset + + או +\begin_inset Formula $\mathcal{H}\in\mathbb{P}(\mathbb{P}(\mathbb{P}(I)))$ +\end_inset + +. + על +\begin_inset Formula $\mathcal{H}$ +\end_inset + + אפשר להגדיר סדר חלקי ע"י הכלה. + כלומר, ל- +\begin_inset Formula $F_{1},F_{2}\in\mathcal{H}$ +\end_inset + + נאמר ש +\begin_inset Formula $F_{1}\le F_{2}$ +\end_inset + + אם לכל +\begin_inset Formula $V\in F_{1}$ +\end_inset + + מתקיים גם +\begin_inset Formula $V\in F_{2}$ +\end_inset + +. + אפשר לכתוב גם +\begin_inset Formula $F_{1}\subseteq F_{2}$ +\end_inset + +. + נרצה להשתמש בלמה של צורן, לכן עלינו להראות שאם +\begin_inset Formula $V\subseteq\mathcal{H}$ +\end_inset + + שרשרת אז ל +\begin_inset Formula $V$ +\end_inset + + יש חסם מלעיל ב +\begin_inset Formula $\mathcal{H}$ +\end_inset + +. + נגדיר +\begin_inset Formula $F_{V}={\displaystyle \bigcup V}=\{U\subseteq I:U\in F,\, for\, some\, F\in V\}$ +\end_inset + +. + נראה ש +\begin_inset Formula $F_{V}$ +\end_inset + + הוא מסנן. + +\end_layout + +\begin_deeper +\begin_layout Enumerate +ברור כי +\begin_inset Formula $\emptyset\not\in F_{V}$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +נניח ש +\begin_inset Formula $U_{1},U_{2}\in F_{V}$ +\end_inset + +. + קיימים +\begin_inset Formula $F_{1},F_{2}\in V$ +\end_inset + + כך ש +\begin_inset Formula $U_{1}\in F_{1}$ +\end_inset + + וגם +\begin_inset Formula $U_{2}\in F_{2}$ +\end_inset + +. + כיוון ש- +\begin_inset Formula $V$ +\end_inset + + שרשרת, ב.ה.כ +\begin_inset Formula $F_{1}\subseteq F_{2}$ +\end_inset + + . + לכן +\begin_inset Formula $U_{1}\in F_{2}$ +\end_inset + + לכן גם +\begin_inset Formula $U_{1}\cap U_{2}\in F_{2}$ +\end_inset + + ולכן +\begin_inset Formula $U_{1}\cap U_{2}\in F_{V}$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $U\in F_{V}$ +\end_inset + + ו- +\begin_inset Formula $U\subseteq W$ +\end_inset + + אז לפי הגדרה קיים איזה +\begin_inset Formula $F\in V$ +\end_inset + + כך ש- +\begin_inset Formula $U\in F$ +\end_inset + +. + לכן גם +\begin_inset Formula $W\in F$ +\end_inset + + ולכן +\begin_inset Formula $W\in F_{V}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +הראנו שלכל שרשרת ב +\begin_inset Formula $\mathcal{H}$ +\end_inset + + יש חסם מלעיל, כי ברור +\begin_inset Formula $F_{V}\in\mathcal{H}$ +\end_inset + + ו- +\begin_inset Formula $F\subseteq F_{V}$ +\end_inset + + לכל +\begin_inset Formula $F\in V$ +\end_inset + + כלומר +\begin_inset Formula $F_{V}$ +\end_inset + + חסם מלעיל ל- +\begin_inset Formula $V$ +\end_inset + +. + לפי הלמה של צורן, ב- +\begin_inset Formula $\mathcal{H}$ +\end_inset + + יש איבר מירבי, נסמנו +\begin_inset Formula $\mathcal{U}$ +\end_inset + +. + נראה ש +\begin_inset Formula $\mathcal{U}$ +\end_inset + + על מסנן. + נניח בשלילה שהוא לא. + כיוון ש- +\begin_inset Formula $\mathcal{U}\in\mathcal{H}$ +\end_inset + + הוא מסנן ולכן הנחת השלילה מבטיחה שיש קבוצה +\begin_inset Formula $U\subseteq I$ +\end_inset + + כך ש- +\begin_inset Formula $U\not\in\mathcal{U}$ +\end_inset + + ו- +\begin_inset Formula $I\backslash U\not\in\mathcal{U}$ +\end_inset + +. + נשים לב כי במקרה זה +\begin_inset Formula $\mathcal{U}_{U}=\mathcal{U}\cup\{W\subseteq I:U\cap V\subseteq W,\, for\, some\, V\in\mathcal{U}\}$ +\end_inset + + הוא מסנן וזאת תהיה סתירה למירביות של +\begin_inset Formula $\mathcal{U}$ +\end_inset + + כי +\begin_inset Formula $\mathcal{U}\not\subseteq\mathcal{U}_{U}$ +\end_inset + +. + מדוע +\begin_inset Formula $\mathcal{U}_{U}$ +\end_inset + + הוא מסנן? +\end_layout + +\begin_layout Enumerate +נוכיח ש +\begin_inset Formula $\emptyset\in\mathcal{U}_{U}$ +\end_inset + +. + אם +\begin_inset Formula $\emptyset\in\mathcal{U}_{U}$ +\end_inset + + הרי שהיא מהצורה +\begin_inset Formula $U\cap V$ +\end_inset + + לאיזה +\begin_inset Formula $V\in\mathcal{U}$ +\end_inset + +. + אבל אז +\begin_inset Formula $V\subseteq I\backslash U$ +\end_inset + + ואז +\begin_inset Formula $I\backslash U\in\mathcal{U}$ +\end_inset + + בסתירה. +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $\mathcal{U}_{U}$ +\end_inset + + סגורה כלפי מעלה מעצם הגדרתה. + +\end_layout + +\begin_layout Enumerate +נראה כי אם +\begin_inset Formula $U_{1},U_{2}\in\mathcal{U}_{U}$ +\end_inset + + אז גם +\begin_inset Formula $U_{1}\cap U_{2}\in\mathcal{U}_{U}$ +\end_inset + +. + ב.ה.כ +\begin_inset Formula $U_{1}\not\in\mathcal{U}$ +\end_inset + +. + לכן +\begin_inset Formula $U\cap V\subseteq U$ +\end_inset + + לאיזה +\begin_inset Formula $V\in\mathcal{U}$ +\end_inset + +. + לכן +\begin_inset Formula $U\cap V\cap U_{2}\subseteq U_{2}\cap U_{1}$ +\end_inset + + עבור +\begin_inset Formula $V$ +\end_inset + + הזו. + אם +\begin_inset Formula $U_{2}\in\mathcal{U}$ +\end_inset + + אז +\begin_inset Formula $V\cap U_{2}\in\mathcal{U}$ +\end_inset + + ולכן +\begin_inset Formula $U\cap(V\cap U_{2})\in\mathcal{U}_{U}$ +\end_inset + + וכך גם +\begin_inset Formula $U_{1}\cap U_{2}$ +\end_inset + +. + אחרת +\begin_inset Formula $U\cap V_{2}\subseteq U_{2}$ +\end_inset + + לאיזה +\begin_inset Formula $V_{2}\in\mathcal{U}$ +\end_inset + + . + ואז +\begin_inset Formula $U\cap(V\cap V_{2})\subseteq U_{1}\cap U_{2}$ +\end_inset + + וגם +\begin_inset Formula $U\cap(V\cap V_{2})\in\mathcal{U}_{U}$ +\end_inset + +. + קיבלנו +\begin_inset Formula $\mathcal{U}_{U}\in\mathcal{H}$ +\end_inset + + ו- +\begin_inset Formula $\mathcal{U}\not\in\mathcal{U}_{U}$ +\end_inset + + סתירה. + לכן +\begin_inset Formula $\mathcal{U}$ +\end_inset + + על מסנן. + +\end_layout + +\begin_layout Standard +)הרחבה( אם +\begin_inset Formula $F$ +\end_inset + + מסנן על +\begin_inset Formula $I$ +\end_inset + + נגדיר +\begin_inset Formula $\mathcal{H}_{F}\subseteq\mathcal{H}$ +\end_inset + + אוסף המסננים המכילים את +\begin_inset Formula $F$ +\end_inset + +. + באופן טריויאלי לכל שרשרת ב- +\begin_inset Formula $\mathcal{H}_{F}$ +\end_inset + + יש חסם מלעיל ב- +\begin_inset Formula $\mathcal{H_{F}}$ +\end_inset + +)כי כל שרשרת כזו היא שרשרת של איברים שגדולים מ- +\begin_inset Formula $F$ +\end_inset + + ולכן אם יש לה חסם ב +\begin_inset Formula $\mathcal{H}$ +\end_inset + + הרי שהוא חסם ב +\begin_inset Formula $\mathcal{H}_{F}$ +\end_inset + +. + לכן +\begin_inset Formula $\mathcal{H}_{F}$ +\end_inset + +מקיימת את הלמה של צורן, לכן יש איבר מירבי גם ב +\begin_inset Formula $\mathcal{H}$ +\end_inset + +וראינו שאלו על מסננים. +\end_layout + +\end_deeper +\begin_layout Corollary +לכל קבוצה אינסופית +\begin_inset Formula $I$ +\end_inset + + יש על מסנן +\begin_inset Formula $F$ +\end_inset + + על +\begin_inset Formula $I$ +\end_inset + + כך שאם +\begin_inset Formula $|I\backslash U|<\aleph_{0}$ +\end_inset + + אז +\begin_inset Formula $U\in F$ +\end_inset + +. +\end_layout + +\begin_layout Definition + +\bar under +מכפלות +\bar default +: תהי +\begin_inset Formula $\Gamma$ +\end_inset + +קבוצה לא ריקה כלשהי ו- +\begin_inset Formula $\{M_{\gamma}\}_{\gamma\in\Gamma}$ +\end_inset + + אוסף של קבוצות לא ריקות. + אז המכפלה +\begin_inset Formula ${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$ +\end_inset + + זה אוסף כל הפונקציות +\begin_inset Formula $f:\Gamma\rightarrow{\displaystyle \bigcup_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$ +\end_inset + + המקיימות +\begin_inset Formula $f(\gamma)\in\mathcal{M}_{\gamma}$ +\end_inset + +. + הערה: אם +\begin_inset Formula $\Gamma=\{1,...,n\}$ +\end_inset + + ו- +\begin_inset Formula $\mathcal{M}_{i}=\mathcal{M}_{j}$ +\end_inset + + לכל +\begin_inset Formula $i,j$ +\end_inset + + אז +\begin_inset Formula ${\displaystyle \prod_{i=1}^{n}\mathcal{M}=\mathcal{M}^{n}}$ +\end_inset + +. +\end_layout + +\begin_layout Theorem + +\bar under +אקסיומת הבחירה +\bar default +: אם +\begin_inset Formula $\Gamma$ +\end_inset + +לא ריקה ו- +\begin_inset Formula $\mathcal{M}_{\gamma}\not=\emptyset$ +\end_inset + + לכל +\begin_inset Formula $\gamma\in\Gamma$ +\end_inset + + אז +\begin_inset Formula ${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}\not=\emptyset}$ +\end_inset + +. +\end_layout + +\begin_layout Section +מכפלות +\end_layout + +\end_deeper +\begin_layout Definition + +\bar under +מכפלות +\bar default +: תהי +\begin_inset Formula $\Gamma$ +\end_inset + + קבוצה לא ריקה כלשהי ו- +\begin_inset Formula $\{M_{\gamma}\}_{\gamma\in\Gamma}$ +\end_inset + + אוסף של קבוצות לא ריקות. + אז המכפלה +\begin_inset Formula ${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$ +\end_inset + + זה אוסף כל הפונקציות +\begin_inset Formula $f:\Gamma\rightarrow{\displaystyle \bigcup_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$ +\end_inset + + המקיימות +\begin_inset Formula $f(\gamma)\in\mathcal{M}_{\gamma}$ +\end_inset + +. + הערה: אם +\begin_inset Formula $\Gamma=\{1,...,n\}$ +\end_inset + + ו- +\begin_inset Formula $\mathcal{M}_{i}=\mathcal{M}_{j}$ +\end_inset + + לכל +\begin_inset Formula $i,j$ +\end_inset + + אז +\begin_inset Formula ${\displaystyle \prod_{i=1}^{n}\mathcal{M}=\mathcal{M}^{n}}$ +\end_inset + +. +\end_layout + +\begin_layout Definition +דוגמה: אם +\begin_inset Formula $\mathcal{M}_{\gamma}=\mathcal{M}$ +\end_inset + + לכל +\begin_inset Formula $\mathcal{M}$ +\end_inset + + אז +\begin_inset Formula ${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}=M^{\Gamma}}$ +\end_inset + +זה פשוט אוסף כל הפונקציות מ +\begin_inset Formula $\Gamma$ +\end_inset + + ל +\begin_inset Formula $\mathcal{M}$ +\end_inset + +. + +\end_layout + +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Definition +אם +\begin_inset Formula $\Gamma$ +\end_inset + +לא ריקה ו- +\begin_inset Formula $\mathcal{M}_{\gamma}\not=\emptyset$ +\end_inset + + לכל +\begin_inset Formula $\gamma\in\Gamma$ +\end_inset + +. + תהי +\begin_inset Formula $\mathcal{M}=\prod\mathcal{M}_{\gamma}$ +\end_inset + +. + ל +\begin_inset Formula $\bar{x},\bar{y}\in\mathcal{M}$ +\end_inset + + נגדיר +\begin_inset Formula $x\sim_{F}y$ +\end_inset + + עבור על מסנן +\begin_inset Formula $F$ +\end_inset + + על +\begin_inset Formula $\Gamma$ +\end_inset + + אם +\begin_inset Formula $\{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{y}(\gamma)\}\in F$ +\end_inset + +. + +\end_layout + +\begin_layout Claim +בסימונים של ההגדרה האחרונה +\begin_inset Formula $\sim_{F}$ +\end_inset + + הוא יחס שקילות. + +\end_layout + +\begin_layout Proof +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $\{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{y}(\gamma)\}=\Gamma\in F$ +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $\{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{y}(\gamma)\}=\{\gamma\in\Gamma:\bar{y}(\gamma)=\bar{x}(\gamma)\}$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +נניח ש +\begin_inset Formula $x\sim_{F}y$ +\end_inset + + ו- +\begin_inset Formula $y\sim_{F}z$ +\end_inset + + אז +\begin_inset Formula +\begin{eqnarray*} +U & = & \{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{y}(\gamma)\}\in F +\end{eqnarray*} + +\end_inset + + וגם +\begin_inset Formula +\begin{eqnarray*} +V & = & \{\gamma\in\Gamma:\bar{y}(\gamma)=\bar{z}(\gamma)\}\in F +\end{eqnarray*} + +\end_inset + + לכן +\begin_inset Formula $U\cap V\in F$ +\end_inset + + אבל +\begin_inset Formula $U\cap V\subseteq\{\gamma\in\Gamma:\bar{x}(\gamma)=\bar{z}(\gamma)\}\in F$ +\end_inset + +. +\end_layout + +\end_deeper +\end_deeper +\begin_layout Definition +תהי +\begin_inset Formula $\Gamma$ +\end_inset + + קבוצה לא ריקה ולכל +\begin_inset Formula $\gamma\in\Gamma$ +\end_inset + + יהי +\begin_inset Formula $\mathcal{M}_{\gamma}$ +\end_inset + + מבנה לשפה +\begin_inset Formula $\mathcal{L}$ +\end_inset + +. + יהי +\begin_inset Formula $F$ +\end_inset + + על מסנן )לא ראשי( על +\begin_inset Formula $\Gamma$ +\end_inset + + אז העל מכפלה של +\begin_inset Formula $\{\mathcal{M}_{\gamma}\}_{\gamma\in\Gamma}$ +\end_inset + + ביחס ל +\begin_inset Formula $F$ +\end_inset + + שתסומן +\begin_inset Formula $\mathcal{M=}({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})/F$ +\end_inset + + היא המבנה המוגדר כלהלן: +\end_layout + +\begin_layout Enumerate +העולם של העל מכפלה הוא +\begin_inset Formula $({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})/\sim_{F}$ +\end_inset + + כלומר אוסף מחלקות השקילות של היחס +\begin_inset Formula $\sim_{F}$ +\end_inset + + על המכפלה +\begin_inset Formula $({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +לכל קבוע אישי +\begin_inset Formula $c\in\mathcal{L}$ +\end_inset + + נפרש +\begin_inset Formula $[(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}]$ +\end_inset + + מחלקת השקילות של הסדרה +\begin_inset Formula $(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}$ +\end_inset + + ביחס ל +\begin_inset Formula $\sim_{F}$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +לכל סימן יחס n-מקומי +\begin_inset Formula $R\in\mathcal{L}$ +\end_inset + + . + נאמר ש +\begin_inset Formula $[\bar{a_{1}},...,\bar{a_{n}}]\in R^{\mathcal{M}}$ +\end_inset + + אם +\begin_inset Formula $\{\gamma\in\Gamma:(\bar{a_{1}}(\gamma),...,\bar{a_{n}}(\gamma))\in R^{\mathcal{M}_{\gamma}}$ +\end_inset + + . + +\end_layout + +\begin_layout Enumerate +לכל סימן פונקציה n-מקומי +\begin_inset Formula $F$ +\end_inset + +נאמר ש +\begin_inset Formula $F^{\mathcal{M}}[(\bar{a_{1}},...,\bar{a_{n})}]=[b]$ +\end_inset + + אם +\begin_inset Formula $\{\gamma\in\Gamma:F^{\mathcal{M}_{\gamma}}(\bar{a_{1}}(\gamma),...,\bar{a_{n}}(\gamma))=b(\gamma)\}\in F$ +\end_inset + + . + הערה: הנ"ל מוגדר היטב. + כלומר אם +\begin_inset Formula $[b]=[d]$ +\end_inset + + אז +\begin_inset Formula +\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*} + +\end_inset + + כי +\begin_inset Formula $[b]=[d]$ +\end_inset + + כלומר +\begin_inset Formula $b\sim_{F}d$ +\end_inset + + וזאת בדיוק ההגדרה. + +\end_layout + +\begin_layout Theorem +יהיו +\begin_inset Formula $\mathcal{M}=({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})/F$ +\end_inset + + ו- +\begin_inset Formula $\varphi(x_{1},...,x_{n})$ +\end_inset + + נוסחה ו- +\begin_inset Formula $s$ +\end_inset + + השמה ל +\begin_inset Formula $\mathcal{M}$ +\end_inset + +. + אזי מתקיים +\begin_inset Formula $Val_{\mathcal{M}}(\varphi,s)=TRUE$ +\end_inset + + אם ורק אם לכל השמות +\begin_inset Formula $(s_{\gamma})_{\gamma\in\Gamma}$ +\end_inset + + )עם +\begin_inset Formula $s_{\gamma}$ +\end_inset + + השמה ל +\begin_inset Formula $\mathcal{M}_{\gamma}$ +\end_inset + +( כך ש +\begin_inset Formula $[(s_{\gamma})_{\gamma\in\Gamma}]\sim_{F}[s]$ +\end_inset + + מתקיים ש +\begin_inset Formula $\{\gamma\in\Gamma:Val_{\mathcal{M}}(\varphi,s_{\gamma})=TRUE\}\in F$ +\end_inset + +. +\end_layout + +\begin_layout Proof +באינדוקציה על יצירת הנוסחאות. + נתחיל משמות עצם: +\end_layout + +\begin_deeper +\begin_layout Itemize +עבור +\begin_inset Formula $t$ +\end_inset + + קבוע אישי +\begin_inset Formula $c$ +\end_inset + + מתקיים +\begin_inset Formula $Val_{\mathcal{M}}(c,s)=c^{\mathcal{M}}=[(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}]=[Val_{\mathcal{M}_{\gamma}}(c,s)_{\gamma\in\Gamma}]$ +\end_inset + +. + לשם נוחות נקבע השמה +\begin_inset Formula $s_{0}$ +\end_inset + + ל- +\begin_inset Formula ${\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$ +\end_inset + + כך ש- +\begin_inset Formula $[s_{0}]=s$ +\end_inset + +. + כלומר לכל משתנה אישי +\begin_inset Formula $x$ +\end_inset + + מתקיים +\begin_inset Formula $[s_{0}(x)]=s(x)$ +\end_inset + +. + +\end_layout + +\begin_layout Itemize +עבור +\begin_inset Formula $t$ +\end_inset + + משתנה אישי +\begin_inset Formula $x$ +\end_inset + + : +\begin_inset Formula $Val_{\mathcal{M}}(x,s)=\underset{=[s_{\gamma}(x)]}{\underbrace{[s_{0}(x)]}}=s(x)$ +\end_inset + + +\end_layout + +\begin_layout Itemize +עבור +\begin_inset Formula $t$ +\end_inset + + פונקציה +\begin_inset Formula $t=F(t_{1},...,t_{n})$ +\end_inset + + אז +\begin_inset Formula +\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_inset + +עתה נתחיל בהוכחה עבור נוסחאות: +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $\varphi$ +\end_inset + + נוסחה אטומית +\begin_inset Formula $R(t_{1}(x_{1},...,x_{n}),...,t_{m}(x_{1},...,x_{n}))$ +\end_inset + + אז אם ורק אם +\begin_inset Formula +\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*} + +\end_inset + + אם ורק אם לפי מה שהראנו עבור שמות עצם +\begin_inset Formula $[Val_{\mathcal{M}}(t_{i},s)]=[(Val_{\mathcal{M}}(t_{i},s_{\gamma})(\gamma))_{\gamma\in\Gamma}]$ +\end_inset + + לכל +\begin_inset Formula $1\le i\le m$ +\end_inset + +. + לכן, +\begin_inset Formula +\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_inset + + וזה מה שהיינו צריכים . +\end_layout + +\end_deeper +\begin_layout Section +משפט +\family roman +\series bold +\shape up +\size larger +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +\lang english +Los +\family roman +\series bold +\shape up +\size larger +\emph off +\bar no +\noun off +\color none +\lang hebrew + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +והוכחת קומפקטיות +\end_layout + +\begin_layout Theorem + +\bar under +משפט +\family roman +\series medium +\shape up +\size normal +\emph off +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\noun default +\color inherit +\lang english +Los +\bar default +\lang hebrew + תהי +\begin_inset Formula $\mathcal{L}$ +\end_inset + + שפה לתחשיב הפסוקים, +\begin_inset Formula $\Gamma$ +\end_inset + + קבוצה לא ריקה, לכל +\begin_inset Formula $\gamma\in\Gamma$ +\end_inset + + מבנה +\begin_inset Formula $\mathcal{M}_{\gamma}$ +\end_inset + + לשפה +\begin_inset Formula $\mathcal{L}$ +\end_inset + +. + יהי +\begin_inset Formula $F$ +\end_inset + + על מסנן על +\begin_inset Formula $\Gamma$ +\end_inset + + ו- +\begin_inset Formula $s$ +\end_inset + + השמה עבור +\begin_inset Formula $\mathcal{M}=({\displaystyle \prod_{\gamma}\mathcal{M}_{\gamma}}/F)$ +\end_inset + + ו- +\begin_inset Formula $\varphi(x)$ +\end_inset + + נוסחה ב +\begin_inset Formula $\mathcal{L}$ +\end_inset + +. + אזי +\begin_inset Formula $Val_{\mathcal{M}}(\varphi,\bar{s})=TRUE$ +\end_inset + +אם ורק אם לכל השמה +\begin_inset Formula $s$ +\end_inset + + ל- +\begin_inset Formula ${\displaystyle \prod_{\gamma}\mathcal{M}_{\gamma}}$ +\end_inset + + המקיימת +\begin_inset Formula $\bar{s}(x)=[s(x)]$ +\end_inset + + מתקיים: +\begin_inset Formula +\begin{eqnarray*} +\{\gamma & \in & \Gamma:Val_{\mathcal{M}_{\gamma}}(\mathcal{M}_{\gamma},s(\gamma))=TRUE\}\in F +\end{eqnarray*} + +\end_inset + + )כאשר +\begin_inset Formula $s(\gamma)(x)$ +\end_inset + + זה הקואורדינטה ה +\begin_inset Formula $\gamma$ +\end_inset + + של +\begin_inset Formula $s(x)$ +\end_inset + +(. + +\end_layout + +\begin_layout Standard +תזכורת: כיצד מגדירין )"לכבוד פסח" - א. + חסון, חג שמח( מבנה לשפה +\begin_inset Formula $\mathcal{L}$ +\end_inset + + על +\begin_inset Formula ${\displaystyle (\prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}/F)$ +\end_inset + +? +\end_layout + +\begin_layout Itemize +עבור קבוע אישי +\begin_inset Formula $c$ +\end_inset + + פשוט לוקחים את +\begin_inset Formula $[(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}]$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +עבור סימן יחס n-מקומי +\begin_inset Formula $R$ +\end_inset + + נקבע ש- +\begin_inset Formula $\left\langle \bar{a}_{1},...,\bar{a}_{n}\right\rangle \in R^{\mathcal{M}}$ +\end_inset + + אם קיימים +\begin_inset Formula $a_{1},...,a_{n}\in{\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$ +\end_inset + + כך ש +\begin_inset Formula $[a_{1}]=\bar{a_{1}},...,[a_{n}]=\bar{a_{n}}$ +\end_inset + + כך ש- +\begin_inset Formula +\begin{eqnarray*} +\{\gamma & \in & \Gamma:(a_{1}(\gamma),...a_{n}(\gamma))\in R^{\mathcal{M}_{\gamma}}\}\in F +\end{eqnarray*} + +\end_inset + + +\end_layout + +\begin_layout Itemize +עבור סימן פונקציה n-מקומי +\begin_inset Formula $F^{\mathcal{M}}(\bar{a}_{1},...,\bar{a}_{n})=b$ +\end_inset + + אם קיימים +\begin_inset Formula $b,a_{1},...,a_{n}\in{\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$ +\end_inset + + כך ש +\begin_inset Formula $[a_{1}]=\bar{a_{1}},...,[a_{n}]=\bar{a_{n}},[b]=b$ +\end_inset + + כך ש +\begin_inset Formula +\begin{eqnarray*} +\{\gamma & \in & \Gamma:F^{\mathcal{M}}(a_{1}(\gamma),...a_{n}(\gamma))=b(\gamma)\}\in F +\end{eqnarray*} + +\end_inset + +. +\end_layout + +\begin_layout Standard + +\bar under +תרגיל: +\end_layout + +\begin_layout Enumerate +להוכיח כי זה מוגדר היטב, כלומר +\begin_inset Formula $F^{\mathcal{M}}$ +\end_inset + + היא אכן פונקציה. + ז"א עבור +\begin_inset Formula $\bar{a_{1}},...,\bar{a_{n}}\in\mathcal{M}$ +\end_inset + + קיים +\begin_inset Formula $b$ +\end_inset + + יחיד כך ש +\begin_inset Formula $F^{\mathcal{M}}(\bar{a_{1},}...,\bar{a_{n}})=b$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $[a_{1}]=\bar{a_{1}},...,[a_{n}]=\bar{a_{n}}$ +\end_inset + + אז +\begin_inset Formula $F^{\mathcal{M}}(\bar{a_{1}},...,\bar{a_{n}})=[F^{\mathcal{M}}(a_{1}(\gamma),...,a_{n}(\gamma))_{\gamma\in\Gamma}]$ +\end_inset + + +\end_layout + +\begin_layout Proof +ראשית נראה: אם +\begin_inset Formula $t$ +\end_inset + + שם עצם ב +\begin_inset Formula $\mathcal{L}$ +\end_inset + +, +\begin_inset Formula $\bar{s},s$ +\end_inset + + השמות כבניסוח המשפט אז +\begin_inset Formula $Val_{\mathcal{M}}(t,\bar{s})=[(Val_{\mathcal{M}_{\gamma}}(t,s(\gamma)))_{\gamma\in\Gamma}]$ +\end_inset + + באינדוקציה על יציאת +\begin_inset Formula $t$ +\end_inset + +. +\end_layout + +\begin_deeper +\begin_layout Itemize +עבור +\begin_inset Formula $t$ +\end_inset + + קבוע אישי +\begin_inset Formula $c$ +\end_inset + +: +\begin_inset Formula $Val_{\mathcal{M}}(t,\bar{s})=[(c^{\mathcal{M}_{\gamma}})_{\gamma\in\Gamma}]=[(Val_{\mathcal{M}_{\gamma}}(c,s(\gamma)))_{\gamma\in\Gamma}]$ +\end_inset + + +\end_layout + +\begin_layout Itemize +עבור +\begin_inset Formula $t$ +\end_inset + + משתנה אישי +\begin_inset Formula $x$ +\end_inset + +: +\begin_inset Formula $Val_{\mathcal{M}}(t,s)=\bar{s}(x)=[s(\gamma)(x)_{\gamma\in\Gamma}]=[(Val_{\mathcal{M}_{\gamma}}(t,s(\gamma)))_{\gamma\in\Gamma}]$ +\end_inset + + +\end_layout + +\begin_layout Itemize +עבור +\begin_inset Formula $t=F(t_{1},...,t_{n})$ +\end_inset + +: +\begin_inset Formula +\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_inset + + +\end_layout + +\begin_layout Standard +הוכחנו עבור שמות עצם. + כעת נוכיח את המשפט באינדוקציה על יצירת הנוסחה. +\end_layout + +\begin_layout Itemize +עבור +\begin_inset Formula $\varphi$ +\end_inset + + נוסחה אטומית +\begin_inset Formula $R(t_{1},...,t_{n})$ +\end_inset + + מתקיים +\begin_inset Formula +\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*} + +\end_inset + + אם ורק אם קיימים נציגים ל- +\begin_inset Formula $Val_{\mathcal{M}}(t,\bar{s})$ +\end_inset + + נסמנם +\begin_inset Formula $a_{1},...,a_{n}$ +\end_inset + + כך ש +\begin_inset Formula $\{\gamma\in\Gamma:(a_{1}(\gamma),...,a_{n}(\gamma))\in R^{\mathcal{M}_{\gamma}}\}\in F$ +\end_inset + +. + את מי נבחר כנציגים? לפי מה שהראנו עבור שמות עצם אפשר לבחור את +\begin_inset Formula $(Val_{\mathcal{M}_{\gamma}}(t_{i},s(\gamma)))_{\gamma\in\Gamma}$ +\end_inset + + בתור נציגים לכל +\begin_inset Formula $i$ +\end_inset + +. + ז"א +\begin_inset Formula +\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*} + +\end_inset + + )וזה בדיוק מה שמשפט +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +\lang english +Los +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +\lang hebrew + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +אומר(. +\end_layout + +\begin_layout Itemize +עבור +\begin_inset Formula $\varphi=\neg\psi$ +\end_inset + + מתקיים +\begin_inset Formula +\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*} + +\end_inset + + וזה מתקיים +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +אם ורק אם +\begin_inset Formula +\begin{eqnarray*} +Val_{\mathcal{M}}(\neg\psi,\bar{s}) & = & FALSE\iff Val_{\mathcal{M}}(\varphi,\bar{s})=FALSE +\end{eqnarray*} + +\end_inset + +. +\end_layout + +\begin_layout Itemize +המקרים של +\begin_inset Formula $\varphi=\psi_{1}\square\psi_{2}$ +\end_inset + + דומים מאוד )משתמשים בתכונות של על מסנן(. +\end_layout + +\begin_layout Itemize +נותר המקרה +\begin_inset Formula $\varphi=\exists x\psi(x)$ +\end_inset + + )המקרה של +\begin_inset Formula $\forall x$ +\end_inset + + נובע מהמקרה הנ"ל וממה שעבר עשינו ע"י השקילות הלוגית +\begin_inset Formula $\forall x\psi(x)=\neg\exists x\neg\psi(x)$ +\end_inset + +(. +\end_layout + +\begin_deeper +\begin_layout Itemize +כיוון אחד: נניח כי +\begin_inset Formula $(\mathcal{M},s)\models(\exists x)\psi(x)$ +\end_inset + + ז"א שקיים +\begin_inset Formula $\bar{a}\in\mathcal{M}$ +\end_inset + + כך ש +\begin_inset Formula $(\mathcal{M},s)\models\psi(\bar{a})$ +\end_inset + +. + נוסיף לשפה קבוע אישי חדש +\begin_inset Formula $c$ +\end_inset + + ונרשום +\begin_inset Formula $\psi(c)$ +\end_inset + + הנוסחה המתקבלת מ +\begin_inset Formula $\psi$ +\end_inset + +ע"י החלפת של מופע חופשי של +\begin_inset Formula $x$ +\end_inset + + בנוסחה +\begin_inset Formula $\psi$ +\end_inset + + ב +\begin_inset Formula $c$ +\end_inset + + . + נרחב את +\begin_inset Formula $\mathcal{M}$ +\end_inset + +למבנה לשפה המועשרת ע"י כך שנגדיר +\begin_inset Formula $c^{\mathcal{M}}=\bar{a}$ +\end_inset + +. + אזי +\begin_inset Formula $Val_{\mathcal{M}}(\psi,\bar{s}[{x\atop \bar{a}}])=Val_{\mathcal{M}}(\psi(c),s)$ +\end_inset + +. + אז לפי הנחת האינדוקציה: +\begin_inset Formula +\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*} + +\end_inset + + +\end_layout + +\begin_layout Itemize +כיוון שני: נניח כי +\begin_inset Formula $\{\gamma\in\Gamma:(M_{\gamma},s)\models(\exists x)\psi(x)\}\in F$ +\end_inset + +. + נגדיר איבר +\begin_inset Formula $a\in{\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}}$ +\end_inset + + באופן הבא: לכל +\begin_inset Formula $\gamma\in\Gamma$ +\end_inset + + אם +\begin_inset Formula $(\mathcal{M}_{\gamma},s)\models\exists x\psi(x)$ +\end_inset + + אז נבחר +\begin_inset Formula $a_{\gamma}$ +\end_inset + + שמעיד על כך. + אם +\begin_inset Formula $(\mathcal{M}_{\gamma},s)\not\models\exists x\psi(x)$ +\end_inset + + נבחר +\begin_inset Formula $a_{\gamma}\in\mathcal{M}_{\gamma}$ +\end_inset + + שרירותי. + נגדיר +\begin_inset Formula $\bar{a}=[a]$ +\end_inset + + . + מההנחה שלנו +\begin_inset Formula +\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_inset + +. + +\end_layout + +\end_deeper +\end_deeper +\begin_layout Corollary +נניח ש +\begin_inset Formula $\Gamma$ +\end_inset + + לא ריקה ו +\begin_inset Formula $\mathcal{M}_{\gamma}$ +\end_inset + +מבנים לשפה +\begin_inset Formula $\mathcal{L}$ +\end_inset + + לכל +\begin_inset Formula $\gamma\in\Gamma$ +\end_inset + + ו- +\begin_inset Formula $F$ +\end_inset + + על מסנן על +\begin_inset Formula $\Gamma$ +\end_inset + +, אזי לכל פסוק +\begin_inset Formula $\psi$ +\end_inset + + ב +\begin_inset Formula $\mathcal{L}$ +\end_inset + + מתקיים +\begin_inset Formula $({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma}})/F\models\psi$ +\end_inset + + אם ורק אם +\begin_inset Formula $\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\in F$ +\end_inset + +. +\end_layout + +\begin_deeper +\begin_layout Corollary + +\bar under +משפט הקומפקטיות +\bar default +: תהי +\begin_inset Formula $\Gamma$ +\end_inset + + קבוצה פסוקים בשפה +\begin_inset Formula $\mathcal{L}$ +\end_inset + +. + נניח שלכל +\begin_inset Formula $\psi_{1},\psi_{2}\in\Gamma$ +\end_inset + + גם +\begin_inset Formula $\psi_{1}\wedge\psi_{2}\in\Gamma$ +\end_inset + + ולכל +\begin_inset Formula $\psi\in\Gamma$ +\end_inset + + קיים מודל +\begin_inset Formula $\mathcal{M}_{\psi}\models\psi$ +\end_inset + + אזי +\begin_inset Formula $\Gamma$ +\end_inset + + ספיקה כלומר קיים +\begin_inset Formula $\mathcal{M}\models\Gamma$ +\end_inset + +. + +\end_layout + +\begin_layout Proof +לכל +\begin_inset Formula $\psi\in\Gamma$ +\end_inset + + נבחר מבנה +\begin_inset Formula $\mathcal{M}_{\psi}\models\psi$ +\end_inset + +. + תהי +\begin_inset Formula $\mathcal{U}\subseteq\mathbb{P}(\Gamma)$ +\end_inset + + הקבוצה המקיימת קיים +\begin_inset Formula $\psi\in\Gamma$ +\end_inset + +כך ש: +\begin_inset Formula $V\in\mathcal{U}\iff\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\subseteq V$ +\end_inset + +. + +\end_layout + +\end_deeper +\begin_layout Claim +\begin_inset Formula $\mathcal{U}$ +\end_inset + + מסנן על +\begin_inset Formula $\Gamma$ +\end_inset + + . +\end_layout + +\begin_layout Proof +לכל +\begin_inset Formula $\psi\in\Gamma$ +\end_inset + + מהנחתנו +\begin_inset Formula $\mathcal{M}_{\psi}\models\psi$ +\end_inset + + לכן +\begin_inset Formula $\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\not=\emptyset$ +\end_inset + +. + לכן +\begin_inset Formula $\mathcal{U}\not=\emptyset$ +\end_inset + +. + ברור ש +\begin_inset Formula $\mathcal{U}$ +\end_inset + + סגורה כלפי מעלה. + נניח ש +\begin_inset Formula $v_{1},v_{2}\in\mathcal{U}$ +\end_inset + + אזי קיימים +\begin_inset Formula $\psi_{1},\psi_{2}\in\Gamma$ +\end_inset + + כך ש- +\begin_inset Formula $\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi_{i}\}\subseteq V_{i}$ +\end_inset + + וזה גורר..... + +\begin_inset Formula $V_{1}\cap V_{2}\in\mathcal{U}$ +\end_inset + +. + +\end_layout + +\begin_layout Standard +יהי +\begin_inset Formula $F$ +\end_inset + + על מסנן שמרחיב את +\begin_inset Formula $\mathcal{U}$ +\end_inset + + . + לפי המסקנה מתקיים +\begin_inset Formula $({\displaystyle \prod_{\gamma\in\Gamma}\mathcal{M}_{\gamma})}/F\models\psi$ +\end_inset + + אם ורק אם +\begin_inset Formula $\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\in F$ +\end_inset + +. + אבל מהגדרת +\begin_inset Formula $\mathcal{U}$ +\end_inset + + לכל +\begin_inset Formula $\psi\in\Gamma$ +\end_inset + + הקבוצה +\begin_inset Formula $\{\gamma\in\Gamma:\mathcal{M}_{\gamma}\models\psi\}\in\mathcal{U}$ +\end_inset + + ולכן ל- +\begin_inset Formula $F$ +\end_inset + +. + מש"ל. +\end_layout + +\begin_layout Section +עקביות +\end_layout + +\begin_layout Theorem +תהי +\begin_inset Formula $(P,\le)$ +\end_inset + + קס"ח, אזי קיים יחס +\begin_inset Formula $R$ +\end_inset + + על +\begin_inset Formula $P$ +\end_inset + + )דו-מקומי( כך ש- +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $R$ +\end_inset + + יחס סדר קווי +\end_layout + +\begin_deeper +\begin_layout Enumerate +לכל +\begin_inset Formula $a,b\in P$ +\end_inset + + אם +\begin_inset Formula $a\le b$ +\end_inset + + אז +\begin_inset Formula $R(a,b)$ +\end_inset + +. +\end_layout + +\begin_layout Standard +במילים אחרות, קיים סדר קווי +\begin_inset Formula $R$ +\end_inset + + על +\begin_inset Formula $P$ +\end_inset + + שמרחיב את +\begin_inset Formula $\le$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Theorem + +\bar under +הערה: +\bar default + המשפט עבור קבוצה סופית +\begin_inset Formula $P$ +\end_inset + + איננו קשה. + ההוכחה באינדוקציה על +\begin_inset Formula $|P|$ +\end_inset + +. + עבור +\begin_inset Formula $|P|=1$ +\end_inset + + אין מה להוכיח. + נניח שהוכחנו עבור כל +\begin_inset Formula $P$ +\end_inset + + עם +\begin_inset Formula $|P|=n$ +\end_inset + + ונוכיח עבור +\begin_inset Formula $n+1$ +\end_inset + +: תהי +\begin_inset Formula $(P,\le)$ +\end_inset + + קס"ח עם +\begin_inset Formula $n+1$ +\end_inset + + איברים. + כיוון ש +\begin_inset Formula $P$ +\end_inset + + סופית יש לה איבר מינימלי +\begin_inset Formula $a$ +\end_inset + +. + תהי +\begin_inset Formula $Q=P\backslash\{a\}$ +\end_inset + +. + אז +\begin_inset Formula $(Q,\le)$ +\end_inset + + קס"ח עם +\begin_inset Formula $n$ +\end_inset + + איברים ולפי הנחת האינדוקציה יש +\begin_inset Formula $R$ +\end_inset + + סדר קווי על +\begin_inset Formula $Q$ +\end_inset + + שמרחיב את +\begin_inset Formula $\le$ +\end_inset + + על +\begin_inset Formula $Q$ +\end_inset + +. + עתה לא קשה לבדוק שאם נגדיר +\begin_inset Formula $R(a,b)$ +\end_inset + + לכל +\begin_inset Formula $b\in Q$ +\end_inset + + נקבל את המבוקש. +\end_layout + +\begin_layout Proof +)מקרה כללי( תהי +\begin_inset Formula $L$ +\end_inset + + שפה לתחשיב היחסים שבה: +\end_layout + +\begin_deeper +\begin_layout Enumerate +לכל +\begin_inset Formula $p\in P$ +\end_inset + + יש קבוע אישי +\begin_inset Formula $c_{p}$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +יחס דו מקומי +\begin_inset Formula $R$ +\end_inset + + +\end_layout + +\begin_layout Standard + +\bar under +בלבד. + +\bar default + נגדיר קבוצת פסוקים +\begin_inset Formula $T_{P}$ +\end_inset + + ב +\begin_inset Formula $L$ +\end_inset + + באופן הבא: +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $c_{p}\not=c_{q}$ +\end_inset + + לכל +\begin_inset Formula $p\not=q\in P$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $R$ +\end_inset + + יחס סדר קווי +\end_layout + +\begin_layout Enumerate +לכל +\begin_inset Formula $p,q\in P$ +\end_inset + + אם +\begin_inset Formula $p\le q$ +\end_inset + + אזי יהיה פסוק +\begin_inset Formula $R(c_{p},c_{q})$ +\end_inset + +. +\end_layout + +\begin_layout Claim +\begin_inset Formula $T_{P}$ +\end_inset + + ספיקה )מקומית(. +\end_layout + +\begin_deeper +\begin_layout Proof +ממשפט הקומפקטיות יספיק להוכיח ש +\begin_inset Formula $T_{P}$ +\end_inset + + ספיקה מקומית. + תהי +\begin_inset Formula $T_{0}\subseteq T_{P}$ +\end_inset + + סופית. + בה"כ האקסיומה ) +\numeric on +2 +\numeric off +( " +\begin_inset Formula $R$ +\end_inset + + יחס סדרי קווי" שייכת ל +\begin_inset Formula $T_{0}$ +\end_inset + +. + בנוסף נשים לב שב +\begin_inset Formula $T_{0}$ +\end_inset + + מופיעים רק מספר סופי של קבועים, נאמר: +\begin_inset Formula $c_{P_{1}},...,c_{p_{n}}$ +\end_inset + +. + נביט בקבוצה +\begin_inset Formula $P_{0}=\{p_{1},...,p_{n}\}\subseteq P$ +\end_inset + +. + אז +\begin_inset Formula $(P_{0},\le)$ +\end_inset + + קס"ח סופית. + לכן לפי ההערה יש יחס +\begin_inset Formula $R^{P_{0}}$ +\end_inset + + שהוא סדר קווי על +\begin_inset Formula $P_{0}$ +\end_inset + + המרחיב את +\begin_inset Formula $\le$ +\end_inset + + על +\begin_inset Formula $P_{0}$ +\end_inset + +. + ברור שאם נפרש את +\begin_inset Formula $R$ +\end_inset + + ב +\begin_inset Formula $P_{0}$ +\end_inset + + ע"י +\begin_inset Formula $R^{P_{0}}$ +\end_inset + + כנ"ל ו- +\begin_inset Formula $c_{p_{i}}$ +\end_inset + + ע"י +\begin_inset Formula $p_{i}$ +\end_inset + + אז נקבל מודל של +\begin_inset Formula $T_{0}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Standard +יהי +\begin_inset Formula $\mathcal{M}\models T_{P}$ +\end_inset + +, בפרט +\begin_inset Formula $R^{\mathcal{M}}$ +\end_inset + + סדר קווי על +\begin_inset Formula $\mathcal{M}$ +\end_inset + +. + יהי +\begin_inset Formula $\mathcal{N}\le\mathcal{M}$ +\end_inset + + המבנה שעולמו הוא הקבועים של +\begin_inset Formula $\mathcal{M}$ +\end_inset + + )כלומר +\begin_inset Formula $a\in\mathcal{N}\iff a=c_{p}^{\mathcal{M}}$ +\end_inset + + לאיזה +\begin_inset Formula $p\in P$ +\end_inset + +(. + נגדיר יחס סדר חלקי +\begin_inset Formula $\le^{\mathcal{N}}$ +\end_inset + +על +\begin_inset Formula $\mathcal{N}$ +\end_inset + + ע"י +\begin_inset Formula $p\le q\iff c_{p}^{\mathcal{N}}\le c_{q}^{\mathcal{N}}$ +\end_inset + + לכל +\begin_inset Formula $p,q\in P$ +\end_inset + + . + אז +\begin_inset Formula $(P,\le)\cong(N,\le^{\mathcal{N}})$ +\end_inset + + פשוט ע"י +\begin_inset Formula $p\mapsto c_{p}^{\mathcal{N}}$ +\end_inset + +. + לכן בה"כ +\begin_inset Formula $(P,\le)=(N,\le^{\mathcal{N}})$ +\end_inset + +. + עתה +\begin_inset Formula $R^{\mathcal{M}}|\mathcal{N}$ +\end_inset + + )צמצום( סדר קווי על +\begin_inset Formula $\mathcal{N}$ +\end_inset + +. + )לפי +\begin_inset Formula $\mathcal{M}\models(2)$ +\end_inset + + מתקיים כי +\begin_inset Formula $R^{\mathcal{M}}$ +\end_inset + + סדר קווי וצמצום של כזה הוא נשאר קווי(. + כיוון ש- +\begin_inset Formula $\mathcal{M}\models(3)$ +\end_inset + + אז אם +\begin_inset Formula $p\le q$ +\end_inset + + אזי +\begin_inset Formula $p(c_{p},c_{q})$ +\end_inset + + היא אקסיומה ב) +\numeric on +3 +\numeric off +( ולכן +\begin_inset Formula $\mathcal{M}\models R(c_{p},c_{q})$ +\end_inset + + ולכן +\begin_inset Formula $\mathcal{N}\models R(c_{p},c_{q})$ +\end_inset + +. + +\end_layout + +\end_deeper +\begin_layout Theorem +תהי +\begin_inset Formula $L=\{G\}$ +\end_inset + + עבור יחס דו מקומי +\begin_inset Formula $G$ +\end_inset + +. + +\begin_inset Formula $T_{G}$ +\end_inset + + התורה שאומרת כי העולם הוא גרף. + אזי אין פסוק +\begin_inset Formula $\psi$ +\end_inset + + ב +\begin_inset Formula $L$ +\end_inset + + כך ש +\begin_inset Formula $\mathcal{M}\models\psi$ +\end_inset + + אם ורק אם +\begin_inset Formula $\mathcal{M}$ +\end_inset + + גרף קשיר. +\end_layout + +\begin_layout Proof +נניח בשלילה שיש פסוק +\begin_inset Formula $\psi$ +\end_inset + + כזה. + נוסיף לשפה קבועים אישיים חדשים +\begin_inset Formula $c_{1},c_{2}$ +\end_inset + +. + יהי +\begin_inset Formula $\varphi_{n}$ +\end_inset + + הפסור שאומר שאין מסילה באורך קטן מ +\begin_inset Formula $n$ +\end_inset + + בין +\begin_inset Formula $c_{1}$ +\end_inset + + ל +\begin_inset Formula $c_{2}$ +\end_inset + +: +\begin_inset Formula +\[ +\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})] +\] + +\end_inset + + נשים לב ש +\begin_inset Formula $\Gamma=\{c_{1},c_{2}\}\cup\psi\cup\{\varphi_{n}\}_{n=1}^{\infty}$ +\end_inset + + עיקבית מקומית. + אם +\begin_inset Formula $\Gamma_{0}$ +\end_inset + + קבוצה סופית של פסוקים מן הקבוצה הנ"ל יש +\begin_inset Formula $n$ +\end_inset + + מירבי כך ש +\begin_inset Formula $\varphi_{n}\in\Gamma_{0}$ +\end_inset + +. + ברור שאם נמצא +\begin_inset Formula $\mathcal{M}\models\varphi_{n}\wedge\psi\wedge(c_{1}\not=c_{2})$ +\end_inset + + אז +\begin_inset Formula $\mathcal{M}\models\Gamma_{0}$ +\end_inset + +. + אבל ברור שלכל +\begin_inset Formula $n$ +\end_inset + + יש גרך המקיים את +\begin_inset Formula $\varphi_{n}\wedge\psi\wedge(c_{1}\not=c_{2})$ +\end_inset + + )פחות מ +\begin_inset Formula $n$ +\end_inset + + קודקודים, בפרט אין מסילה מ +\begin_inset Formula $c_{1}$ +\end_inset + +ל +\begin_inset Formula $c_{2}$ +\end_inset + +(. + ולכן +\begin_inset Formula $\Gamma$ +\end_inset + + ספיקה סופית. + לפי קומפקטיות +\begin_inset Formula $\Gamma$ +\end_inset + + עקבית. + אבל זה לא ייתכן: אם +\begin_inset Formula $\mathcal{M}\models\Gamma$ +\end_inset + + אז +\begin_inset Formula $\mathcal{M}\models\psi$ +\end_inset + + ולכן בין +\begin_inset Formula $c_{1}$ +\end_inset + + ל +\begin_inset Formula $c_{2}$ +\end_inset + + יש מסילה ובהכרח אורכה סופי, נאמר +\begin_inset Formula $n$ +\end_inset + +. + מצד שני +\begin_inset Formula $\mathcal{M}\models\varphi_{n}$ +\end_inset + + ולכן אין מסילה באורך +\begin_inset Formula $n$ +\end_inset + + בין +\begin_inset Formula $c_{1}$ +\end_inset + + ל +\begin_inset Formula $c_{2}$ +\end_inset + + וזוהי סתירה להנחת השלילה. +\end_layout + +\begin_layout Standard + +\bar under +הערה: +\end_layout + +\begin_layout Enumerate +באופן דומה אפשר להוכיח כי אין פסוק +\begin_inset Formula $\psi$ +\end_inset + + בשפה +\begin_inset Formula $L=\{\le\}$ +\end_inset + + כך ש +\begin_inset Formula $\mathcal{M}\models\psi$ +\end_inset + + אם ורק אם +\begin_inset Formula $\{\le\}$ +\end_inset + + סדר טוב )כלומר +\begin_inset Formula $\le$ +\end_inset + + סדר שווי בלי סדרה אינסופית יורדת(. + +\end_layout + +\begin_layout Enumerate +אותה הוכחה בדיוק תעבוד אם ננסה למצוא קבוצת פסוקים +\begin_inset Formula $\Gamma$ +\end_inset + + כך ש +\begin_inset Formula $\mathcal{M}\models\Gamma$ +\end_inset + + אם ורק אם +\begin_inset Formula $\mathcal{M}$ +\end_inset + + גרף קשיר/ +\begin_inset Formula $\mathcal{M}$ +\end_inset + + סדור היטב )סדר טוב(. +\end_layout + +\begin_layout Standard + +\bar under +תזכורת: +\end_layout + +\begin_layout Standard +אם +\begin_inset Formula $\Gamma$ +\end_inset + + קבוצת פסוקים אז +\begin_inset Formula $\Gamma\models\psi$ +\end_inset + + אם לכל מבנה +\begin_inset Formula $\mathcal{M}$ +\end_inset + +: אם +\begin_inset Formula $\mathcal{M}\models\Gamma$ +\end_inset + + אז +\begin_inset Formula $\mathcal{M}\models\psi$ +\end_inset + + . +\end_layout + +\begin_layout Corollary +אם +\begin_inset Formula $\Gamma\models\psi$ +\end_inset + + אז קיימת קבוצת פסוקים +\begin_inset Formula $\Gamma_{0}\subseteq\Gamma$ +\end_inset + + סופית כך ש +\begin_inset Formula $\Gamma_{0}\models\psi$ +\end_inset + +. + +\end_layout + +\begin_layout Proof +נביט בקבוצה +\begin_inset Formula $\Gamma\cup\{\neg\psi\}$ +\end_inset + + . + מהנחתנו קבוצה זו איננה ספיקה. + מקומפקטיות יש +\begin_inset Formula $\Gamma_{1}\subseteq\Gamma\cup\{\neg\psi\}$ +\end_inset + + סופית כך ש +\begin_inset Formula $\Gamma_{1}$ +\end_inset + + איננה ספיקה. + ברור ש +\begin_inset Formula $\neg\psi\in\Gamma_{1}$ +\end_inset + + כי אחרת +\begin_inset Formula $\Gamma_{1}\subseteq\Gamma$ +\end_inset + + ו +\begin_inset Formula $\Gamma$ +\end_inset + + עקבית. + )אם +\begin_inset Formula $\Gamma$ +\end_inset + + איננה עקבית מקומפקטיות יש +\begin_inset Formula $\Gamma_{0}\subseteq\Gamma$ +\end_inset + + שאינה ספיקה ו +\begin_inset Formula $\Gamma_{0}\models\varphi$ +\end_inset + + לכל פסוק +\begin_inset Formula $\varphi$ +\end_inset + +(. + לכן +\begin_inset Formula $\Gamma\supseteq\Gamma_{0}=\Gamma_{1}\backslash\{\neg\psi\}$ +\end_inset + + סופית ומקיימת +\begin_inset Formula $\Gamma_{0}\models\psi$ +\end_inset + + )כי אחרת יש מודל +\begin_inset Formula $\mathcal{M}\models\Gamma_{0}$ +\end_inset + + ו- +\begin_inset Formula $\mathcal{M}\not\models\psi$ +\end_inset + + כלומר +\begin_inset Formula $\mathcal{M}\models\neg\psi$ +\end_inset + + כלומר +\begin_inset Formula $\mathcal{M}\models\Gamma_{1}$ +\end_inset + + בסתירה לבחירת +\begin_inset Formula $\Gamma_{1}$ +\end_inset + +(. + במילים אחרות ליחס +\begin_inset Formula $\models$ +\end_inset + + יש טבע סופי. +\end_layout + +\begin_layout Standard + +\bar under +שאלה מרכזית +\bar default +: בהינתן שפה +\begin_inset Formula $L$ +\end_inset + + וקבוצת פסוקים +\begin_inset Formula $\Gamma$ +\end_inset + + ב +\begin_inset Formula $L$ +\end_inset + +, כיצד אפשר לדעת/לבדוק ביחס לפסוק +\begin_inset Formula $\psi$ +\end_inset + + כלשהו האם +\begin_inset Formula $\Gamma\models\psi$ +\end_inset + +? בתור התחלה נשים לב שאם +\begin_inset Formula $\psi\in\Gamma$ +\end_inset + + אז בוודאי +\begin_inset Formula $\Gamma\models\psi$ +\end_inset + +. + ולכן רצוי שנוכל לענות על השאלה האם +\begin_inset Formula $\psi\in\Gamma$ +\end_inset + +? נניח שהגדרנו מתי קבוצת פסוקים +\begin_inset Formula $\Gamma$ +\end_inset + + היא חשיבה, כלומר ניתן לענות על השאלה מתי פסוק +\begin_inset Formula $\psi$ +\end_inset + + שייך ל +\begin_inset Formula $\Gamma$ +\end_inset + +. + נניח ש +\begin_inset Formula $\Gamma$ +\end_inset + + קבוצת פסוקים חשיבה ונניח ש +\begin_inset Formula $\psi_{1},\psi_{2}\in\Gamma$ +\end_inset + + אז +\begin_inset Formula $\Gamma\models\psi_{1}\wedge\psi_{2}$ +\end_inset + +. + נניח ש +\begin_inset Formula $\psi_{1}\in\Gamma$ +\end_inset + + ו +\begin_inset Formula $\Gamma\models\psi_{1}\rightarrow\psi_{2}$ +\end_inset + + אז +\begin_inset Formula $\Gamma\models\psi_{2}$ +\end_inset + +. + באופן כללי יותר אם הראנו למשל +\begin_inset Formula $\psi_{1}$ +\end_inset + + ו- +\begin_inset Formula $\psi_{1}\rightarrow\psi_{2}$ +\end_inset + + נגררים לוגית ע"י +\begin_inset Formula $\Gamma$ +\end_inset + + אז ניתן להראות +\begin_inset Formula $\Gamma\models\psi_{2}$ +\end_inset + +. +\end_layout + +\begin_layout Section +מערכות היסק ויכיחות +\end_layout + +\begin_layout Standard + +\bar under +בעיה מרכזית: +\bar default + נתונה קבוצת פסוקים +\begin_inset Formula $\Gamma$ +\end_inset + + ורוצים לדעת עבור פסוק +\begin_inset Formula $\psi$ +\end_inset + + האם +\begin_inset Formula $\Gamma\models\psi$ +\end_inset + +. + +\end_layout + +\begin_layout Standard +מקרה פרטי: +\begin_inset Formula $\Gamma=\emptyset$ +\end_inset + +, כלומר רוצים לדעת האם פסוק +\begin_inset Formula $\psi$ +\end_inset + + אמיתי לוגית או לא. + המקרה הפרטי מנביע את המקרה הכללי. + מדוע? בהינתן קבוצת פסוקים +\begin_inset Formula $\Gamma$ +\end_inset + + ו +\begin_inset Formula $\psi$ +\end_inset + + כלשהו, אם +\begin_inset Formula $\Gamma\models\psi$ +\end_inset + + אז יש +\begin_inset Formula $\Gamma_{0}\subseteq\Gamma$ +\end_inset + + סופית כך ש +\begin_inset Formula $\Gamma_{0}\models\psi$ +\end_inset + + )משפט הקומפקטיות( ולכן +\begin_inset Formula $({\displaystyle \bigwedge_{\varphi\in\Gamma_{0}}\varphi})\rightarrow\psi$ +\end_inset + + אמיתי לוגית ואת זה אנחנו יודעים לבדוק. +\end_layout + +\begin_layout Standard + +\bar under +שאלה +\bar default +: מתי פסוק הוא אמיתי לוגית? +\end_layout + +\begin_layout Enumerate +אנחנו יודעים שכל טאוטולוגיה היא אמיתית לוגית. +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $\varphi$ +\end_inset + + אמיתי לוגית אז +\begin_inset Formula $\forall x\varphi$ +\end_inset + + אמיתי לוגית. + אפשר לרשום גם: +\begin_inset Formula $\varphi\rightarrow\forall x\varphi$ +\end_inset + + אמיתי לוגית. +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $\forall x\varphi(x)$ +\end_inset + + אמיתי לוגית אז +\begin_inset Formula $\varphi(t)$ +\end_inset + + אמיתי לוגית לכל שם עצם +\begin_inset Formula $t$ +\end_inset + +. + אפשר לרשום גם: +\begin_inset Formula $\forall x\varphi(x)\rightarrow\varphi(t)$ +\end_inset + + אמיתי לוגית. +\end_layout + +\begin_layout Enumerate + +\series bold +אם +\begin_inset Formula $\varphi\rightarrow\psi$ +\end_inset + + אמיתי לוגית ו +\begin_inset Formula $\varphi$ +\end_inset + + אמיתי לוגית אז +\begin_inset Formula $\psi$ +\end_inset + + אמיתי לוגית. + +\series default +)בכל מערכות ההיסק שנעבוד איתן זה יהיה כלל ההיסק היחיד. + זה נקרא +\bar under +כלל הניתוק +\bar default + או +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +\lang english +Modus Poneus +\lang hebrew +( +\end_layout + +\begin_layout Standard + +\bar under +סימון: +\bar default + בהינתן שפה +\begin_inset Formula $\mathcal{L}$ +\end_inset + + מסדר ראשון נסמן +\begin_inset Formula $Def(\mathcal{L})$ +\end_inset + + אוסף הנוסחאות בשפה +\begin_inset Formula $\mathcal{L}$ +\end_inset + +. +\end_layout + +\begin_layout Definition +מערכת היסק )לשפה +\begin_inset Formula $\mathcal{L}$ +\end_inset + +( זה זוג סדור +\begin_inset Formula $\left\langle \mathcal{A},\mathcal{I}\right\rangle $ +\end_inset + +כאשר: +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $\mathcal{A}\subseteq Def(\mathcal{L})$ +\end_inset + + )אולי ריקה( שנקראת קבוצת האקסיומות הלוגיות +\end_layout + +\begin_layout Enumerate +\begin_inset Formula ${\displaystyle \mathcal{I}\subseteq{\displaystyle \bigcup}_{i=1}^{\infty}F_{i}}$ +\end_inset + + כאשר +\begin_inset Formula $F_{n}$ +\end_inset + + זה אוסף הפונקציות +\begin_inset Formula $f:Def^{n}(\mathcal{L})\rightarrow Def(\mathcal{L})$ +\end_inset + + ו- +\begin_inset Formula $\mathcal{I}$ +\end_inset + + נקראת אוסף כללי ההיסק. +\end_layout + +\begin_layout Standard + +\bar under +הערה: +\bar default + תמיד נדרוש כי: +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $\varphi\in\mathcal{A}$ +\end_inset + + אז +\begin_inset Formula $\varphi$ +\end_inset + + אמיתי לוגית. + במקרה זה נאמר כי האקסיומות הלוגיות +\bar under +תקפות +\bar default +. +\end_layout + +\begin_layout Enumerate +אם +\begin_inset Formula $f\in\mathcal{I}$ +\end_inset + + ו- +\begin_inset Formula $\{\varphi_{1},...,\varphi_{n}\}\in dom(f)$ +\end_inset + + אז +\begin_inset Formula $\{\varphi_{1},...,\varphi_{n}\}\models f(\varphi_{1},...,\varphi_{n})$ +\end_inset + +. + במקרה זה נאמר כי כללי ההיסק +\bar under +נאותים +\bar default +. +\end_layout + +\begin_layout Standard + +\bar under +סימון +\bar default +: אם נרצה לומר ש +\begin_inset Formula $\psi$ +\end_inset + +מתקבל מ +\begin_inset Formula $\psi_{1},...,\psi_{n}$ +\end_inset + + על ידי אחד מכללי ההיסק נרשום +\begin_inset Formula $\frac{\psi_{1},...,\psi_{n}}{\psi}$ +\end_inset + + ולא צריך יהיה להסביר באיזה כלל היסק מדובר. + +\end_layout + +\begin_layout Definition +בהינתן מערכת היסק +\begin_inset Formula $\left\langle \mathcal{A},\mathcal{I}\right\rangle $ +\end_inset + + וקבוצת נוסחאות +\begin_inset Formula $\Gamma$ +\end_inset + + נאמר שנוסחה +\begin_inset Formula $\psi$ +\end_inset + + +\series bold +יכיחה +\series default + )כלומר, ניתנת להוכחה( מ +\begin_inset Formula $\Gamma$ +\end_inset + + ,ונסמן +\begin_inset Formula $\Gamma\vdash\psi$ +\end_inset + +, אם קיימת סדרת נוסחאות +\begin_inset Formula $\varphi_{1},...,\varphi_{k}$ +\end_inset + + לאיזה +\begin_inset Formula $k\in\mathbb{N}$ +\end_inset + + כך ש: +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $\psi=\varphi_{k}$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +לכל +\begin_inset Formula $1\le i\le k$ +\end_inset + + או: +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $\varphi_{i}$ +\end_inset + + אקסיומה לוגית. + או: +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $\varphi_{i}\in\Gamma$ +\end_inset + +. + או: +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $\varphi_{i}$ +\end_inset + + מתקבל מנוסחאות קודמות בסדרה ע"י אחד מכללי ההיסק. + במקרה שלנו יש +\begin_inset Formula $j_{1},j_{2}0$ +\end_inset + + מתקיים +\begin_inset Formula $m_{i}=m_{i-1}^{(T)}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Enumerate +ריצה של מ"ט +\begin_inset Formula $T$ +\end_inset + + נקראת +\series bold +סופית +\series default + )או מסתיימת( אם היא מהצורה +\begin_inset Formula $m_{0},m_{1},...,m_{n}$ +\end_inset + + לאיזה +\begin_inset Formula $n\in\mathbb{N}$ +\end_inset + + ו- +\begin_inset Formula $M_{n}^{(T)}$ +\end_inset + + אינו מוגדר. +\end_layout + +\end_deeper +\begin_layout Definition +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Definition +בהינתן מ"ט +\begin_inset Formula $T$ +\end_inset + + ומספר טבעי +\begin_inset Formula $n$ +\end_inset + + נגדיר פונקציה )חלקית( +\begin_inset Formula $f_{T}^{n}=\mathbb{N}^{n}\rightarrow\mathbb{N}$ +\end_inset + + באופן הבא: +\begin_inset Formula $n=0$ +\end_inset + +, +\begin_inset Formula $q=q_{0}$ +\end_inset + + , והסרט נראה כך: +\begin_inset Formula +\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*} + +\end_inset + +מתקיים +\begin_inset Formula $m=f_{T}^{n}(x_{1},...,x_{n})$ +\end_inset + + אם ריצה של +\begin_inset Formula $T$ +\end_inset + + עם המצב ההתחלתי הנ"ח מסתיימת )אחרת לא מוגדר( ו- +\begin_inset Formula $m$ +\end_inset + + היא מספר האחדות על הסרט בתום הריצה. +\end_layout + +\end_deeper +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Definition +פונקציה +\begin_inset Formula $f:\mathbb{N}^{n}\rightarrow\mathbb{N}$ +\end_inset + + נקראת +\series bold +חשיבה ע"י מ"ט +\series default +אם קיימת מ"ט +\begin_inset Formula $T$ +\end_inset + + כך ש +\begin_inset Formula $f_{T}^{n}=f$ +\end_inset + +, כלומר +\begin_inset Formula $f$ +\end_inset + + מוגדרת בדיוק באותו התחום בו +\begin_inset Formula $f_{T}^{n}$ +\end_inset + + מוגדרת ובכל מקום שהן מוגדרות +\begin_inset Formula $f_{T}^{n}(x_{1},...,x_{n})=f(x_{1},...,x_{n})$ +\end_inset + +. + +\end_layout + +\begin_layout Section +מכונות טיורינג - המשך +\end_layout + +\begin_layout Definition +תהי +\begin_inset Formula $f:\mathbb{N}^{k}\rightarrow\mathbb{N}$ +\end_inset + + פונקציה +\begin_inset Formula $f$ +\end_inset + + נקראת +\series bold +חשיבה +\series default + )ע"י מכונת טיורינג( אם קיימת מכונה +\begin_inset Formula $T$ +\end_inset + + כך שלכל +\begin_inset Formula $(n_{1},...,n_{k})\in\mathbb{N}^{k}$ +\end_inset + + הריצה של +\begin_inset Formula $T$ +\end_inset + + על סרט מהצורה +\begin_inset Formula +\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*} + +\end_inset + + מסתיימת אם ורק אם +\begin_inset Formula $f(n_{1},...,n_{k})$ +\end_inset + + מוגדר ובמקרה זה מספר האחדות על הסרט בתום הריצה הוא +\begin_inset Formula $f(n_{1},...,n_{k})$ +\end_inset + +. +\end_layout + +\begin_layout Definition + +\bar under +תזכורת +\bar default +: סימנו, בהינתן מ"ט +\begin_inset Formula $T$ +\end_inset + + את הפונקציה +\begin_inset Formula $f_{T}^{n}$ +\end_inset + + להיות הפונקציה שעבור קלט כנ"ל מחזירה את מספר האחדות בריצה סופית של המכונה + )על הקלט(. +\end_layout + +\begin_layout Claim +לכל מכונת טיורינג +\begin_inset Formula $T$ +\end_inset + + יש מכונת טיורינג +\begin_inset Formula $T^{*}$ +\end_inset + + כך ש: +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $f_{T}^{n}=f_{T^{*}}^{n}$ +\end_inset + + לכל +\begin_inset Formula $n$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +בא"ב של +\begin_inset Formula $T^{*}$ +\end_inset + + יש שני תווים מיוחדים +\begin_inset Formula $S,E$ +\end_inset + + כך שבכל ריצה מסתיימת של +\begin_inset Formula $T^{*}$ +\end_inset + + )על קלט תקני( הסרט לאחר הריצה נראה כך: +\begin_inset Formula $...BBS111...1EBB...$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +המכונה מעולם לא עברה במהלך הריצה את התא המסומן ב +\begin_inset Formula $S$ +\end_inset + + שמאלה +\end_layout + +\begin_layout Enumerate +פרט ל +\begin_inset Formula $S,E$ +\end_inset + + ל- +\begin_inset Formula $T^{*}$ +\end_inset + + יש רק את התווים +\begin_inset Formula $\{1,B\}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Proof +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Enumerate +לכל מצב פנימי +\begin_inset Formula $q\in Q(T)$ +\end_inset + + יהיה במכונה +\begin_inset Formula $T^{*}$ +\end_inset + + מצב פנימי +\begin_inset Formula $q^{*}$ +\end_inset + +. + כל פקודה +\begin_inset Formula $rqxq^{\prime}\in I(T)$ +\end_inset + + נחליף בפקודה +\begin_inset Formula $rq^{*}x(q^{\prime})^{*}$ +\end_inset + +. + נוסיף ל +\begin_inset Formula $T^{*}$ +\end_inset + + את הפקודות הבאות: +\end_layout + +\begin_deeper +\begin_layout Itemize +כותב +\begin_inset Formula $S$ +\end_inset + + משמאל לקלט וחוזר ימינה +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $Bq_{0}Lq_{1}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $1q_{0}Lq_{1}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Bq_{1}Sq_{2}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Bq_{2}Lq_{3}$ +\end_inset + + +\end_layout + +\end_deeper +\begin_layout Itemize +מטפל בהגעה לסוף הקלט, כותב +\begin_inset Formula $E$ +\end_inset + + וחוזר להתחלה +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $Bq_{3}Rq_{4}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Bq_{4}Lq_{5}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Bq_{5}Eq_{r}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $*q_{r}Lq_{r}$ +\end_inset + + ) +\begin_inset Formula $*$ +\end_inset + + זה או +\begin_inset Formula $B$ +\end_inset + + או +\begin_inset Formula $1$ +\end_inset + +( +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Sq_{r}Rq_{0}^{*}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +שלב הסריקה +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $1q_{3}Rq_{3}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $1q_{4}Rq_{3}$ +\end_inset + + +\end_layout + +\end_deeper +\end_deeper +\begin_layout Standard +נותר להבטיח שכל האחדות צמודות ושהמכונה יודעת מה לעשות במקרה שהיא נתקלת ב +\begin_inset Formula $S$ +\end_inset + + או ב +\begin_inset Formula $E$ +\end_inset + + בשלב הריצה. + נטפל קודם בחלק השני, לכל מצב פנימי +\begin_inset Formula $q^{*}$ +\end_inset + + נוסיף פקודות: +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Sq^{*}B\tilde{q_{1}}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $B\tilde{q_{1}}L\tilde{q_{2}}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $B\tilde{q_{2}}S\tilde{q_{3}}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $S\tilde{q_{3}}Rq^{*}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +באופן אנלוגי מטפלים ב +\begin_inset Formula $E$ +\end_inset + + +\end_layout + +\begin_layout Standard +נטפל כעט בלהבטיח שכל האחדות צמודות. + נניח שכל ריצה מסתיימת של +\begin_inset Formula $T$ +\end_inset + + מסתיימת במצב פנימי +\begin_inset Formula $\hat{q}$ +\end_inset + + )שאינו מופיע במהלך הריצה של +\begin_inset Formula $T$ +\end_inset + +(. + נוסיף פקודות: +\end_layout + +\begin_layout Itemize +\begin_inset Formula $*\hat{q}R\hat{q}$ +\end_inset + + )כאשר +\begin_inset Formula $*$ +\end_inset + + הינו כל תו שאינו +\begin_inset Formula $E$ +\end_inset + +( +\end_layout + +\begin_layout Itemize +\begin_inset Formula $E\hat{q}Bq_{w}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Bq_{w}Lq_{w}^{1}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $*q_{w}^{1}E\hat{q}$ +\end_inset + + )כאשר +\begin_inset Formula $*$ +\end_inset + + הינו כל תו שאינו +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit + +\begin_inset Formula $1$ +\end_inset + + ואינו +\begin_inset Formula $S$ +\end_inset + +( +\end_layout + +\begin_layout Itemize +נטפל במקרה שראינו +\begin_inset Formula $S$ +\end_inset + +אחרי שמחקנו את +\begin_inset Formula $E$ +\end_inset + +: +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $Sq_{w}^{1}Eq_{w}^{s}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Eq_{w}^{s}Lq_{w}^{s_{1}}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Bq_{w}^{s_{1}}Sq_{w}^{s_{2}}$ +\end_inset + + - מצב סופי +\end_layout + +\end_deeper +\begin_layout Itemize +וגם: +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $1q_{w}^{1}Eq_{w}^{d}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $1q_{w}^{d}Lq_{w}^{d}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $*q_{w}^{d}1\hat{q}$ +\end_inset + + )כאשר +\begin_inset Formula $*$ +\end_inset + +- כל תו שאינו +\begin_inset Formula $S$ +\end_inset + + או +\begin_inset Formula $1$ +\end_inset + +( +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Sq_{w}^{d}1q_{w}^{s}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $1q_{w}^{s}Lq_{w}^{s_{1}}$ +\end_inset + + +\end_layout + +\end_deeper +\end_deeper +\begin_layout Enumerate +הטיפול דומה לזה של הסעיף הקודם, פרט לטיפול במה קורה כאשר פוגשים +\begin_inset Formula $S$ +\end_inset + +. + כל פעם שהמכונה פוגשת +\begin_inset Formula $S$ +\end_inset + + היא תיכנס ל"תת מכונה" שמזיזה את כל הסרט שעד +\begin_inset Formula $E$ +\end_inset + + ימינה בתו אחד, כותבת +\begin_inset Formula $B$ +\end_inset + + במקום הראשון שמימין ל- +\begin_inset Formula $S$ +\end_inset + + וחוזרת לריצה של +\begin_inset Formula $T$ +\end_inset + +. + הדבר היחיד שצריך להשתכנע: יש מכונה +\begin_inset Formula $Sh$ +\end_inset + + שבהינתן קלט מן הצורה +\begin_inset Formula $...BBS...EBBB...$ +\end_inset + + מעתיקה את כל הקלט בהזזה של תא אחד ימינה. + נוסיף לא"ב שלנו תו מיוחד +\begin_inset Formula $B^{*}$ +\end_inset + + , המכונה תרוץ באופן הבא: +\end_layout + +\begin_deeper +\begin_layout Enumerate +תסרוק עד שתגיע ל +\begin_inset Formula $E$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +לכל תו +\begin_inset Formula $\alpha$ +\end_inset + + בא"ב המקורי )כלומר שאינו +\begin_inset Formula $B^{*}$ +\end_inset + +( יהיה מצב פנימי +\begin_inset Formula $q_{\alpha}$ +\end_inset + +. + סדרת הפקודות: +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $\alpha q_{w}B^{*}q_{\alpha}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $Bq_{\alpha}Lq_{\alpha}^{1}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $B^{*}q_{\alpha}^{1}\alpha q_{w}$ +\end_inset + + +\end_layout + +\begin_layout Standard +מעתיקה את התו +\begin_inset Formula $\alpha$ +\end_inset + + תו אחד מימין למקומו המקורי. + צריך טיפול נפרד בתווים +\begin_inset Formula $S,E$ +\end_inset + + אבל אין בעיה. +\end_layout + +\end_deeper +\end_deeper +\begin_layout Enumerate +אם בא"ב שלנו יש +\begin_inset Formula $n$ +\end_inset + + תווים נבנה מכונה +\begin_inset Formula $T^{*}$ +\end_inset + + שבה התו ה- +\begin_inset Formula $i$ +\end_inset + + בא"ב של +\begin_inset Formula $T$ +\end_inset + + ייוצג ע"י +\begin_inset Formula $n$ +\end_inset + +-יה של תאים +\begin_inset Formula $\underset{i}{\underbrace{11...1}}\underset{n-i}{\underbrace{BB...B}}$ +\end_inset + + . + קל לבדוק שכל פקודה מהצורה "זוז ימינה" או "זוז שמאלה" ב +\begin_inset Formula $T$ +\end_inset + + ניתן לתרגם בקלות לפקודה "זוז +\begin_inset Formula $n$ +\end_inset + + תווים ימינה/שמאלה" ב +\begin_inset Formula $T^{*}$ +\end_inset + +. + פקודה מהצורה "כתוב את התו ה +\begin_inset Formula $i$ +\end_inset + + בא"ב בתא הנוכחי" תתרגם לסדרה של +\begin_inset Formula $n$ +\end_inset + + פקודות כתיבה "כתוב במקום ה +\begin_inset Formula $n$ +\end_inset + +-יה שאתה נמצא בתחילתה את ה +\begin_inset Formula $n$ +\end_inset + +-יה +\begin_inset Formula $\underset{i}{\underbrace{11...1}}\underset{n-i}{\underbrace{BB...B}}$ +\end_inset + +. + כנ"ל לגבי הקריאה. + לא קשה לבדוק: אם נייצג את התו +\begin_inset Formula $1$ +\end_inset + + בא"ב של +\begin_inset Formula $T$ +\end_inset + + ע"י +\begin_inset Formula $\underset{n-1}{1\underbrace{BB...B}}$ +\end_inset + +אז +\begin_inset Formula $f_{T^{*}}^{n}=f_{T}^{n}$ +\end_inset + + לכל +\begin_inset Formula $n$ +\end_inset + +. + +\end_layout + +\end_deeper +\begin_layout Standard +מעכשיו נניח שכל מכונת טיורינג שנעבוד איתה מקיימת את +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +התנאים +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +2,3,4 +\family roman +\series medium +\shape up +\size normal +\emph off +\numeric off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +. + לפי +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +1 +\family roman +\series medium +\shape up +\size normal +\emph off +\numeric off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +אם מה שמעניין אותנו זה מחלקת הפונקציות הניתנות לחישוב ע"י מכונת טיורינג + הרי שהנחה זו אינה משנה את המחלקה. + בנוסף נניח שלכל מכונת טיורינג יש מצב מסיים יחיד שאינו מופיע במהלך הריצה. + עוד אפשר להניח שבסיום הריצה הראש הקורא נמצא תו אחד מימין ל- +\begin_inset Formula $S$ +\end_inset + +. +\end_layout + +\begin_layout Claim +נניח ש- +\begin_inset Formula $f:\mathbb{N}\rightarrow\mathbb{N}$ +\end_inset + + ו- +\begin_inset Formula $g:\mathbb{N}\rightarrow\mathbb{N}$ +\end_inset + + חשיבות טיורינג אז גם +\begin_inset Formula $f\circ g$ +\end_inset + + חשיבה טיורינג. +\end_layout + +\begin_layout Proof +תהינה +\begin_inset Formula $T_{f},T_{g}$ +\end_inset + + מכונות כך ש +\begin_inset Formula $f_{T_{f}}^{\prime}=f$ +\end_inset + + וגם +\begin_inset Formula $g_{T_{g}}^{\prime}=g$ +\end_inset + + . + לכל מצב פנימי של +\begin_inset Formula $f$ +\end_inset + + במכונה החדשה יהיה מצב פנימי +\begin_inset Formula $q^{*}$ +\end_inset + +. + אז המכונה של ההרכבה תהיה: +\end_layout + +\begin_deeper +\begin_layout Enumerate +רשימת הפקודות של +\begin_inset Formula $T_{g}$ +\end_inset + +. + +\end_layout + +\begin_layout Enumerate +מוחקים את +\begin_inset Formula $S$ +\end_inset + +, וכותבים במקומו +\begin_inset Formula $1$ +\end_inset + +, מוחקים את +\begin_inset Formula $E$ +\end_inset + +, חוזר להתחלה ועובר למצב פנימי +\begin_inset Formula $q_{0}^{*}$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +רשימת הפקודות של +\begin_inset Formula $T_{f}$ +\end_inset + + עם השינוי שכל פקודה מהצורה +\begin_inset Formula $*q\star q_{1}$ +\end_inset + + משתנה לפקודה מהצורה +\begin_inset Formula $*q^{*}\star q_{1}^{*}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Claim +משפחת הפונקציות החשיבות טיורינג סגורה תחת אופרטור "מיזער": +\begin_inset Formula +\begin{eqnarray*} +\mu_{x_{1}}(g(x_{1},...,x_{n})) & = & \begin{cases} +a & (*)\\ +undefined & else +\end{cases} +\end{eqnarray*} + +\end_inset + + כאשר * הינו תנאי שנגדיר בשיעור הבא.... +\end_layout + +\begin_layout Section +פונקציות חשיבות +\end_layout + +\begin_layout Standard +ראינו שהפונקציות הבאות חשיבות טיורינג: +\end_layout + +\begin_layout Itemize +\begin_inset Formula $1$ +\end_inset + + - הפונקציה הקבועה +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +1 +\end_layout + +\begin_layout Itemize +\begin_inset Formula $0$ +\end_inset + + - הפונקציה הקבועה +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +0 +\end_layout + +\begin_layout Itemize +\begin_inset Formula $x+y$ +\end_inset + + - חיבור +\end_layout + +\begin_layout Itemize +קל לוודא ש +\begin_inset Formula $\Pi_{k}^{n}(x_{1},...,x_{n})=x_{k}$ +\end_inset + + עבור +\begin_inset Formula $k0)\\ +undefined & else +\end{cases} +\end{eqnarray*} + +\end_inset + + אזי אם +\begin_inset Formula $g$ +\end_inset + + חשיבה טיורינג גם +\begin_inset Formula $h$ +\end_inset + + חשיבה טיורינג. + +\begin_inset Formula $\mu$ +\end_inset + + נקרא אופרטור ה"מיזער". +\end_layout + +\begin_layout Proof +)רעיון( תהי +\begin_inset Formula $T$ +\end_inset + + מכונת טיורינג המחשבת את +\begin_inset Formula $g$ +\end_inset + + )כלומר +\begin_inset Formula $f_{T}^{k}=g$ +\end_inset + +(. + "מטה רעיון" - נריץ את +\begin_inset Formula $T$ +\end_inset + + על הקלט +\begin_inset Formula $0,x_{2},...,x_{k}$ +\end_inset + +. + אם המכונה לא עוצרת זה אומר ש +\begin_inset Formula $g$ +\end_inset + + לא מוגדרת ב +\begin_inset Formula $(0,x_{2},...,x_{k})$ +\end_inset + + ולכן גם +\begin_inset Formula $h(x_{2},...,x_{k})$ +\end_inset + + לא מוגדרת כנדרש. + אם הריצה מסתיימת נבדוק האם היא הסתיימה ב +\begin_inset Formula $0$ +\end_inset + +. + אם כן, נחזיר +\begin_inset Formula $0$ +\end_inset + + ואז +\begin_inset Formula $h(0,x_{2},...,x_{k})=0$ +\end_inset + + כנדרש. + אם לא, נחזור על אותה פעולה עם הקלט +\begin_inset Formula $1,x_{2},...,x_{k}$ +\end_inset + + וכו'. + אם המכונה הנ"ל תעצור אי פעם, זה יהיה הטבעי הקטן ביותר +\begin_inset Formula $t$ +\end_inset + + עבורו +\begin_inset Formula $g(t,x_{2},...,x_{k})=0$ +\end_inset + +, בפרט +\begin_inset Formula $g(t^{\prime},x_{2},...,x_{k})$ +\end_inset + + מוגדרת לכל +\begin_inset Formula $t^{\prime}0$ +\end_inset + + לכל +\begin_inset Formula $t^{\prime}0$ +\end_inset + + לכל +\begin_inset Formula $t$ +\end_inset + +. + ואילו במקומות בהם +\begin_inset Formula $h$ +\end_inset + + לא מוגדרת כך שקיבלנו שיוויון. +\end_layout + +\begin_layout Standard +ביתר פירוט: נבנה מכונה הפועלת באופן הבא. + המכונה מסמנת את סוף הקלט ב +\begin_inset Formula $S$ +\end_inset + +. + בשלב הראשון המכונה +\begin_inset Formula $T^{*}$ +\end_inset + + תעתיק את הקלט +\begin_inset Formula $x_{2},...,x_{k}$ +\end_inset + + מימין ל +\begin_inset Formula $S$ +\end_inset + + ותוסיף +\begin_inset Formula $1B$ +\end_inset + + בהתחלה. + בשלב הבא +\begin_inset Formula $T^{*}$ +\end_inset + + תחקה את הריצה של +\begin_inset Formula $T$ +\end_inset + + על +\begin_inset Formula $0,x_{2},...,x_{k}$ +\end_inset + + כאשר היא מקפידה )וזה הרי +\begin_inset Formula $T$ +\end_inset + + עושה ממילא( לא לזוז משמאל ל +\begin_inset Formula $S$ +\end_inset + +. + אם השלב הזה בריצה הסתיים במקום כלשהו על הסרט מימין ל +\begin_inset Formula $S$ +\end_inset + + יהיה כתוב +\begin_inset Formula $E$ +\end_inset + + )כי כך +\begin_inset Formula $T$ +\end_inset + + עובדת(. + אם בין +\begin_inset Formula $S$ +\end_inset + + ל +\begin_inset Formula $E$ +\end_inset + + לא מופיע התו +\begin_inset Formula $1$ +\end_inset + +, אז +\begin_inset Formula $T^{*}$ +\end_inset + + תחזור עד להתחלת הקלט של +\begin_inset Formula $T^{*}$ +\end_inset + + )משמאל ל +\begin_inset Formula $S$ +\end_inset + +( תמחק את כל הקלט ותעצור. + אם בין +\begin_inset Formula $S$ +\end_inset + + ל +\begin_inset Formula $E$ +\end_inset + + מופיע התו +\begin_inset Formula $1$ +\end_inset + + המכונה תחזור לתחילת הקלט של +\begin_inset Formula $T^{*}$ +\end_inset + +, תכתוב +\begin_inset Formula $1$ +\end_inset + + לפני ה +\begin_inset Formula $B$ +\end_inset + + הראשון ותתחיל מההתחלה. + +\end_layout + +\end_deeper +\begin_layout Definition +פונקציה +\begin_inset Formula $f:\mathbb{N}^{k}\rightarrow\mathbb{N}^{m}$ +\end_inset + + תיקרא חשיבה/רקורסיבית אם היא מתקבלת מן הפונקציות +\begin_inset Formula $\{x+y,x\cdot y,C_{<}(x,y),\Pi_{k}^{n}(x_{1},...,x_{n}),1,0\}$ +\end_inset + + על ידי מספר סופי של הרכבות והפעלה של האופרטור +\begin_inset Formula $\mu_{x}$ +\end_inset + +. + במילים אחרות, משפחת הפונקציות החשיבות זו המשפחה/אוסף הקטנ/ה ביותר של פונקציות + מ +\begin_inset Formula $\mathbb{N}^{k}$ +\end_inset + + ל +\begin_inset Formula $\mathbb{N}^{m}$ +\end_inset + + שמכיל/ה את הפונקציות הנ"ל וסגור/ה תחת הרכבה והאופרטור +\begin_inset Formula $\mu_{x}$ +\end_inset + +. + +\end_layout + +\begin_layout Theorem +פונקציה +\begin_inset Formula $f:\mathbb{N}^{k}\rightarrow\mathbb{N}^{m}$ +\end_inset + + חשיבה אם ורק אם היא חשיבה טיורינג. +\end_layout + +\begin_layout Theorem +הוכחנו שכל פונקציה חשיבה היא חשיבה טיורינג. + +\bar under +תרגיל: +\bar default + הפונקציה +\begin_inset Formula $n\mapsto n!$ +\end_inset + + היא חשיבה טיורינג. + הוכח שהפונקציה חשיבה. + שאלה כמעט זהה: מדוע הפונקציה +\begin_inset Formula $f(m)=\begin{cases} +n & m=2^{n}\\ +0 & m=1\, or\, else +\end{cases}$ +\end_inset + + חשיבה? +\end_layout + +\begin_layout Definition +תהי +\begin_inset Formula $A\subseteq\mathbb{N}^{m}$ +\end_inset + + אזי +\begin_inset Formula $\chi_{A}=\mathbb{N}^{m}\rightarrow\mathbb{N}$ +\end_inset + + זו הפונקציה המוגדרת על ידי +\begin_inset Formula +\begin{eqnarray*} +\chi_{A}(x) & = & \begin{cases} +1 & x\in A\\ +0 & else +\end{cases} +\end{eqnarray*} + +\end_inset + +. + +\begin_inset Formula $\chi_{A}$ +\end_inset + + נקראת +\series bold +הפונקציה המציינת +\series default + של +\begin_inset Formula $A$ +\end_inset + +. +\end_layout + +\begin_deeper +\begin_layout Definition +יחס +\begin_inset Formula $A\subseteq\mathbb{N}^{m}$ +\end_inset + + נקרא +\series bold +חשיב +\series default + אם +\begin_inset Formula $\chi_{A}$ +\end_inset + + פונקציה חשיבה. +\end_layout + +\begin_layout Claim +משפחת היחסים החשיבים סגורה תחת פעולות בוליאניות, כלומר תחת איחודים, חיתוכים + והשלמה. +\end_layout + +\end_deeper +\begin_layout Proof +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Itemize +אם +\begin_inset Formula $A$ +\end_inset + + חשיבה אז +\begin_inset Formula $\chi_{A}(x)=C_{<}(\chi_{A}(x),1)$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +אם +\begin_inset Formula $A,B$ +\end_inset + + חשיבות אז +\begin_inset Formula $\chi_{A\cap B}(x)=\chi_{A}(x)\cdot\chi_{B}(x)$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $\chi_{A\cup B}(x)=C_{<}(0,\chi_{A}(x)+\chi_{B}(x))$ +\end_inset + + או לפי דה-מורגן. +\end_layout + +\begin_layout Standard +יוצא, למשל, כי היחס +\begin_inset Formula $A(x,y)=(x\le y)$ +\end_inset + + חשיב. + זה פשוט איחוד היחסים החשיבים +\begin_inset Formula $C_{<}(x,y)$ +\end_inset + + ו- +\begin_inset Formula $x=y$ +\end_inset + +. + +\end_layout + +\end_deeper +\begin_layout Claim +)הגדרה לפי מקרים(: תהיינה +\begin_inset Formula $f_{1},...,f_{n}$ +\end_inset + + פונקציות חשיבות +\begin_inset Formula $k$ +\end_inset + +-מקומיות, ו- +\begin_inset Formula $A_{1},...,A_{n}\subseteq\mathbb{N}^{k}$ +\end_inset + + זרות וחשיבות, כך ש +\begin_inset Formula $\bigcup_{i=1}^{n}A_{i}=\mathbb{N}^{k}$ +\end_inset + +. + אזי הפונקציה +\begin_inset Formula +\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_inset + + חשיבה. + +\end_layout + +\begin_layout Proof +\begin_inset Formula $\sum_{i=1}^{n}f_{i}(x)\cdot\chi_{A_{i}}(x)$ +\end_inset + + וזו פונקציה חשיבה כי +\begin_inset Formula $\chi_{A_{i}}$ +\end_inset + + חשיבות, +\begin_inset Formula $f_{i}$ +\end_inset + + חשיבות והחיבור והכפל חשיבים. +\end_layout + +\begin_layout Section +פונקציות חשיבות - המשך +\end_layout + +\begin_layout Definition +יהי +\begin_inset Formula $A\subseteq\mathbb{N}^{k+1}$ +\end_inset + + יחס חשיב, +\begin_inset Formula $k+1$ +\end_inset + + מקומי. + נגדיר אופרטור: +\begin_inset Formula +\begin{eqnarray*} +\mu_{x + + + + + + + + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +0 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +1 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +2 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +3 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +4 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +5 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +6 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +0 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +0 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +1 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +3 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +6 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +10 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +15 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\swarrow$ +\end_inset + + +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +1 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +2 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +4 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +7 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +11 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +16 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\swarrow$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\vdots$ +\end_inset + + +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +2 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +5 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +8 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +12 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +17 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\swarrow$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\vdots$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +3 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +9 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +13 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +18 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\swarrow$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\vdots$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +4 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +14 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +19 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\swarrow$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\vdots$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +5 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\numeric on +20 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\swarrow$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\vdots$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\series bold +\numeric on +6 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\swarrow$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $\vdots$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + + + +\end_inset + + +\end_layout + +\begin_layout Proof +לא קשה לבדוק שהפונקציה הזאת היא פשוט +\begin_inset Formula $\frac{1}{2}(x+y)\cdot(x+y+1)+x$ +\end_inset + +. + לפי התיאור הזה ברור ש: +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $Pr(x,y)$ +\end_inset + + חשיבה +\end_layout + +\begin_layout Enumerate +מקיימת +\begin_inset Formula $Pr(x,y)\ge x$ +\end_inset + + וגם +\begin_inset Formula $Pr(x,y)\ge y$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +לפי התיאור הגרפי היא חח"ע ועל )הוכחה יותר אלגברית - מכירים ממבוא ללוגיקה(. +\end_layout + +\end_deeper +\end_deeper +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Claim +)טענת עזר +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +2 +\family roman +\series medium +\shape up +\size normal +\emph off +\numeric off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +- משפט השאריות הסיני( יהי +\begin_inset Formula $n\in\mathbb{N}$ +\end_inset + +, +\begin_inset Formula $m_{1},...,m_{n}$ +\end_inset + + מספרים טבעיים זרים בזוגות. + יהיו +\begin_inset Formula $k_{1},...,k_{n}$ +\end_inset + + מספרים טבעיים כלשהם )בד"כ מניחים +\begin_inset Formula $k_{i}b_{2}$ +\end_inset + +( לכל +\begin_inset Formula $1\le i\le n$ +\end_inset + +. + לכן +\begin_inset Formula $b_{1}-b_{2}$ +\end_inset + + מחלק את המכפלה המשותפת הקטנה ביותר של ה +\begin_inset Formula $m_{i}$ +\end_inset + +. + כיוון שה +\begin_inset Formula $m_{i}$ +\end_inset + + זרים בזוגות המכפלה המשותפת הקטנה ביותר היא +\begin_inset Formula $d$ +\end_inset + +. + אבל +\begin_inset Formula $b_{1}-b_{2}j$ +\end_inset + +. + לכן: +\begin_inset Formula $p|(i-j)\cdot(n!)$ +\end_inset + + . + כיוון ש +\begin_inset Formula $p$ +\end_inset + + ראשוני הוא מחלק או את +\begin_inset Formula $i-j$ +\end_inset + + או את +\begin_inset Formula $n!$ +\end_inset + +. + כיוון ש +\begin_inset Formula $i-jn$ +\end_inset + + כלשהו ונבחר +\begin_inset Formula $y=k!$ +\end_inset + +. + לפי טענת עזר +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +3 +\family roman +\series medium +\shape up +\size normal +\emph off +\numeric off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +קיים +\begin_inset Formula $z$ +\end_inset + + כך ש +\begin_inset Formula $\gamma(z,y,i)=a_{i}$ +\end_inset + + לכל +\begin_inset Formula $i\le n$ +\end_inset + +. + +\end_layout + +\begin_layout Enumerate +)טכני( +\begin_inset Formula $\gamma(z,y,i)\le z$ +\end_inset + + לכל +\begin_inset Formula $z,y,i$ +\end_inset + +. + +\end_layout + +\end_deeper +\begin_layout Standard +הפונקציה +\begin_inset Formula $\beta(b,i)$ +\end_inset + + המבוקשת תהיה +\begin_inset Formula $\gamma(Pr^{L}(b),Pr^{R}(b),i)$ +\end_inset + + כאשר +\begin_inset Formula $Pr^{L}(b)=\Pi_{1}(Pr^{-1}(b))$ +\end_inset + + ו- +\begin_inset Formula $Pr^{R}(b)=\Pi_{2}(Pr^{-1}(b))$ +\end_inset + +. + הדבר היחיד שנותר לוודא +\begin_inset Formula $Pr^{L},Pr^{R}$ +\end_inset + + הן פונקציות חשיבות. + +\end_layout + +\begin_layout Section +הצפנות +\end_layout + +\begin_layout Standard + +\bar under +חזרה: +\bar default + אם +\begin_inset Formula $A(x,y)$ +\end_inset + + יחס חשיב אז +\begin_inset Formula $(\exists x3$ +\end_inset + + ל +\begin_inset Formula $i>1$ +\end_inset + + אז +\begin_inset Formula $p$ +\end_inset + + פקודה מהצורה +\begin_inset Formula $\beta(x,i-1)\beta(x,i)**$ +\end_inset + +. + במילים אחרות אם +\begin_inset Formula $p$ +\end_inset + + היא הרביעייה +\begin_inset Formula $\left\langle \alpha,q,\alpha^{\prime},q^{\prime}\right\rangle $ +\end_inset + + אז +\begin_inset Formula $x$ +\end_inset + + רלוונטי ל +\begin_inset Formula $p$ +\end_inset + + אם +\begin_inset Formula $\beta(x,i-1)=\alpha,\beta(x,i)=q$ +\end_inset + +. + נסמן זאת +\begin_inset Formula $\varphi_{p}(x)$ +\end_inset + +. + לומר ש +\begin_inset Formula $y$ +\end_inset + + עוקב של +\begin_inset Formula $x$ +\end_inset + + לפי +\begin_inset Formula $p$ +\end_inset + + זה לומר +\begin_inset Formula $\varphi(x),\varphi(y)$ +\end_inset + +. + +\begin_inset Formula $\varphi_{p}(x)$ +\end_inset + + עכשיו מתחלק לפי מהות הפקודה +\begin_inset Formula $p$ +\end_inset + +. + נטפל למשל במקרה ש +\begin_inset Formula $p=\left\langle \alpha,q,\alpha^{\prime},q^{\prime}\right\rangle $ +\end_inset + + כאשר +\begin_inset Formula $\alpha^{\prime}\in\{0,1\}$ +\end_inset + +. + מתי +\begin_inset Formula $y$ +\end_inset + + יתקבל מ +\begin_inset Formula $x$ +\end_inset + + ע"י הפקודה +\begin_inset Formula $p$ +\end_inset + +? אם +\begin_inset Formula $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 $ +\end_inset + +. + פשוט צריך לדרוש: +\end_layout + +\begin_deeper +\begin_layout Enumerate +נסמן +\begin_inset Formula $i_{0}$ +\end_inset + + להיות ה +\begin_inset Formula $i$ +\end_inset + + היחיד כך ש +\begin_inset Formula $i\le\beta(x,0)$ +\end_inset + + ו- +\begin_inset Formula $\beta(x,i_{0})\in\{4,...,k\}$ +\end_inset + +. + +\end_layout + +\begin_layout Enumerate +נדרוש ש +\begin_inset Formula $\beta(y,i_{0})=q^{\prime},\beta(y,i_{0}-1)=\alpha^{\prime}$ +\end_inset + + ובכל מקרה אחר +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\begin_inset Formula $\beta(y,j)=\beta(x,j)$ +\end_inset + +. +\end_layout + +\begin_layout Standard +הטיפול בפקודות של תזוזה הוא דומה. + זה מקרה ש +\begin_inset Formula $\varphi_{p}(x,y)$ +\end_inset + + חשיבה. + לומר ש +\begin_inset Formula $y$ +\end_inset + + עוקב של +\begin_inset Formula $x$ +\end_inset + + זה פשוט +\begin_inset Formula ${\displaystyle \varphi(x)\wedge\varphi(y)\wedge\bigvee_{p\in I}\varphi_{p}(x,y)}$ +\end_inset + + . + +\end_layout + +\end_deeper +\begin_layout Claim +) +\numeric on +4 +\numeric off +( היחס +\begin_inset Formula $\rho(x)$ +\end_inset + + האומר " +\begin_inset Formula $x$ +\end_inset + + מקודד ריצה מסתיימת של +\begin_inset Formula $T$ +\end_inset + +" הוא חשיב. +\end_layout + +\begin_layout Proof +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $\theta(x)$ +\end_inset + + - +\begin_inset Formula $x$ +\end_inset + + מצפין סדרה. +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $\varphi_{S}(\beta(x,1))$ +\end_inset + + כלומר האיבר הראשון בסדרה ש +\begin_inset Formula $x$ +\end_inset + + מצפין הוא מצב התחלתי של +\begin_inset Formula $T$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $\varphi_{E}(\beta(x,\beta(x,0)))$ +\end_inset + + - האיבר האחרון בסדרה הוא מצב סופי של +\begin_inset Formula $T$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +לכל +\begin_inset Formula $1\le i<\beta(x,0)$ +\end_inset + + מתקיים +\begin_inset Formula $\varphi(\beta(x,i),\beta(x,i+1))$ +\end_inset + + כלומר כל איבר בסדרה הוא מצב עוקב של המצב המוצפן ע"י האיבר הקודם לו. +\end_layout + +\end_deeper +\begin_layout Claim +) +\numeric on +5 +\numeric off +( +\begin_inset Formula $f_{E}(x)=n$ +\end_inset + + זו הפונקציה שמחזירה +\begin_inset Formula $n$ +\end_inset + + אם +\begin_inset Formula $x$ +\end_inset + + מצפין מצב סופי של +\begin_inset Formula $T$ +\end_inset + + ו +\begin_inset Formula $n$ +\end_inset + + הפלט של המכונה במצב זה. + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +0 +\family roman +\series medium +\shape up +\size normal +\emph off +\numeric off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +אחרת. + זו פונקציה חשיבה: +\begin_inset Formula $\chi_{\varphi_{E}}(x)\cdot(\beta(x,0)-3)$ +\end_inset + + . +\end_layout + +\begin_layout Section +חשיבות +\end_layout + +\begin_layout Standard +היינו בעיצומה של ההוכחה שכל פונקציה חשיבה טיורינג היא חשיבה. +\end_layout + +\begin_layout Claim +) +\numeric on +1 +\numeric off +( היחס +\begin_inset Formula $\varphi(x)$ +\end_inset + + האומר " +\begin_inset Formula $x$ +\end_inset + + מצפין מצב של המכונה +\begin_inset Formula $T$ +\end_inset + +" חשיב. + +\end_layout + +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Claim +) +\numeric on +2 +\numeric off +( היחסים +\begin_inset Formula $\varphi_{s}(x)$ +\end_inset + +, " +\begin_inset Formula $x$ +\end_inset + + מצפין מצב התחלתי של +\begin_inset Formula $T$ +\end_inset + +", " +\begin_inset Formula $x$ +\end_inset + + מצפין מצב סופי של +\begin_inset Formula $T$ +\end_inset + +" - כולם חשיבים. +\end_layout + +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Claim +) +\numeric on +3 +\numeric off +( היחס +\begin_inset Formula $\varphi(x,y)$ +\end_inset + + האומר " +\begin_inset Formula $x,y$ +\end_inset + + מייצגים מצבים של +\begin_inset Formula $T$ +\end_inset + + ו +\begin_inset Formula $y$ +\end_inset + + המצב העוקב של +\begin_inset Formula $x$ +\end_inset + + לפי +\begin_inset Formula $T$ +\end_inset + +" הוא יחס חשיב. +\end_layout + +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Claim +) +\numeric on +4 +\numeric off +( היחס +\begin_inset Formula $\rho(x)$ +\end_inset + + האומר " +\begin_inset Formula $x$ +\end_inset + + מקודד ריצה מסתיימת של +\begin_inset Formula $T$ +\end_inset + +" הוא חשיב. +\end_layout + +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Claim +) +\numeric on +5 +\numeric off +( +\begin_inset Formula $\varphi_{E}(x)=n$ +\end_inset + + זו הפונקציה שמחזירה +\begin_inset Formula $n$ +\end_inset + + אם +\begin_inset Formula $x$ +\end_inset + + מצפין מצב סופי של +\begin_inset Formula $T$ +\end_inset + + ו +\begin_inset Formula $n-1$ +\end_inset + + הפלט של המכונה במצב זה. + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +0 +\family roman +\series medium +\shape up +\size normal +\emph off +\numeric off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +אחרת. + זו פונקציה חשיבה: +\begin_inset Formula $\chi_{\varphi_{E}}(x)\cdot(\beta(x,0)-3)$ +\end_inset + + . + נדרוש ש +\begin_inset Formula $\varphi_{E}(x)=0$ +\end_inset + + אחרת. +\end_layout + +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Claim +היחס " +\begin_inset Formula $x$ +\end_inset + + מקודד מצב התחלתי של +\begin_inset Formula $T$ +\end_inset + + שבו הקלט הוא +\begin_inset Formula $x_{1},...,x_{n}$ +\end_inset + +" הוא יחס חשיב. + נסמן זאת +\begin_inset Formula $\varphi_{s}(x,x_{1},...,x_{n})$ +\end_inset + +. +\end_layout + +\begin_layout Standard +כדי להוכיח את המשפט עלינו להראות ש +\begin_inset Formula $f_{T}^{n}(x_{1},...,x_{n})$ +\end_inset + + פונקציה חשיבה. + נגדיר פונקציה חשיבה באופן הבא: +\begin_inset Formula +\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*} + +\end_inset + + כאשר +\begin_inset Formula $\varphi_{s,0}(x)=\beta(x,1)$ +\end_inset + + - האיבר הראשון בסדרה ש +\begin_inset Formula $x$ +\end_inset + + מקודד, וכאשר +\begin_inset Formula $\mu_{x}^{*}(A(x,y))$ +\end_inset + + זה ה +\begin_inset Formula $x$ +\end_inset + + המזערי עבורו +\begin_inset Formula $\chi_{A}(x,y)=1$ +\end_inset + +. + +\end_layout + +\begin_layout Claim +\begin_inset Formula $f(x_{1},...,x_{n})=f_{T}^{n}(x_{1},...,x_{n})$ +\end_inset + + ובפרט +\begin_inset Formula $f$ +\end_inset + + מוגדרת אם ורק אם ריצת +\begin_inset Formula $T$ +\end_inset + + על +\begin_inset Formula $x_{1},...,x_{n}$ +\end_inset + + עוצרת. +\end_layout + +\begin_layout Proof +ראשית נבדוק שתחומי ההגדרה של שתי הפונקציות זהים. + אם +\begin_inset Formula $T$ +\end_inset + + עוצרת על +\begin_inset Formula $x_{1},...,x_{n}$ +\end_inset + + אז קיים +\begin_inset Formula $x$ +\end_inset + + כך ש +\begin_inset Formula $\rho(x)\wedge\varphi_{s}(\varphi_{s,0}(x_{1},...,x_{n}))$ +\end_inset + + - כלומר קיים +\begin_inset Formula $x$ +\end_inset + + המקודד ריצה מסתיימת של +\begin_inset Formula $T$ +\end_inset + + המתחילה בקלט +\begin_inset Formula $x_{1},...,x_{n}$ +\end_inset + +. + אם נבחר +\begin_inset Formula $x_{0}$ +\end_inset + + הקטן ביותר המקיים זאת אז +\begin_inset Formula +\begin{eqnarray*} +x_{0} & = & \mu_{x}^{*}(\rho(x)\wedge\varphi_{s}(\varphi_{s,0}(x),x_{1},...,x_{n})) +\end{eqnarray*} + +\end_inset + + כי לכל +\begin_inset Formula $x^{\prime}n$ +\end_inset + +. + בנוסף, אם ב- +\begin_inset Formula $\varphi$ +\end_inset + + מופיע סימן פונקציה, סימן יחס, קבוע אישי או משתנה עם אינדקס +\begin_inset Formula $i>n$ +\end_inset + + אז )באינדוקציה( +\begin_inset Formula $g(\varphi)>n$ +\end_inset + +. +\end_layout + +\begin_layout Proof +לכן השאלה האם +\begin_inset Formula $n$ +\end_inset + + מספר גדל של נוסחה שקולה לשאלה האם קיימת נוסחה +\begin_inset Formula $\varphi$ +\end_inset + + באורך קטן-שווה ל- +\begin_inset Formula $n$ +\end_inset + +, שכל הסימנים הלא-לוגיים המופיעים בה הם עם אינדקס קטן או שווה ל- +\begin_inset Formula $n$ +\end_inset + +. + ומספר גדל של +\begin_inset Formula $\varphi$ +\end_inset + + הוא +\begin_inset Formula $n$ +\end_inset + +. + +\end_layout + +\begin_layout Proof +אבל קבוצת הנוסחאות +\begin_inset Formula $\varphi$ +\end_inset + + מאורך קטן-שווה ל- +\begin_inset Formula $n$ +\end_inset + + , שכל הסימנים בה עם אינדקס קטן-שווה ל- +\begin_inset Formula $n$ +\end_inset + + היא סופית, כלומר זהו כימות חסום. + לכן מספיק לבדוק שהפונקציה ששולחת נוסחה למספר גדל שלה היא חשיבה טיורינג. + )זה עסק מייגע, אבל לא קשה.( +\end_layout + +\begin_layout Definition +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Enumerate +תהי +\begin_inset Formula $f:\mathbb{N}\rightarrow\mathbb{N}$ +\end_inset + + , נאמר שתורה +\begin_inset Formula $T$ +\end_inset + + בשפה המרחיבה את +\begin_inset Formula $(0,s)$ +\end_inset + + מייצגת )חלש( את +\begin_inset Formula $f$ +\end_inset + + אם קיימת נוסחה +\begin_inset Formula $\varphi(x,y)$ +\end_inset + + בשפה +\begin_inset Formula $\mathcal{L}$ +\end_inset + + כל שלכל +\begin_inset Formula $n\in Dom(f)$ +\end_inset + + מתקיים +\begin_inset Formula $T\vdash(\forall y)(\varphi(\underline{n},y)\iff\underline{f(n)})$ +\end_inset + + כאשר הסימון +\begin_inset Formula $\underline{n}:=s^{n}(0)$ +\end_inset + + עבור +\begin_inset Formula $s$ +\end_inset + + פונקציית העוקב. +\end_layout + +\begin_layout Enumerate +יחס +\begin_inset Formula $A\subseteq\mathbb{N}$ +\end_inset + + +\bar under +מיוצג +\bar default + ב- +\begin_inset Formula $T$ +\end_inset + + אם +\begin_inset Formula $\chi_{A}$ +\end_inset + + מיוצגת ב +\begin_inset Formula $T$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Definition + +\bar under +תורת פיאנו +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +\lang english +(Peano Arithmetic) +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +\lang hebrew + זו קבוצת הפסוקים הבאה בשפה +\begin_inset Formula $\mathcal{L}=\{0,+,\cdot,s)$ +\end_inset + +: +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $(\forall x)(s(x)\not=0)$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $(\forall x\forall y)(s(x)=s(y)\rightarrow x=y)$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $(\forall x)(x+0=x)$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $(\forall x\forall y)(x+s(y)=s(x+y))$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $(\forall x)(x\cdot0=0)$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $(\forall x\forall y)(x\cdot s(y)=x\cdot y+x)$ +\end_inset + + +\end_layout + +\begin_layout Enumerate + +\bar under +סכימת האינדוקציה: +\bar default + לכל נוסחה +\begin_inset Formula $\varphi(x,y)$ +\end_inset + + אקסיומה מהצורה: +\begin_inset Formula +\[ +(\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_inset + + +\end_layout + +\end_deeper +\begin_layout Theorem +כל פונקציה חשיבה ניתנת לייצוג ב- +\begin_inset Formula $PA$ +\end_inset + +. + יתר על כן, קיימת תורה +\begin_inset Formula $N$ +\end_inset + + סופית כך ש- +\begin_inset Formula $PA\vdash N$ +\end_inset + + וכל פונקציה חשיבה מיוצגת ב- +\begin_inset Formula $N$ +\end_inset + +. +\end_layout + +\begin_layout Standard + +\bar under +תרגיל +\bar default +: אם +\begin_inset Formula $f:\mathbb{N}\rightarrow\mathbb{N}$ +\end_inset + + שלמה ומיוצגת ב- +\begin_inset Formula $PA$ +\end_inset + + אז +\begin_inset Formula $f$ +\end_inset + + חשיבה. +\end_layout + +\begin_layout Corollary +התורה +\begin_inset Formula $N$ +\end_inset + + שמובטחת במשפט, אינה כריעה. +\end_layout + +\begin_layout Proof +תהי +\begin_inset Formula $\varphi(e,z,n)$ +\end_inset + + הנוסחה האומרת שמ"ט +\begin_inset Formula $T_{e}$ +\end_inset + + )שהקוד שלה הוא +\begin_inset Formula $e$ +\end_inset + +( עוצרת על הקלט +\begin_inset Formula $n$ +\end_inset + + אחרי +\begin_inset Formula $z$ +\end_inset + + צעדים. +\end_layout + +\begin_layout Proof +היחס +\begin_inset Formula $\varphi(e,z,n)$ +\end_inset + + חשיב ]הוכחנו[, לכן לפי המשפט מיוצג ב- +\begin_inset Formula $N$ +\end_inset + +. + כלומר אם +\begin_inset Formula $T_{e}(n)$ +\end_inset + + +\bar under +לא עוצרת +\bar default + אז לכל +\begin_inset Formula $z$ +\end_inset + + מתקיים +\begin_inset Formula $N\vdash\neg\varphi(e,z,n)$ +\end_inset + +. + +\end_layout + +\begin_layout Proof +מצד שני, אם +\begin_inset Formula $T_{e}(n)$ +\end_inset + + +\bar under +עוצרת +\bar default + אז +\begin_inset Formula $N\vdash\varphi(e,z,n)$ +\end_inset + + לאיזה +\begin_inset Formula $z$ +\end_inset + +. + נניח בשלילה ש- +\begin_inset Formula $N$ +\end_inset + + כריעה אז +\begin_inset Formula $N\vdash(\exists z)\varphi(e,z,n)$ +\end_inset + + אם ורק אם +\begin_inset Formula $T_{e}(n)$ +\end_inset + + עוצרת. +\end_layout + +\begin_layout Proof +אבל מכריעות נקבל שלכל זוג +\begin_inset Formula $\left\langle e,n\right\rangle $ +\end_inset + + אפשר לדעם האם +\begin_inset Formula $N\vdash(\exists z)\varphi(e,z,n)$ +\end_inset + + או +\begin_inset Formula $N\vdash(\neg\exists z)\varphi(e,z,n)$ +\end_inset + +. + כלומר אפשר להכריע האם +\begin_inset Formula $T_{e}(n)$ +\end_inset + + עוצרת או לא. + אבל לפי משפט רייס זו איננה קבוצה חשיבה. + סתירה. +\end_layout + +\begin_layout Standard + +\bar under +הערה +\bar default +: אם +\begin_inset Formula $N\subseteq T$ +\end_inset + + ) +\begin_inset Formula $N$ +\end_inset + + התורה המובטחת במשפט( אז: +\end_layout + +\begin_layout Enumerate +כל פונקציה חשיבה ניתנת לייצוג ב- +\begin_inset Formula $T$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +לכן, +\begin_inset Formula $T$ +\end_inset + + איננה כריעה, כי אותה ההוכחה ש- +\begin_inset Formula $N$ +\end_inset + + אינה כריעה תעבוד עבור +\begin_inset Formula $T$ +\end_inset + +. +\end_layout + +\begin_layout Standard + +\bar under +הערה +\bar default +: אם תורה +\begin_inset Formula $T$ +\end_inset + + היא חשיבה ושלמה אז +\begin_inset Formula $T$ +\end_inset + + כריעה. + להלן אלגוריתם הכרעה: +\end_layout + +\begin_layout Standard +נראה בהמשך שאם +\begin_inset Formula $T$ +\end_inset + + חשיבה אז +\begin_inset Formula $C_{T}:=\{g(\varphi):T\vdash\varphi\}$ +\end_inset + + נל"ח. + כיוון ש- +\begin_inset Formula $T$ +\end_inset + + שלמה, כדי לבדוק האם +\begin_inset Formula $T\vdash\varphi$ +\end_inset + + נפעיל את המכונה המונה את +\begin_inset Formula $C_{T}$ +\end_inset + +. + בכל שלב נבדוק האם האיבר שהמכונה פלטה הוא הוכחה של +\begin_inset Formula $\varphi$ +\end_inset + + או הוכחה של +\begin_inset Formula $\neg\varphi$ +\end_inset + + . + השלמות מבטיחה לנו שאחד מהם יתקבל בזמן סופי. + אם מתקבל +\begin_inset Formula $\varphi$ +\end_inset + + - ניצחנו. + אם מתקבל +\begin_inset Formula $\neg\varphi$ +\end_inset + + - גם ניצחנו. +\end_layout + +\begin_layout Corollary +כל תורה +\begin_inset Formula $T$ +\end_inset + + כך ש- +\begin_inset Formula $N\subseteq T\subseteq PA$ +\end_inset + + מהמסקנה הקודמת אינה כריעה. + )למשל תורת המספרים איננה כריעה(. +\end_layout + +\begin_layout Section +פונקציות יציגות +\end_layout + +\begin_layout Standard + +\bar under +תזכורת: +\bar default + פונקציה +\begin_inset Formula $f:\mathbb{N}^{k}\rightarrow\mathbb{N}$ +\end_inset + + תקרא מיוצגת )חלש( בתורה +\begin_inset Formula $T$ +\end_inset + + )בשפה עם סימן קבוע +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +0 +\family roman +\series medium +\shape up +\size normal +\emph off +\numeric off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +וסימן פונקציה חד מקומי +\begin_inset Formula $s$ +\end_inset + +( אם קיימת נוסחה +\begin_inset Formula $\varphi(x,y)$ +\end_inset + + כך שלכל +\begin_inset Formula $\bar{n}\in Dom(f)$ +\end_inset + + מתקיים +\begin_inset Formula +\begin{eqnarray*} +T & \vdash & (\forall y)(\varphi(\underline{\bar{n}},y)\iff\underline{f(n)}=y) +\end{eqnarray*} + +\end_inset + +כאשר +\begin_inset Formula $\underline{n}=s^{n}(0)$ +\end_inset + +. + +\end_layout + +\begin_layout Theorem +כל פונקציה חשיבה יציגה בתורת פאנו ואפילו יש תת-תורה סופית של +\begin_inset Formula $PA$ +\end_inset + + שבה כל פונקציה חשיבה יציגה. +\end_layout + +\begin_layout Corollary +תהי +\begin_inset Formula $N\subseteq PA$ +\end_inset + + כמובטח במשפט. + אזי +\begin_inset Formula $N$ +\end_inset + + אינה כריעה. + +\end_layout + +\begin_layout Proof +יהי +\begin_inset Formula $\varphi(e,n,z)$ +\end_inset + + היחס האומר "המכונה שהקוד שלה +\begin_inset Formula $e$ +\end_inset + + עצרה על הקלט +\begin_inset Formula $n$ +\end_inset + + אחרי לכל היותר +\begin_inset Formula $z$ +\end_inset + + מהלכים". + אז ברור ש- +\begin_inset Formula $\varphi(e,n,z)$ +\end_inset + + הוא יחס חשיב. + מהמשפט נובע שלכל שלשה +\begin_inset Formula $\left\langle e,n,z\right\rangle \in\mathbb{N}^{3}$ +\end_inset + + מתקיים +\begin_inset Formula $N\vdash\varphi(e,n,z)$ +\end_inset + + אם ורק אם +\begin_inset Formula $\left\langle e,n,z\right\rangle $ +\end_inset + + עומדת ביחס, כלומר המכונה +\begin_inset Formula $e$ +\end_inset + + עוצרת על +\begin_inset Formula $n$ +\end_inset + + אחרי לא יותר מ +\begin_inset Formula $z$ +\end_inset + + צעדים. + לכן אם +\begin_inset Formula $\left\langle e,n\right\rangle $ +\end_inset + + עוצרת יש +\begin_inset Formula $z_{0}$ +\end_inset + + כך ש +\begin_inset Formula $N\vdash\varphi(\underline{e},\underline{n},\underline{z_{0}})$ +\end_inset + +. + לכן אם +\begin_inset Formula $\left\langle e,n\right\rangle $ +\end_inset + + עוצרת אז +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\begin_inset Formula $N\vdash(\exists z)\varphi(\underline{e},\underline{n},z)$ +\end_inset + +. + מצד שני, אם +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit + +\begin_inset Formula $\left\langle e,n\right\rangle $ +\end_inset + + לא עוצרת אז +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\begin_inset Formula $N\not\vdash\varphi(\underline{e},\underline{n},\underline{z_{0}})$ +\end_inset + + לכל +\begin_inset Formula $\underline{z_{0}}$ +\end_inset + +. + אבל +\begin_inset Formula $\mathbb{N}\models PA$ +\end_inset + + ולכן +\begin_inset Formula $\mathbb{N}\models N$ +\end_inset + + . + לכן לא ייתכן ש +\begin_inset Formula $N\vdash(\exists z)\varphi(\underline{e},\underline{n},z)$ +\end_inset + + אבל מהנחתנו זה לא מתקיים. + יוצא +\begin_inset Formula $N\vdash(\exists z)\varphi(\underline{e},\underline{n},z)$ +\end_inset + + אם ורק אם +\begin_inset Formula $\left\langle e,n\right\rangle $ +\end_inset + + עוצרת. + לכן אילו הייתה +\begin_inset Formula $N$ +\end_inset + + כריעה היינו יכולים להכריע את בעיית העצירה: בהינתן זוג +\begin_inset Formula $\left\langle e,n\right\rangle $ +\end_inset + + היינו פשוט שואלים אם +\begin_inset Formula $N\vdash(\exists z)(\underline{e},\underline{n},z)$ +\end_inset + +. + אם כן - +\begin_inset Formula $\left\langle e,n\right\rangle $ +\end_inset + + עוצרת, ואם לא אז +\begin_inset Formula $\left\langle e,n\right\rangle $ +\end_inset + + לא עוצרת. +\end_layout + +\begin_layout Corollary +כל תורה +\begin_inset Formula $N\subseteq T\subseteq PA$ +\end_inset + + מהמסקנה הקודמת אינה כריעה. +\end_layout + +\begin_layout Corollary +ניגש להוכחת המשפט עצמו. + +\end_layout + +\begin_layout Standard +תהי +\begin_inset Formula $N\subseteq PA$ +\end_inset + + התורה הבאה: +\end_layout + +\begin_layout Itemize +\begin_inset Formula $PA(1)-PA(6)$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $(N7)$ +\end_inset + +: +\begin_inset Formula $(\forall x)(\neg x<0)$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $(N8)$ +\end_inset + +: +\begin_inset Formula $(\forall x\forall y)(xn$ +\end_inset + +, הבניה במקרה ב' תייצר +\begin_inset Formula $2_{e,k}$ +\end_inset + + - הכרזה. + )ובתנאי שבשלב ה- +\begin_inset Formula $i$ +\end_inset + + כבר נכנסו ל- +\begin_inset Formula $A$ +\end_inset + + כל האיברים שבהם נעשה שימוש חיובי בחישוב של +\begin_inset Formula $T_{e}^{A}(k)$ +\end_inset + +. +\end_layout + +\begin_layout Proof +אבל מהדיון הקודם, כל תנאי יכול לייצר לכל היותר מספר סופי של הכרזות. + אז האחרונה מביניהן שהכרח לא תשתנה, ז"א תהיה קבועה. +\end_layout + +\begin_layout Proof +עד עתה: בנינו את +\begin_inset Formula $A$ +\end_inset + +, הראנו ש- +\begin_inset Formula $A$ +\end_inset + + מקיימת את התנאים +\begin_inset Formula $1_{e}$ +\end_inset + + ואת +\begin_inset Formula $2_{e,k}$ +\end_inset + + )לפי א' הנ"ל( וברור שהבניה חשיבה. + כיוון ש- +\begin_inset Formula $A$ +\end_inset + + מקיימת את +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit + +\begin_inset Formula $1_{e}$ +\end_inset + + לכל +\begin_inset Formula $e$ +\end_inset + +, ברור ש- +\begin_inset Formula $A$ +\end_inset + + אינה חשיבה. + כיוון שהבניה חשיבה, אם נגדיר +\begin_inset Formula $s(n)$ +\end_inset + + להיות הקבוצה +\begin_inset Formula $A_{n}$ +\end_inset + + שהתקבלה בשלב ה- +\begin_inset Formula $n$ +\end_inset + + של הבנייה נקבל ש- +\begin_inset Formula $A$ +\end_inset + + נל"ח, כי +\begin_inset Formula $s(n)$ +\end_inset + + חשיבה. +\end_layout + +\begin_layout Proof +נותר לוודא ש- +\begin_inset Formula $deg(A^{*})\le0$ +\end_inset + +. + ראינו בתרגיל +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\numeric on +\bar default +\noun default +\color inherit +11 +\family roman +\series medium +\shape up +\size normal +\emph off +\numeric off +\bar no +\noun off +\color none + +\family default +\series default +\shape default +\size default +\emph default +\bar default +\noun default +\color inherit +טענה שאומרת שאם +\begin_inset Formula $A^{*}=dim(B_{i})$ +\end_inset + + עבור +\begin_inset Formula $i\in\mathbb{N}$ +\end_inset + + כך ש- +\begin_inset Formula $B_{i}$ +\end_inset + + חשיבה מ +\numeric on +- +\numeric off + +\begin_inset Formula $A$ +\end_inset + + אז +\begin_inset Formula $deg(A^{*})\le0^{\prime}$ +\end_inset + +. + נגדיר +\begin_inset Formula $\left\langle e,k\right\rangle \in B_{i}$ +\end_inset + +אם ורק אם בשלב ה- +\begin_inset Formula $i$ +\end_inset + + של הבנייה יש +\begin_inset Formula $2_{e,k}$ +\end_inset + + - הכרזה שאיננה פצועה. + כיוון שהבניה חשיבה +\begin_inset Formula $B_{i}$ +\end_inset + + יחס חשיב. + לפי )א( הנ"ל +\begin_inset Formula $T_{e}^{A}(k)(\iff\left\langle e,k\right\rangle \in B_{i})$ +\end_inset + + עוצרת אם ורק אם +\begin_inset Formula $dim\chi_{B_{i}}(\left\langle e,k\right\rangle )=1$ +\end_inset + +. +\end_layout + +\begin_layout Theorem +לכל דרגה +\begin_inset Formula $0^{\prime}\le a$ +\end_inset + + קיימת דרגה +\begin_inset Formula $b$ +\end_inset + + כך ש- +\begin_inset Formula $b^{\prime}=0^{\prime}\cup b=a$ +\end_inset + +. +\end_layout + +\begin_layout Standard + +\bar under +רעיון ההוכחה +\bar default +: נבחר +\begin_inset Formula $g:\mathbb{N}\rightarrow\mathbb{N}$ +\end_inset + + כך ש- +\begin_inset Formula $deg(g)=a$ +\end_inset + +, אפשר לבחור +\begin_inset Formula $g$ +\end_inset + + כזו שלמה. + נרצה לבנות +\begin_inset Formula $f:\mathbb{N}\rightarrow\mathbb{N}$ +\end_inset + + כך ש- +\begin_inset Formula $f^{*}$ +\end_inset + + חשיבה מ- +\begin_inset Formula $0^{\prime}\cup deg(f)$ +\end_inset + + ו- +\begin_inset Formula $g$ +\end_inset + + חשיבה מ- +\begin_inset Formula $f^{*}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +נרצה להגשים שני סוגים תנאים: +\end_layout + +\begin_layout Itemize +\begin_inset Formula $1_{e,k}$ +\end_inset + + - להחליט האם +\begin_inset Formula $T_{e}^{f}(k)$ +\end_inset + + עוצרת +\end_layout + +\begin_layout Itemize +\begin_inset Formula $2_{n}$ +\end_inset + + - לוודא ש- +\begin_inset Formula $f(m)=g(n)$ +\end_inset + + לאיזה +\begin_inset Formula $m\in\mathbb{N}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +כרגיל נמספר את התנאים +\begin_inset Formula $\{c_{i}\}$ +\end_inset + +, ובשלב ה- +\begin_inset Formula $i$ +\end_inset + + אם אנו בתנאי +\begin_inset Formula $1_{e,k}$ +\end_inset + + ויש +\begin_inset Formula $\sigma:\mathbb{N}\rightarrow\mathbb{N}$ +\end_inset + + סופית שמתיישבת עם +\begin_inset Formula $f_{i-1}$ +\end_inset + + כך ש- +\begin_inset Formula $T_{e}^{\sigma}(k)$ +\end_inset + + עוצרת, נגדיר +\begin_inset Formula $f_{i}=f_{i-1}\cup\sigma$ +\end_inset + + ואחרת נגדיר +\begin_inset Formula $f_{i}=f_{i-1}$ +\end_inset + +. + ואם בשלב ה- +\begin_inset Formula $i$ +\end_inset + + אנו בתנאי +\begin_inset Formula $2_{n}$ +\end_inset + + אז נבחר +\begin_inset Formula $m$ +\end_inset + + מזערי כך שאינו בתחום של +\begin_inset Formula $f_{i-1}$ +\end_inset + + ונגדיר +\begin_inset Formula $f_{i}(m)=g(n)$ +\end_inset + +. + לסיכום: יוצא שהבניה חשיבה מ- +\begin_inset Formula $0^{\prime}\cup a=a$ +\end_inset + + וחשיבה גם מ- +\begin_inset Formula $0^{\prime}\cup b$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset space ~ +\end_inset + + +\end_layout + +\begin_layout Proof +תהי +\begin_inset Formula $g$ +\end_inset + + כנ"ל ונמצא פונקציה +\begin_inset Formula $f$ +\end_inset + + כך ש- +\begin_inset Formula $deg(f)$ +\end_inset + + תענה על הדרישות. +\end_layout + +\begin_layout Proof +\begin_inset Formula $b\cup b^{\prime}\le b^{\prime}$ +\end_inset + + ולכן יספיק למצוא +\begin_inset Formula $b$ +\end_inset + + כך ש- +\begin_inset Formula $b^{\prime}\le a\le b$ +\end_inset + +. + מזה נבטיח שיש שיוויונות לכל אורך הדרך. + אז צריך למצוא +\begin_inset Formula $b$ +\end_inset + + כך ש- +\begin_inset Formula $b^{\prime}$ +\end_inset + + חשיבה מ- +\begin_inset Formula $b$ +\end_inset + + ומ- +\begin_inset Formula $0^{\prime}$ +\end_inset + +. + +\end_layout + +\begin_layout Proof +כרגיל נמספר את התנאים )כולם ביחד( במספור חשיב +\begin_inset Formula $\{e_{i}\}_{i=0}^{\infty}$ +\end_inset + + ונניח שלכל +\begin_inset Formula $i\le n$ +\end_inset + + בנינו פונקציה +\begin_inset Formula $f_{i}$ +\end_inset + + )עם תחום סופי( כך ש- +\begin_inset Formula $f_{i}\subseteq f_{j}$ +\end_inset + + אם +\begin_inset Formula $i\le j$ +\end_inset + +. +\end_layout + +\begin_layout Proof + +\bar under +בניית +\begin_inset Formula $f_{n+1}$ +\end_inset + +: +\end_layout + +\begin_deeper +\begin_layout Itemize +אם +\begin_inset Formula $e_{n+1}$ +\end_inset + + הוא תנאי מסוג +\begin_inset Formula $1_{e,k}$ +\end_inset + +: נבדוק האם יש +\begin_inset Formula $\sigma$ +\end_inset + + סופית שמתיישבת עם +\begin_inset Formula $f_{n}$ +\end_inset + + כך ש- +\begin_inset Formula $T_{e}^{\sigma}(k)$ +\end_inset + + עוצרת. + אם כן, נגדיר +\begin_inset Formula $f_{n+1}=f_{n}\cup\sigma$ +\end_inset + + אחרת נגדיר +\begin_inset Formula $f_{n+1}=f_{n}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +אם +\begin_inset Formula $e_{n+1}$ +\end_inset + + הוא תנאי מסוג +\begin_inset Formula $2_{k}$ +\end_inset + + אז נמצא +\begin_inset Formula $m$ +\end_inset + + מזערי שאיננו בתחום של +\begin_inset Formula $f_{n}$ +\end_inset + + ונגדיר +\begin_inset Formula $f_{n+1}=f_{n}\cup\left\langle m,g(k)\right\rangle $ +\end_inset + +. + נגדיר +\begin_inset Formula $f={\displaystyle \bigcup_{i=0}^{\infty}}f_{i}$ +\end_inset + + ואז +\begin_inset Formula $f$ +\end_inset + + פונקציה שלמה. +\end_layout + +\begin_layout Standard +כדי לממש את הבניה: +\end_layout + +\begin_layout Itemize +אם אנחנו בתנאי +\begin_inset Formula $1_{e,k}$ +\end_inset + + צריך לדעת האם קיים +\begin_inset Formula $\sigma$ +\end_inset + + כזה. + כדי לענות על השאלה הזו אנו יכולים מ- +\begin_inset Formula $0^{\prime}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +אם אנחנו בתנאי מסוג +\begin_inset Formula $2_{k}$ +\end_inset + +, אין בעיה למצוא את +\begin_inset Formula $m$ +\end_inset + +. + כל מה שצריך זה לחשב את +\begin_inset Formula $g(k)$ +\end_inset + + ואת זה אפשר לעשות מ- +\begin_inset Formula $g$ +\end_inset + +. +\end_layout + +\begin_layout Standard +נשאר להראות כי את +\begin_inset Formula $b^{\prime}$ +\end_inset + + ניתן לחשב מ- +\begin_inset Formula $b$ +\end_inset + + ומ- +\begin_inset Formula $0^{\prime}$ +\end_inset + + אבל +\begin_inset Formula $b^{\prime}=deg(f^{*})$ +\end_inset + + ו- +\begin_inset Formula $f^{*}$ +\end_inset + + זהו האוב שעונה לכל שאלה מהצורה "האם +\begin_inset Formula $T_{e}^{f}(k)$ +\end_inset + + עוצרת?". + ראשית אם אנו יודעים את הבניה של +\begin_inset Formula $t$ +\end_inset + + אז אנו יודעים לענות על כל השאלות מהצורה הנ"ל. + אבל הבניה חשיבה גם מ- +\begin_inset Formula $0^{\prime}$ +\end_inset + + וגם מ- +\begin_inset Formula $b^{\prime}$ +\end_inset + + )ביחד( ולכן +\begin_inset Formula $b^{\prime}\le b\cup0^{\prime}$ +\end_inset + + כנדרש. +\end_layout + +\end_deeper +\begin_layout Corollary +הפונקציה +\begin_inset Formula $a\rightarrow a^{\prime}$ +\end_inset + + איננה חח"ע. +\end_layout + +\end_body +\end_document -- cgit v1.3.1