# The Recursion Theorem .... Searcoid, Theroem 1.3.24 .... ....

• MHB
• Math Amateur
In summary: I hope someone can help me to get a sense of how it is related to the notion of recursion ...Peter==================================================================================It may help MHB readers of the above post to have access to Searcoid's remarks at the start of the section on Induction and Recursion ... so I am providing the same ... as follows ...It may alxo help MHB readers to have access top Searcoid's Definition 1.3 4 ... so I am also providing access ... as follows ...Hope that helps ...Peter
Math Amateur
Gold Member
MHB
I am reading Micheal Searcoid's book: "Elements of Abstract Analysis" ... ...

I am currently focused on understanding Chapter 1: Sets ... and in particular Section 1.3 Ordered Sets ...

I need some help in fully understanding Theorem 1.3.24 ...

View attachment 8433In the statement of Theorem 1.3.24 we read the following:

" ... ... Suppose that $$\displaystyle r$$ is a function into $$\displaystyle X$$ whose domain satisfies the hypothesis that $$\displaystyle \{ g \in X^{ \grave{ \alpha } } \mid \alpha \in W ; \beta \in \grave{ \alpha } \Longrightarrow ( g \mid_{ \grave{ \beta } } , g( \beta ) ) \in r \} \subseteq \text{ dom} ( r )$$

... ... "

*** NOTE *** ... ... the definition of LOWER SEGMENTS $$\displaystyle \grave{ \alpha }$$ and $$\displaystyle \grave{ \beta }$$ are given in the scanned text of Definition 1.3.4 ... see below ...
Now ... I do not understand how the expression $$\displaystyle \{ g \in X^{ \grave{ \alpha } } \mid \alpha \in W ; \beta \in \grave{ \alpha } \Longrightarrow ( g \mid_{ \grave{ \beta } } , g( \beta ) ) \in r \} \subseteq \text{ dom} ( r )$$ relates to the common notion of recursion ... ...Can someone explain how the expression above relates to recursion and what the overall strategy of Theorem 1.3.24 is?In particular ... related to the above expression ...

1. How does a set of functions $$\displaystyle g$$ form a subset of the domain of a function $$\displaystyle r$$ ... ... ? ( ... I know it is possible ... but why are we doing it?)

2. $$\displaystyle ( g \mid_{ \grave{ \beta } } , g( \beta ) )$$ appears to be an ordered pair ... but its first member $$\displaystyle g \mid_{ \grave{ \beta } }$$ seems to be the restriction of a function ... how can this be ... ?I am somewhat lost in making sense of the expression$$\displaystyle \{ g \in X^{ \grave{ \alpha } } \mid \alpha \in W ; \beta \in \grave{ \alpha } \Longrightarrow ( g \mid_{ \grave{ \beta } } , g( \beta ) ) \in r \} \subseteq \text{ dom} ( r )$$ ... ... I hope someone can help me to get a sense of how it is related to the notion of recursion ...Peter
==================================================================================It may help MHB readers of the above post to have access to Searcoid's remarks at the start of the section on Induction and Recursion ... so I am providing the same ... as follows ...View attachment 8434
It may alxo help MHB readers to have access top Searcoid's Definition 1.3 4 ... so I am also providing access ... as follows ...
View attachment 8435
Hope that helps ...

Peter

#### Attachments

• Searcoid - Theorem 1.3.24 ... Recursion Theorem ... ....png
28.6 KB · Views: 87
• Searcoid - 1 - Start of section on Induction and Recursion ... ... PART 1 ... ....png
32.2 KB · Views: 64
• Searcoid - Definition 1.3.4 ... ....png
28.5 KB · Views: 80
Last edited:
Peter said:
I am reading Micheal Searcoid's book: "Elements of Abstract Analysis" ... ...

I am currently focused on understanding Chapter 1: Sets ... and in particular Section 1.3 Ordered Sets ...

I need some help in fully understanding Theorem 1.3.24 ...

In the statement of Theorem 1.3.24 we read the following:

" ... ... Suppose that $$\displaystyle r$$ is a function into $$\displaystyle X$$ whose domain satisfies the hypothesis that $$\displaystyle \{ g \in X^{ \grave{ \alpha } } \mid \alpha \in W ; \beta \in \grave{ \alpha } \Longrightarrow ( g \mid_{ \grave{ \beta } } , g( \beta ) ) \in r \} \subseteq \text{ dom} ( r )$$

... ... "

*** NOTE *** ... ... the definition of LOWER SEGMENTS $$\displaystyle \grave{ \alpha }$$ and $$\displaystyle \grave{ \beta }$$ are given in the scanned text of Definition 1.3.4 ... see below ...
Now ... I do not understand how the expression $$\displaystyle \{ g \in X^{ \grave{ \alpha } } \mid \alpha \in W ; \beta \in \grave{ \alpha } \Longrightarrow ( g \mid_{ \grave{ \beta } } , g( \beta ) ) \in r \} \subseteq \text{ dom} ( r )$$ relates to the common notion of recursion ... ...Can someone explain how the expression above relates to recursion and what the overall strategy of Theorem 1.3.24 is?In particular ... related to the above expression ...

