What really algorithm are? Can we define algorithm as functions or in terms of set theory Can we reconvert proof using algorithm in set theory concept.For example,
Theorem: A function defined on closed and bounded interval [a, b] be continuous. And if f(a).f(b)<0 then there exist c in (a, b) such that f(c) = 0 Proof: Outline of proof using an algorithmic approach is: wee take midpoint d of [a, b] if f(d) = 0 then we are done. If not we look at sign of f(d) and define [a1, b1] such that one of a1 or b1 is d and such that f(a1)f(b1)<0 and again we look at midpoint and procced as above. And in the end we use nested interval theorem if process does not terminate. I think you get outline of proof.
But question: Is it possible to write same proof in set theory terms?(And there is proof of theorem using connected metric space concept which does not use algorithm but am just consult with above proof)
Summary of Questions: 1. What is proof by recursion? 2. Can every theorem which is proved by a 'proof by recursion' be proved without 'proof by recursion'?
Recursion is a powerful, well-defined concept in set theory. The Recursion Theorem (or its generalization) can be applied whenever a deterministic recursive algorithm can be used.
Here is a proof sketch of an equivalent formulation of the Intermediate Value Theorem, using recursion in the set theoretic context.
Theorem
Let $f : [a, b] \to \mathbb R$ be a continuous function, where $a \le b$ is a pair of real numbers such that $f(a) \cdot f(b) \le 0$. Then, there exists a $c \in [a, b]$ such that $f(c) = 0$.
Proof Sketch
We shall first represent the midpoint procedure as a set-theoretic function $g$, whose domain and range shall be the set $S$ of closed subintervals of $[a, b]$. For instance, $g : S \to S$ can be defined as:
$$ g\left([p, q]\right) = \begin{cases} \left[ p, \frac{p+q}{2} \right] & \text{if}\mathrel{} f(p) \cdot f\left(\frac{p+q}{2}\right) \le 0 \\ \left[ \frac{p+q}{2}, q \right] & \text{otherwise} \end{cases} $$
By invoking the recursion theorem on $g$, we obtain a unique function $G : \mathbb N \to S$ such that $G(0) = [a, b]$ and that $G(n+1) = g\bigl(G(n)\bigr)$.
It can be verified that $\langle G(0), G(1), G(2) \ldots \rangle$ is an infinite sequence of closed, nested intervals whose lower and upper bounds converge to a single point $c \in [a, b]$.
It can further be verified (by properties of $g$ and by continuity of $f$) that $f(c) \cdot f(c) \le 0$, whence $f(c) = 0$.
Remark
A small generalization—the Axiom of Dependent Choice—can be used to obtain a proof of the intermediate value theorem from a nondeterministic recursive algorithm.
To do so, one can represent the nondeterministic algorithm as a relation $R$ on the nonempty set $\big\{ [p, q] \subseteq [a, b] \bigm| f(p) \cdot f(q) \le 0 \bigr\}$.
For instance, suppose we only cared that each subsequent interval was a subinterval whose size was half or less:
$$ [p, q] \mathrel R [s, t] \Longleftrightarrow [s, t] \subseteq [p, q] \mathrel{}\text{and}\mathrel{} t-s \le \frac{q-p}{2} $$
Then, it is straightforward to verify that $R$ is an entire relation, whence the axiom of dependent choice can be used to obtain an infinite sequence $$ [a_1, b_1] \mathrel R [a_2, b_2] \mathrel R [a_3, b_3] \mathrel R [a_4, b_4] \mathrel R \ldots $$ with the required properties.