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