ในทฤษฎีการเรียกซ้ำ α ทฤษฎีการเรียกซ้ำเป็นการขยายความของทฤษฎีการเรียกซ้ำไปยังเซตย่อยของลำดับที่ยอมรับได้ เซตที่ยอมรับได้นั้นปิดภายใต้ฟังก์ชัน โดยที่แทนลำดับชั้นของลำดับชั้นที่สร้างได้ ของ Gödel เป็นลำดับที่ยอมรับได้ถ้าเป็นแบบจำลองของทฤษฎีเซต Kripke–Platekในส่วนต่อไปนี้ถือว่าคงที่ ${\displaystyle \alpha }$${\displaystyle \Sigma _{1}(L_{\alpha })}$${\displaystyle L_{\xi }}$${\displaystyle \alpha }$${\displaystyle L_{\alpha }}$${\displaystyle \alpha }$

วัตถุที่ศึกษาในทฤษฎีการเรียกซ้ำคือเซตย่อยของ โดยเซตย่อยเหล่านี้มีคุณสมบัติบางประการดังนี้: ${\displaystyle \alpha }$${\displaystyle \alpha }$

• เซตจะเรียกว่าสามารถแจงนับได้แบบเรียกซ้ำได้ก็ต่อเมื่อสามารถกำหนดได้เหนือโดยอาจมีพารามิเตอร์จากในคำจำกัดความ^{[ 1 ]}${\displaystyle A\subseteq \alpha }$${\displaystyle \alpha }$${\displaystyle \Sigma _{1}}$${\displaystyle L_{\alpha }}$${\displaystyle L_{\alpha }}$
• เซต A เรียกว่า เซต แบบเรียกซ้ำ (recursive set ) ถ้าทั้ง A และ( ส่วนเติมเต็มสัมพัทธ์ ของมัน ใน) เป็น เซตที่สามารถแจงนับแบบ เรียกซ้ำได้ (recursively-enumerable set) เป็นที่น่าสังเกตว่าเซตแบบเรียกซ้ำเป็นสมาชิกของตามนิยามของ${\displaystyle \alpha }$${\displaystyle \alpha \setminus A}$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle L_{\alpha +1}}$${\displaystyle L}$
• สมาชิกของเรียกว่า-finiteและมีบทบาทคล้ายกับจำนวนจำกัดในทฤษฎีการเรียกซ้ำแบบคลาสสิก${\displaystyle L_{\alpha }}$${\displaystyle \alpha }$
• สมาชิกของเรียกว่า-arithmetic ^{[ 2 ]}${\displaystyle L_{\alpha +1}}$${\displaystyle \alpha }$

นอกจากนี้ยังมีคำจำกัดความที่คล้ายกันสำหรับฟังก์ชันที่แมปไปยัง: ^{[ 3 ]}${\displaystyle \alpha }$${\displaystyle \alpha }$

• ฟังก์ชันบางส่วนจากถึงสามารถแจงนับได้แบบเรียกซ้ำหรือเรียกซ้ำแบบบางส่วน^{[ 4 ]}ก็ต่อเมื่อกราฟของมัน สามารถกำหนด ได้บน${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \Sigma _{1}}$${\displaystyle (L_{\alpha },\in )}$
• ฟังก์ชันบางส่วนจากไปเป็น ฟังก์ชัน แบบเรียกซ้ำได้ก็ต่อเมื่อกราฟของฟังก์ชันนั้นสามารถนิยามได้ บนเช่นเดียวกับในทฤษฎีการเรียกซ้ำแบบคลาสสิกฟังก์ชันที่สามารถแจงนับได้แบบเรียกซ้ำทั้งหมดจะเป็น ฟังก์ชัน แบบเรียกซ้ำได้${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \Delta _{1}}$${\displaystyle (L_{\alpha },\in )}$${\displaystyle \alpha }$${\displaystyle f:\alpha \rightarrow \alpha }$${\displaystyle \alpha }$
• นอกจากนี้ ฟังก์ชันบางส่วนจากไปจะเป็นฟังก์ชันเชิงเลขคณิตก็ต่อเมื่อมีค่าบางค่าที่ทำให้กราฟของฟังก์ชันนั้น สามารถนิยาม ได้บน${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle n\in \omega }$${\displaystyle \Sigma _{n}}$${\displaystyle (L_{\alpha },\in )}$

