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

[Math Amateur]

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 ...

Theorem 1.3.24 reads as follows:
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

 

[Math Amateur]

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 ...

Theorem 1.3.24 reads as follows:
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