I Is the negation of the statement in the book correct too?

[member 587159]

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

Thanks in advance

 

[mfb]

What is s?

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

 

[member 587159]

What is s?

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

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

 

[mfb]

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.

 

[member 587159]

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.

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

 

[mfb]

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

 

[member 587159]

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

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

 

[mfb]

That's what I said.

 

[member 587159]

That's what I said.

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

 

[mfb]

So they are equivalent?

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

 

[member 587159]

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

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.

 

[fresh_42]

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.

Try this reference:
https://fr.wikipedia.org/wiki/Négation_logique#Utilisation_en_logique_classique