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.tex | 3143 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 3143 insertions(+) create mode 100644 notes.tex (limited to 'notes.tex') 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