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