1. How does a set of functions $$\displaystyle g$$ form a subset of the domain of a function $$\displaystyle r$$ ... ... ? ( ... I know it is possible ... but why are we doing it?)

2. $$\displaystyle ( g \mid_{ \grave{ \beta } } , g( \beta ) )$$ appears to be an ordered pair ... but its first member $$\displaystyle g \mid_{ \grave{ \beta } }$$ seems to be the restriction of a function ... how can this be ... ?I am somewhat lost in making sense of the expression$$\displaystyle \{ g \in X^{ \grave{ \alpha } } \mid \alpha \in W ; \beta \in \grave{ \alpha } \Longrightarrow ( g \mid_{ \grave{ \beta } } , g( \beta ) ) \in r \} \subseteq \text{ dom} ( r )$$ ... ... I hope someone can help me to get a sense of how it is related to the notion of recursion ...Peter
==================================================================================It may help MHB readers of the above post to have access to Searcoid's remarks at the start of the section on Induction and Recursion ... so I am providing the same ... as follows ...
It may alxo help MHB readers to have access top Searcoid's Definition 1.3 4 ... so I am also providing access ... as follows ...

Hope that helps ...

Peter

I have been reflecting on the above post and, in particular the set $$\displaystyle \{ g \in X^{ \grave{ \alpha } } \mid \alpha \in W ; \beta \in \grave{ \alpha } \Longrightarrow ( g \mid_{ \grave{ \beta } } , g( \beta ) ) \in r \} \subseteq \text{ dom} ( r )$$A few thoughts follow ...

First ... importantly, where a and b are any sets, an ordered pair is the pair $$\displaystyle (a,b)$$ where $$\displaystyle (a, b)$$ is equal to the set $$\displaystyle \{ \{ a \} , \{ a, b \} \}$$ ... and a function is a set of ordered pairs no two of which have the same first member ...So ... the set $$\displaystyle G =$$ $$\displaystyle \{ g \in X^{ \grave{ \alpha } } \mid \alpha \in W ; \beta \in \grave{ \alpha } \Longrightarrow ( g \mid_{ \grave{ \beta } } , g( \beta ) ) \in r \} \subseteq \text{ dom} ( r )$$ is a set of functions ... so therefore the set $$\displaystyle G$$ is a set of sets of ordered pairs where no two of the ordered pairs have the same first member ...

So ... given that r is a function into a non-empty set $$\displaystyle X$$ and that $$\displaystyle G \subseteq \text{ dom} (r)$$ ... we have that $$\displaystyle r$$ is a set of ordered pairs where the first element of the ordered pair is a function (set of ordered pairs etc etc ... ... ) and the second member of each ordered pair is a member of the set $$\displaystyle X$$ ... ... Is the above interpretation correct as far as it goes ...?Note that I would still value any explanations of how the above set $$\displaystyle G$$ and the function $$\displaystyle r$$ fit into the general notion of recursion ... just a simple sensemaking would do ... I know Searcoid made some sensemaking remarks ... but unfortunately I cannot follow them ..

Hope someone can help ...

Peter

Last edited:

## 1. What is the Recursion Theorem?

The Recursion Theorem, also known as Searcoid Theorem 1.3.24, is a mathematical theorem that states that any computable function can be expressed using a recursive function. This means that any algorithm can be broken down into simpler steps and repeated until a desired result is achieved.

## 2. Who developed the Recursion Theorem?

The Recursion Theorem was developed by mathematician John Searcoid, who introduced it in his book "Computability and Unsolvability" in 1954. It is one of the fundamental theorems in the field of computability theory.

## 3. What is the importance of the Recursion Theorem in computer science?

The Recursion Theorem is important in computer science because it provides a theoretical basis for the concept of recursion in programming languages. It allows for the design of more efficient and elegant algorithms by breaking down complex problems into simpler, recursive steps.

## 4. How does the Recursion Theorem relate to the Halting Problem?

The Recursion Theorem is closely related to the Halting Problem, which is a problem in computer science that asks whether a program will ever terminate or continue to run indefinitely. The Recursion Theorem proves that the Halting Problem is unsolvable, meaning there is no algorithm that can determine whether a program will halt or not.

## 5. Are there any limitations or exceptions to the Recursion Theorem?

There are some limitations and exceptions to the Recursion Theorem. For example, it only applies to computable functions, meaning those that can be calculated using a finite number of steps. It also does not apply to non-computable functions, such as the Halting Problem. Additionally, the theorem assumes that the underlying model of computation is powerful enough to express recursive functions.

Replies
1
Views
920
Replies
1
Views
1K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
2
Views
1K
Replies
5
Views
2K
Replies
1
Views
1K
Replies
2
Views
1K
Replies
4
Views
1K
Replies
2
Views
2K