#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