- #1
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
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
Last edited by a moderator: