Hello.(adsbygoogle = window.adsbygoogle || []).push({});

I'm currently studying about natural numbers and I encountered the theorem of definition by recursion:

This states:

Let ##H## be a set, let ##e \in H## and let ##k: H \rightarrow H## be a function. Then there is a unique function ##f: \mathbb{N} \rightarrow H## such that ##f(1) = e## and ##f \circ s = k \circ f##

I will not post the entire proof here, as it is a quite long proof, but the part where I have a question about.

In the proof, they prove that:

If ##(n,y) \in f## and ##(n,y) \neq (1,e)##, then there is some ##(m,u) \in f## such that ##(n,y) = (s(m), k(u))##

They do this by deriving a contradiction. I quote the book:

Suppose to the contrary that there is some ##(r,t) \in f## such that ##(r,t) \neq (1,e)##, and that there is no ##(m,u) \in f## such that ##(r,t) = (s(m),k(u))##

Writing out the statement we want to proof with symbols, we get:

##(n,y) \in f \land (n,y) \neq (1,e) \Rightarrow \exists (m,u) \in f : (n,y) = (s(m), k(u))##

I think, if we negate this (to start with a contradiction), we should haveinstead:

##(n,y) \in f \land (n,y) \neq (1,e) \land \forall (m,u) \in f : (n,y) \neq (s(m), k(u))##

and thus, since the book recalls ##(n,y) = (r,t)## since ##(n, y)## was used previously:

##(r,t) \in f \land (r,t) \neq (1,e) \Rightarrow \forall (m,u) \in f : (r,t) \neq (s(m), k(u))##

Is the statement in the book correct too and are both logically equivalent or...?

Thanks in advance

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# I Proof by contradiction

Have something to add?

Draft saved
Draft deleted

Loading...

Similar Threads - Proof contradiction | Date |
---|---|

I Contradiction in an absolute value property? | Apr 10, 2017 |

A Circular reasoning and proof by Contradiction | Sep 29, 2016 |

I Can you make the induction step by contradiction? | Jun 19, 2016 |

Proving: Proof by Contradiction | Jan 16, 2013 |

Proof by contradiction for statement of the form P->(Q and R) | Jul 18, 2012 |

**Physics Forums - The Fusion of Science and Community**