Jelaskan Rekursi dalam matematika dari Rekursi

Himpunan yang didefinisikan secara rekursif

Contoh kanonikal dari himpunan yang didefinisikan secara rekursif yaitu diberikan oleh bilangan asli:

jika n ada dalam , maka n + 1 ada dalam

Himpunan dari bilangan asli adalah himpunan terkecil yang memenuhi dua properti sebelumnya.

Contoh: himpunan dari proposisi benar terjangkau

Contoh menarik lainnya adalah himpunan dari semua proposisi "benar terjangkau" dalam suatu sistem aksioma.

Jika suatu proposisi adalah sebuah aksioma, maka ia adalah suatu proposisi benar terjangkau.

Jika suatu proposisi dapat dihasilkan dari proposisi benar terjangkau dengan menggunakan aturan-aturan inferensi, maka ia adalah proposisi benar terjangkau.

Himpunan dari proposisi benar-terjangkau adalah himpunan terkecil dari proposisi yang memenuhi kondisi tersebut.

Himpunan ini disebut 'proposisi benar terjangkau' karena dalam pendekatan non-konstruktif terhadap fondasi matematika, himpunan dari proposisi benar bisa lebih besar daripada himpunan yang dibangun secara rekursif dari aksioma-aksioma dan aturan-aturan inferensi.

Lihat juga Teorema ketaklengkapan Godel.