# Algorithmic specifications

1. Feb 2, 2005

### gnome

This one is from "A Programming Approach to Computability" , by A.J. Kfoury, Robert Moll, & Michael Arbib (1982), on page 77.
How do they get all that out of $\sigma \leq \mu$ ???

[This section continues as follows:

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.

2. Feb 2, 2005

### Hurkyl

Staff Emeritus
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?

3. Feb 2, 2005

### 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)$?

4. Feb 2, 2005

### 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? :yuck: :yuck:

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

Last edited: Feb 2, 2005