# I Proof by contradiction

Tags:
1. Sep 17, 2016

### Math_QED

Hello.

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 have instead:

$(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...?

Last edited: Sep 17, 2016
2. Sep 17, 2016

### Staff: Mentor

What is s?

Something went wrong with formatting in the second part of the post.

3. Sep 17, 2016

### Math_QED

Trying to fix it, I don't find the mistake:

s is a function $\mathbb{N} \rightarrow \mathbb{N}$ that is defined by the Peano Postulates.

EDIT: fixed the Latex

4. Sep 17, 2016

### Staff: Mentor

Okay, so we get f(1)=e, f(2)=k(e), f(3)=k(k(e)) and so on.

Replaying n by r and y by t doesn't change anything.

5. Sep 17, 2016

### Math_QED

Yes but that's not the question. They just do that because they used (n,y) previously and otherwise it could cause confusion.

6. Sep 17, 2016

### Staff: Mentor

You asked if they are equivalent?
The negation looks right.

7. Sep 17, 2016

### Math_QED

Yes, is the book's negation correct? And mine?

8. Sep 17, 2016

### Staff: Mentor

That's what I said.

9. Sep 17, 2016

### Math_QED

So they are equivalent? How can I verify that other than just thinking about it? Are there rules for?

10. Sep 17, 2016

### Staff: Mentor

Again: yes.
Wikipedia has a list of rules for negation.

11. Sep 17, 2016

### Math_QED

I don't see anything about negations involving quantifiers. But I guess it's obvious, although I'm somewhat curious how one should prove these things, if this is even possible. Maybe they are axioms.

12. Sep 20, 2016