สามารถเชื่อมโยงความสัมพันธ์เพิ่มเติมระหว่างทฤษฎีการเรียกซ้ำและทฤษฎีการเรียกซ้ำ α ได้ แม้ว่าอาจยังไม่มีการเขียนคำจำกัดความที่ชัดเจนเพื่อทำให้ความสัมพันธ์เหล่านั้นเป็นทางการก็ตาม:

• ฟังก์ชันที่กำหนดได้จะมีบทบาทคล้ายกับ ฟังก์ชันเรียกซ้ำ แบบดั้งเดิม^{[ 3 ]}${\displaystyle \Delta _{0}}$${\displaystyle (L_{\alpha },\in )}$

เรากล่าวว่า R เป็นกระบวนการลดรูป (reduction procedure) ถ้า R สามารถแจงนับได้แบบเวียนซ้ำ (recursively enumerable) และสมาชิกทุกตัวของ R อยู่ในรูปแบบที่H , J , Kเป็นจำนวนจำกัดอัลฟา (α-finite) ทั้งหมด ${\displaystyle \alpha }$${\displaystyle \langle H,J,K\rangle }$

กล่าวได้ว่าA เป็น α-recursive ใน Bหากมีขั้นตอนการลดรูปอยู่ซึ่งเป็นไปตามเงื่อนไขดังต่อไปนี้: ${\displaystyle R_{0},R_{1}}$

${\displaystyle K\subseteq A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{0}\wedge H\subseteq B\wedge J\subseteq \alpha /B],}$

${\displaystyle K\subseteq \alpha /A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{1}\wedge H\subseteq B\wedge J\subseteq \alpha /B].}$

ถ้าAเป็นฟังก์ชันเรียกซ้ำในBจะเขียนได้ว่า ตามนิยามนี้Aเป็นฟังก์ชันเรียกซ้ำใน( เซตว่าง ) ก็ต่อเมื่อAเป็นฟังก์ชันเรียกซ้ำ อย่างไรก็ตาม การที่ A เป็นฟังก์ชันเรียกซ้ำใน B ไม่ได้หมายความว่า A เป็นฟังก์ชันเรียกซ้ำใน B เสมอไป ${\displaystyle \scriptstyle A\leq _{\alpha }B}$${\displaystyle \scriptstyle \varnothing }$${\displaystyle \Sigma _{1}(L_{\alpha }[B])}$

เรากล่าวว่าAเป็นเมทริกซ์ปกติ ถ้าหรือกล่าวอีกนัยหนึ่งคือ ถ้าทุกส่วนเริ่มต้นของAเป็นเมทริกซ์ α-finite ${\displaystyle \forall \beta \in \alpha :A\cap \beta \in L_{\alpha }}$

ทฤษฎีบทการแยกของ Shore : ให้ A เป็นเซตที่แจงนับได้แบบเวียนซ้ำและเป็นเซตปกติ จะมีเซตที่แจงนับได้แบบเวียนซ้ำ อยู่ เช่นนั้น${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle B_{0},B_{1}}$${\displaystyle A=B_{0}\cup B_{1}\wedge B_{0}\cap B_{1}=\varnothing \wedge A\not \leq _{\alpha }B_{i}(i<2).}$

ทฤษฎีบทความหนาแน่นของ Shore: ให้AและCเป็นเซตที่นับได้แบบเวียนเกิด α-ปกติ โดยที่แล้วจะมีเซตที่นับได้แบบเวียนเกิด α-ปกติBอยู่จริง โดยที่${\displaystyle \scriptstyle A<_{\alpha }C}$${\displaystyle \scriptstyle A<_{\alpha }B<_{\alpha }C}$

