- #1
mathmari
Gold Member
MHB
- 5,049
- 7
Hey!
I want to show the following properties of Ackermann's function:
Is this correct?? Could I improve something?? (Wondering)
Could you give me some hints to prove the properties ?? (Wondering)
I want to show the following properties of Ackermann's function:
-
.
-
.
- If
, then .
-
.
-
.
- If
, then .
-
.
- Induction on
.
- Induction on
.
Base case: For we have , by the definition of .
Inductive hypothesis: We assume that it holds for , that means (I.H.x)
Inductive step: We want to show that .
By the definition of and by the property we have .
-
- Induction on
.
Base case: For we have .
Inductive hypothesis: We assume that it holds for , that means (I.H.)
Inductive step: We want to show that .
By the definition we have . By the (I.H.) and the property we have . By the property we have . So, we cocnlude that .
- By the property
we have . So, we have .
But how can we prove this formally??
-
- Induction on
.
Base case: For we have by the property .
Inductive hypothesis: We assume that it holds for , that means (I.H.)
Inductive step: We want to show that .
By the definition of we have . By the (I.H.) we have . By the property we have . By the property we have According to the property , or equivalently . By the property we have . So, .
Is this correct?? Could I improve something?? (Wondering)
Could you give me some hints to prove the properties