Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: logic

Topic: Induction

Sara Garcia (Apr 04 2022 at 12:02):

What does this function do defined on the set of natural numbers :

f(a,0) = a , f (a,s(n)) = s(f(p(a),n))

where is the functions s and p are the successor and predecessor functions respectively .

the function seems to give the max based of couple of trials , but how do we formally prove this for all N ? can we construct such a function using primitive language ?

Graham Manuell (Apr 04 2022 at 13:43):

What is f(0,s(n))?

Reid Barton (Apr 04 2022 at 13:48):

From context, probably p(0) = 0.

Graham Manuell (Apr 04 2022 at 14:20):

Okay. I suggest separating the a = 0 and a = s(m) cases. Then it should be easy to prove this is max by induction.

Sara Garcia (Apr 04 2022 at 17:31):

Graham Manuell said:

Okay. I suggest separating the a = 0 and a = s(m) cases. Then it should be easy to prove this is max by induction.

Thanks for the answer, but can we describe the maximum function using only the definition of addition subtraction and multiplication ?

Todd Trimble (Apr 04 2022 at 17:50):

Not using ordinary subtraction (since max is not a polynomial function), but there is such a thing as truncated subtraction given by $a \stackrel{\cdot}{-} b = \max\{0, a-b\}$. Here one has $\max\{a, b\} = b + (a \stackrel{\cdot}{-} b)$. Since this is the category theory zulip, it's worth pointing out that this truncated subtraction is the internal hom for the poset $([0, \infty], \geq)$ equipped with $+$ as the tensor product, one of the main characters of Lawvere's paper Metric Spaces, Closed Categories, and Generalized Logic (hope I'm remembering the title correctly).