บาร์ไวส์ได้พิสูจน์แล้วว่าเซตที่กำหนดบนคือเซตที่กำหนดบนโดยที่หมายถึงลำดับถัดไปที่ยอมรับได้ข้างต้นและมาจากลำดับชั้นของเลวี^{[ 5 ]}${\displaystyle \Sigma _{1}}$${\displaystyle L_{\อัลฟา ^{+}}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle L_{\alpha }}$${\displaystyle \alpha ^{+}}$${\displaystyle \alpha }$${\displaystyle \Sigma }$

มีการขยายความสามารถในการคำนวณลิมิตไปยังฟังก์ชัน บางส่วน ^{[ 6 ]}${\displaystyle \alpha \to \alpha }$

มีการตีความการคำนวณของ การเรียกซ้ำแบบ โดยใช้ " เครื่องจักรทัวริงแบบ ที่มีเทปสองสัญลักษณ์ความยาวซึ่งในขั้นตอนการคำนวณจำกัดจะใช้ค่าต่ำสุดของเนื้อหาเซลล์ สถานะ และตำแหน่งหัว สำหรับค่าที่ยอมรับได้เซตจะเป็นแบบเรียกซ้ำแบบ ก็ต่อเมื่อสามารถคำนวณได้ด้วยเครื่องจักรทัวริงแบบและจะเป็นแบบเรียกซ้ำที่สามารถแจงนับได้แบบ ก็ต่อเมื่อเป็นช่วงของฟังก์ชันที่สามารถคำนวณได้ด้วยเครื่องจักรทัวริงแบบ^{[ 7 ]}${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle A\subseteq \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle A}$${\displaystyle \alpha }$

ปัญหาในทฤษฎี α-recursion ซึ่งยังไม่ได้รับการแก้ไข (ณ ปี 2019) คือสมมติฐานการฝังตัวสำหรับลำดับที่ยอมรับได้ ซึ่งก็คือว่าสำหรับลำดับที่ยอมรับได้ทั้งหมดออโตมอร์ฟิซึมของระดับการแจงนับ - จะฝังตัวลงในออโตมอร์ฟิซึมของระดับการแจงนับ - หรือ ไม่ ^{[ 8 ]}${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$

ผลลัพธ์บางอย่างในทฤษฎีการเรียกซ้ำสามารถแปลเป็นผลลัพธ์ที่คล้ายกันเกี่ยวกับเลขคณิตอันดับสองได้ เนื่องมาจากความสัมพันธ์ที่มีกับลำดับชั้นการวิเคราะห์แบบแตกแขนง ซึ่งเป็นอนาล็อกของภาษาเลขคณิตอันดับสองที่ประกอบด้วยเซตของจำนวนเต็ม^{[ 9 ]}${\displaystyle \alpha }$${\displaystyle L}$${\displaystyle L}$

ในความเป็นจริง เมื่อพิจารณา เฉพาะ ตรรกะลำดับแรกเท่านั้น ความสอดคล้องกันอาจใกล้เคียงกันมากพอที่สำหรับผลลัพธ์บางอย่างบนลำดับ ชั้น ทางเลขคณิตและลำดับชั้นของ Lévy สามารถใช้แทนกันได้ ตัวอย่างเช่น เซตของจำนวนธรรมชาติสามารถกำหนดได้ด้วยสูตรก็ต่อเมื่อสามารถกำหนดได้ด้วยสูตรบน โดยที่เป็นระดับของลำดับชั้นของ Lévy ^{[ 10 ]}โดยทั่วไปแล้ว ความสามารถในการกำหนดเซตย่อยของ ω บนด้วยสูตรจะสอดคล้องกับความสามารถในการกำหนดทางเลขคณิตโดยใช้สูตร^{[ 11 ]}${\displaystyle L_{\omega }}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Sigma _{1}}$${\displaystyle L_{\omega }}$${\displaystyle \Sigma _{1}}$${\displaystyle L_{\omega }}$${\displaystyle \Sigma _{n}}$${\displaystyle \Sigma _{n}^{0}}$