IndexSet2 2008-06-27 14:05:00 2008-06-27 14:05:49 Definition % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here In computability theory, a set $A\subseteq\omega$ is called an \emph{index set} if for all $x, y$, \begin{equation*} x\in A, \varphi_x=\varphi_y \Longrightarrow y\in A. \end{equation*} $\varphi_x$ stands for the partial function with G\"odel number (or index) $x$. Thus, if $A$ is an index set and $\varphi_x=\varphi_y$, then either $x, y\in A$ or $x, y\not\in A$. Intuitively, if $A$ contains the G\"odel index $x$ of a partial function $\varphi$, then $A$ contains all indices for the partial function. (Recall that there are $\aleph_0$ G\"odel numbers for each partial function.) It is instructive to compare the notion of an index set in computability theory with that of an \emph{indexing} set.