How does \sigma \leq \mu relate to the subset relation and ordering of sets?

[gnome]

This one is from "A Programming Approach to Computability" , by A.J. Kfoury, Robert Moll, & Michael Arbib (1982), on page 77.

3 Example Let $\sigma:N \rightarrow N$ and $\mu:N \rightarrow N$ be two computable functions such that $\sigma \leq \mu$. This means that whenever $\sigma (y)$ is defined, so is $\mu (y)$, and in this case we must have $\sigma (y) = \mu (y)$. Thus $\sigma$ is a subset of $\mu$ when considered as a set of ordered pairs of natural numbers.

How do they get all that out of $\sigma \leq \mu$ ?


[This section continues as follows:

Now define $\psi_3$ by the specification:

$$\psi_3(x,y) = \left \{ \begin{array} {cc} \mu(y), &\text{if} \;\phi_x(x)\downarrow \\<br /> \sigma (y), &otherwise \end{array}\right$$

At first glance, the second line asks us to return a value $\sigma(y)$ based on the assumption that computation P_x on x runs on forever. But on closer inspection, we realize that $\sigma \leq \mu$ tells us that if $\sigma(y)$ is defined it equals $\mu(y)$. Thus we can compute $\psi_3(x,y)$ as follows: Start the computations of $\sigma(y)$ and of P_x at the same time. If a result $\sigma(y)$ is returned, halt--for then $\sigma (y) = \mu (y)$ is the desired answer, no matter whether or not P_x halts on x. But if P_x halts on x before a result $\sigma(y)$ is returned, stop computing $\sigma(y)$ and start computing $\mu(y)$. If and when this computation halts, the $\mu(y)$ then returned is the desired answer.

Are these guys kidding, or what?

In every previous instance that I have found in this book, they used $\leq$ to represent "less than or equal to". Here, I guess maybe they are using it to signify "is a subset of". But even if that's the case, how do they conclude (in the second paragraph), that "if $\sigma(y)$ is defined, it equals $\mu(y)$"?

I can't say that I like this stuff, but I'm determined to understand it if I can, so any suggestions will be appreciated.

 

[Hurkyl]

It means "less than or equal to" here too. And it is synonymous with the subset relation!

It is common to partially order sets by inclusion, so the subset relation is the order on sets.


Are you familiar with the definition of a function as a set of ordered pairs?

 

[gnome]

$(a,b) \in f \mbox{ and }(a,c) \in f \mbox{ implies } b=c.$

here, that becomes

$(y,\sigma(y)) \in \sigma \mbox{ and } (y,\mu(y)) \in \mu$?

and if $\sigma \subseteq \mu$, then:

$(y,\sigma(y)) \in \mu \mbox{ and } (y,\mu(y)) \in \mu \mbox{ so } \sigma(y)=\mu(y)$?

 

[gnome]

That was 5 months ago. And this:
>>It is common to partially order sets by inclusion, so the subset relation is the order on sets.
was 2 years ago.

How'm I supposed to remember that?

Well, now it all falls into place. Thanks Hurkyl.