Is a function defined by an algorithme that must end rigourously defined?

72 Views Asked by At

I wonder if it is commonly agreed by the mathematics community that a function that is describe by an algortihme that is shown to be always solvable in a finite amount of step is correctly defined.

As for an example : If say I want to prove that a finite list of real numbers must have a minimum; may I state that I can sort the list by some algorithme that I would show to be correctly solvable in finite amount of step and then must that first element of the be list the minimum (and since there is a minimum then it must exist).

Or rather : $\exists a / a= Min(L)$ because

$Min(L) = x_0 / (\ (x_0, \dots,x_n) = Sort(L)\ )$ ?

I'm sorry if my question is dumb, I'm far from a professional mathematician. Anyway thank you for your time.

1

There are 1 best solutions below

1
On BEST ANSWER

This is perfectly valid, and many common function definitions can be viewed as simple algorithms.

Note that defining $f(x_1, x_2, \dots, x_n)$ as "the first element in the output of bubblesort applied to the sequence $(x_1, x_2, \dots, x_n)$" does not, in itself, prove that $(x_1, x_2, \dots, x_n)$ has a minimum. Presumably you have a definition of the minimum (e.g., some number $x$ such that $x \le x_i$ for all $i$, and $x = x_i$ for at least one $i$). You should prove the correctness of your algorithm: that the output satisfies the definition. Only then have you shown that every sequence $(x_1, x_2, \dots, x_n)$ has a minimum.

You should also watch out for arbitrary choices. For example, suppose you try to define the minimum of the set $\{x_1, x_2, \dots, x_n\}$ by applying a sorting algorithm to the sequence $(x_1, x_2, \dots, x_n)$. Then you must show that this function is well-defined by showing that it produces the same output, no matter how you put the elements of the set into a sequence.