Enumerability

Last class, and occasionally throughout the semester we have discussed two closely related notions:

• Decidability
• Recursiveness

There is something subtle about the definitions of the notions: We not only require a procedure for deciding when a tuple is in a relation, but also for deciding when it is not in the relation.

Now, we consider dropping the negative half. The book doesn't introduce terms for the informal notions, and so I'll use ones that are relatively standard.

A relation is semidecidable if there is a procedure such that, given any tuple that is in the relation, tells that it is in the relation.

A relation is listable (or, effectively enumerable ) if there is a procedure that lists all the %$n$%-tuples in the relation.

Fact. A relation is semidecidable if and only if it is listable.

Informal Proof. If a relation is listable, then, given an %$n$%-tuple, we can tell that it is in the relation by watching the list and, if it appears, saying that it is in the relation, and so a listable relation is semidecidable. Note that we never know for sure if a tuple is not in the list—maybe it just hasn't come up yet.

Conversely, if a relation is semidecidable, we can list it using a "busy beaver" procedure: We apply the semidecision procedure to the first tuple for one step, then the first two tuples for two steps each, and so on, and whenever we find out that a tuple is in the relation, we add it to the list.

Fact. A relation that holds of only finitely many tuples is decidable if it is listable.

Informal Proof. Run the listing procedure until all the tuples have been listed and then use the obvious decision procedure.

Fact. A decidable relation is listable.

Informal Proof. List the tuples in some order. Decide for each one whether or not it is in the relation. If it is, add it to the list.

Now, the formal notion:

A relation %$Rv_{1},\dotsc ,v_{k}$% is recursively enumerable if there is a recursive relation %$Sv_{1},\dotsc ,v_{k}v_{k+1},\dotsc ,v_{k+l}$% such that a tuple %$n_{1},\dotsc ,n_{k}$% is in %$R$% if there are %$m_{1},\dotsc ,m_{l}$% such that %$Sn_{1},\dotsc ,n_{k},m_{1},\dotsc ,m_{l}$%.

Representable Functions

Definition. A function is representable if it is representable as a relation.

So, for example, the addition function is representable since the ternary relation %$\{\langle l,m,n\rangle: l+m=n\}$% is representable.

Theorem 33H. The following are equivalent for any function %$f$%:

• %$f$% is computable.
• %$f$% is decidable as a relation.
• %$f$% is effectively enumerable as a relation.

Informal Proof. If %$f$% is computable, then, given an %$n+1$%-tuple, we can compute the function on the first %$n$% members of the tuple to construct an %$n+1$%-tuple, if that is our %$n+1$%-tuple, it is in, if not, it is out.

If %$f$% is decidable as a relation then %$f$% is effectively enumerable as a relation, because that is always true—see the fact above.

If %$f$% is effectively enumerable as a relation, to compute the value of the function on an %$n$%-tuple, list until you find an %$n+1$%-tuple that begins with the %$n$%-tuple, and read off the answer.

-- ShaughanLavine - 22 Feb 2008

Next, we prove a bit more than that every bounded formula is numeralwise determined.

Theorem 33I.

1. Every atomic formula is numeralwise determined in %$A_E$%.
2. If %$\phi$% and%$\psi$% are numeralwise determined in %$A_E$% then so are %$\lnot\phi$% and %$\phi\rightarrow\psi$%.
3. If %$\phi$% is numeralwise determined in %$A_E$% then so are %$\forall x<y\phi$% and %$\exists x<y\phi$%.

Proof. Case 1 is the proof of the atomic part of Theorem 33C.

Case 2 is just like the same clauses in the proof of Theorem 33C.

Case 3. We do the existential case first. That is, we must show that %$\exists x<y\phi = \exists x(x<y\land\phi )$% is numeralwise determined. To simplify notation, pretend that %$\exists x(x<y\land\phi )$% is %$\exists v_{3}(v_{3}<v_{2}\land\phi )$% and that the only free variables in %$\phi$% are %$v_1$%, %$v_2$%, and %$v_3$%. To show that the formula is numeralwise determined, we must show for any two numbers %$a,b$% that we can either prove %$\exists v_{3}(v_{3}<v_{2}\land\phi )(S^{a}0,S^{b}0)$% or its negation in %$A_E$%.

Subcase a. %$\exists v_{3}(v_{3}<v_{2}\land\phi )(S^{a}0,S^{b}0)$% is true. Then there is some number %$c$% such that %$c<b$% and %$\phi (S^{a}0,S^{b}0,S^{c}0)$% is true. By the hypothesis of Case 3, %$\phi$% is numeralwise determined, and so %$A_{E}\vdash\phi (S^{a}0,S^{b}0,S^{c}0)$%. Since %$c<b$%, by Case 1, %$A_{E}\vdash S^{c}0<S_{b}0)$%. That is what we need.

-- ShaughanLavine - 25 Feb 2008

• Set #DENSITY = 232
• Set #SIZE = +3