Proving that a relation is well-defined
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I know that in general to show a map $f:Xto Y$ is well-defined, we need to show that for any $xin X$, $f(x)=y_1$ and $f(x)=y_2$ imply that $y_1=y_2$, i.e. each element of $X$ is related to exactly one element of $Y$.
I am reading the proof of theorem 4 on page 56 of Dummit and Foote's Abstract Algebra, 3rd edition. On the second and third lines of the proof, he says we need to show $x^r=x^s$ implies $varphi(x^r)=varphi(x^s)$ in order to prove $varphi$ is well-defined.
How is this logically equivalent to the statement that each element of the domain is related to exactly one element of the range?
I see his argument shows that the map $varphi$ is independent of the specific choice of representative in $langle xrangle$. Is that equivalent to the map being well-defined?
proof-verification logic
add a comment |Â
up vote
2
down vote
favorite
I know that in general to show a map $f:Xto Y$ is well-defined, we need to show that for any $xin X$, $f(x)=y_1$ and $f(x)=y_2$ imply that $y_1=y_2$, i.e. each element of $X$ is related to exactly one element of $Y$.
I am reading the proof of theorem 4 on page 56 of Dummit and Foote's Abstract Algebra, 3rd edition. On the second and third lines of the proof, he says we need to show $x^r=x^s$ implies $varphi(x^r)=varphi(x^s)$ in order to prove $varphi$ is well-defined.
How is this logically equivalent to the statement that each element of the domain is related to exactly one element of the range?
I see his argument shows that the map $varphi$ is independent of the specific choice of representative in $langle xrangle$. Is that equivalent to the map being well-defined?
proof-verification logic
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I know that in general to show a map $f:Xto Y$ is well-defined, we need to show that for any $xin X$, $f(x)=y_1$ and $f(x)=y_2$ imply that $y_1=y_2$, i.e. each element of $X$ is related to exactly one element of $Y$.
I am reading the proof of theorem 4 on page 56 of Dummit and Foote's Abstract Algebra, 3rd edition. On the second and third lines of the proof, he says we need to show $x^r=x^s$ implies $varphi(x^r)=varphi(x^s)$ in order to prove $varphi$ is well-defined.
How is this logically equivalent to the statement that each element of the domain is related to exactly one element of the range?
I see his argument shows that the map $varphi$ is independent of the specific choice of representative in $langle xrangle$. Is that equivalent to the map being well-defined?
proof-verification logic
I know that in general to show a map $f:Xto Y$ is well-defined, we need to show that for any $xin X$, $f(x)=y_1$ and $f(x)=y_2$ imply that $y_1=y_2$, i.e. each element of $X$ is related to exactly one element of $Y$.
I am reading the proof of theorem 4 on page 56 of Dummit and Foote's Abstract Algebra, 3rd edition. On the second and third lines of the proof, he says we need to show $x^r=x^s$ implies $varphi(x^r)=varphi(x^s)$ in order to prove $varphi$ is well-defined.
How is this logically equivalent to the statement that each element of the domain is related to exactly one element of the range?
I see his argument shows that the map $varphi$ is independent of the specific choice of representative in $langle xrangle$. Is that equivalent to the map being well-defined?
proof-verification logic
edited Aug 2 at 21:05


Chickenmancer
2,937621
2,937621
asked Aug 2 at 20:45


kmiyazaki
12610
12610
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
accepted
"I know that in general to show a map f:X→Y is well-defined, we need to show that for any x∈X, f(x)=y1 and f(x)=y2 imply that y1=y2,
That's sort of true. But as a definition for being "well-defined" it isn't .... well, defined.
Let's take a specific example of something that is not well defined:
For and $n = acdot b; n, a,b in mathbb N$ define $f(ab) = a$. That's obviously not well-defined because if we view $20$ as $1*20$ or $4*5$ or $10*2$ we'll get that maybe $f(1*20) = 1$ but $f(4*5) = 4$ and $f(10*2) = 10$ etc.
That just doesnt make any sense.
And that sort of fits your definition.
$f(20) =1$ and $f(20) = 4$ but $1ne 4$ so not well-defined... except... how can we say $f(20) = 4$, how did we decide that that time it'd pop out a $4$ but the next time $f(20) = 1$ it popped out a $1$? Do we just sit and wait for all of them?
Thing is $f$ is defined on representations and not actually on the numbers. SO to show something is well defined we must show if $a*b = n$ and $c*d = n$ are two representations of the some number then we must show that it will always be such that $f(a*b) = a$ and $f(c*d) = c$ that $a = c$.
And, of course, that is bollucks and that is whay it is not well defined.
On the other hand if something is defined on the number then... it's determined for that number. Period. If $f(n) =K$ then .... $f(n)$ will always be $K$ and it can't be anything else. So if something is defined specifically on the number and not the representation, then the issue of being well defined is not a concern.
(The nuance, of course, is recognizing when a definition is innate to the number or to the representation.)
But sometimes a representation definition is okay.
Two examples (one familiar and one probably taken for granted without question): i) Define $sqrtx$ as the number (if any) so that $y ge 0;$ and $y^2 = x$. This is well defined IF we can show that for any $y^2 = x$ and $y_1^2 = x$ and $yge 0$ and $y_1 ge 0$ then $y= y_1$. And we can prove that. (If $y_1 ne y$ then one is smaller than the other; wolog we'll assume $0 le y_1 < y$. So then $y_1^2 < y^2$. So they aren't equal). So it is well defined.
ii) for $b > 0$ define $b^q$ for $q in mathbb Q; q = frac nm; n,m in mathbb Z$ as $(sqrt[m]b)^n$. Well if $q = frac nm = frac rs$ how do we know $(sqrt[m]b)^n= (sqrt[s]b)^r$? For example $q =frac 12 = frac 36$ how do we know that $sqrt b = (sqrt[6]b)^3$
I see his argument shows that the map Æ is independent of the specific choice of representative in ⟨x⟩. Is that equivalent to the map being well-defined?
In a word, yes.
He wants to say $xmapsto y; x^2 mapsto y^2; .... ;x^n-1mapsto y^n-1; emapsto e$. and if he had said that there'd be no question of being well-defined if we assume that all the $x^k; 0le k < n$ are distinct.
But if we can't assume they are distinct and we have a more general: $x^k mapsto y^k$... Well there is the possiblity that $x^k = x^k+r$ but $y^k ne y^k+r$. We have to prove that is not an issue.
Thank you for your very thoughtful answer.
– kmiyazaki
Aug 2 at 22:15
add a comment |Â
up vote
3
down vote
You say that to show a map $f :X to Y$ is well defined we need to show that if $f(x) = y_1$ and $f(x)=y_2$ then $y_1 = y_2$. That is true.
An equivalent formulation is that if $x=y$ then we must have $f(x) = f(y)$.
This is what the proof does. Since $x^k = x^n+k = x^2n+k = cdots$ we need to check that it doesn't matter whether we define $f(x^k)$ to be $y^k$ or $y^n+k$ or ...
add a comment |Â
up vote
0
down vote
In a cyclic group Every element w is a power of x but there will be many choices of the power say r and s .So $w=x^r=x^s$ ,one must show $x^r+k=x^s+k$.
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
"I know that in general to show a map f:X→Y is well-defined, we need to show that for any x∈X, f(x)=y1 and f(x)=y2 imply that y1=y2,
That's sort of true. But as a definition for being "well-defined" it isn't .... well, defined.
Let's take a specific example of something that is not well defined:
For and $n = acdot b; n, a,b in mathbb N$ define $f(ab) = a$. That's obviously not well-defined because if we view $20$ as $1*20$ or $4*5$ or $10*2$ we'll get that maybe $f(1*20) = 1$ but $f(4*5) = 4$ and $f(10*2) = 10$ etc.
That just doesnt make any sense.
And that sort of fits your definition.
$f(20) =1$ and $f(20) = 4$ but $1ne 4$ so not well-defined... except... how can we say $f(20) = 4$, how did we decide that that time it'd pop out a $4$ but the next time $f(20) = 1$ it popped out a $1$? Do we just sit and wait for all of them?
Thing is $f$ is defined on representations and not actually on the numbers. SO to show something is well defined we must show if $a*b = n$ and $c*d = n$ are two representations of the some number then we must show that it will always be such that $f(a*b) = a$ and $f(c*d) = c$ that $a = c$.
And, of course, that is bollucks and that is whay it is not well defined.
On the other hand if something is defined on the number then... it's determined for that number. Period. If $f(n) =K$ then .... $f(n)$ will always be $K$ and it can't be anything else. So if something is defined specifically on the number and not the representation, then the issue of being well defined is not a concern.
(The nuance, of course, is recognizing when a definition is innate to the number or to the representation.)
But sometimes a representation definition is okay.
Two examples (one familiar and one probably taken for granted without question): i) Define $sqrtx$ as the number (if any) so that $y ge 0;$ and $y^2 = x$. This is well defined IF we can show that for any $y^2 = x$ and $y_1^2 = x$ and $yge 0$ and $y_1 ge 0$ then $y= y_1$. And we can prove that. (If $y_1 ne y$ then one is smaller than the other; wolog we'll assume $0 le y_1 < y$. So then $y_1^2 < y^2$. So they aren't equal). So it is well defined.
ii) for $b > 0$ define $b^q$ for $q in mathbb Q; q = frac nm; n,m in mathbb Z$ as $(sqrt[m]b)^n$. Well if $q = frac nm = frac rs$ how do we know $(sqrt[m]b)^n= (sqrt[s]b)^r$? For example $q =frac 12 = frac 36$ how do we know that $sqrt b = (sqrt[6]b)^3$
I see his argument shows that the map Æ is independent of the specific choice of representative in ⟨x⟩. Is that equivalent to the map being well-defined?
In a word, yes.
He wants to say $xmapsto y; x^2 mapsto y^2; .... ;x^n-1mapsto y^n-1; emapsto e$. and if he had said that there'd be no question of being well-defined if we assume that all the $x^k; 0le k < n$ are distinct.
But if we can't assume they are distinct and we have a more general: $x^k mapsto y^k$... Well there is the possiblity that $x^k = x^k+r$ but $y^k ne y^k+r$. We have to prove that is not an issue.
Thank you for your very thoughtful answer.
– kmiyazaki
Aug 2 at 22:15
add a comment |Â
up vote
2
down vote
accepted
"I know that in general to show a map f:X→Y is well-defined, we need to show that for any x∈X, f(x)=y1 and f(x)=y2 imply that y1=y2,
That's sort of true. But as a definition for being "well-defined" it isn't .... well, defined.
Let's take a specific example of something that is not well defined:
For and $n = acdot b; n, a,b in mathbb N$ define $f(ab) = a$. That's obviously not well-defined because if we view $20$ as $1*20$ or $4*5$ or $10*2$ we'll get that maybe $f(1*20) = 1$ but $f(4*5) = 4$ and $f(10*2) = 10$ etc.
That just doesnt make any sense.
And that sort of fits your definition.
$f(20) =1$ and $f(20) = 4$ but $1ne 4$ so not well-defined... except... how can we say $f(20) = 4$, how did we decide that that time it'd pop out a $4$ but the next time $f(20) = 1$ it popped out a $1$? Do we just sit and wait for all of them?
Thing is $f$ is defined on representations and not actually on the numbers. SO to show something is well defined we must show if $a*b = n$ and $c*d = n$ are two representations of the some number then we must show that it will always be such that $f(a*b) = a$ and $f(c*d) = c$ that $a = c$.
And, of course, that is bollucks and that is whay it is not well defined.
On the other hand if something is defined on the number then... it's determined for that number. Period. If $f(n) =K$ then .... $f(n)$ will always be $K$ and it can't be anything else. So if something is defined specifically on the number and not the representation, then the issue of being well defined is not a concern.
(The nuance, of course, is recognizing when a definition is innate to the number or to the representation.)
But sometimes a representation definition is okay.
Two examples (one familiar and one probably taken for granted without question): i) Define $sqrtx$ as the number (if any) so that $y ge 0;$ and $y^2 = x$. This is well defined IF we can show that for any $y^2 = x$ and $y_1^2 = x$ and $yge 0$ and $y_1 ge 0$ then $y= y_1$. And we can prove that. (If $y_1 ne y$ then one is smaller than the other; wolog we'll assume $0 le y_1 < y$. So then $y_1^2 < y^2$. So they aren't equal). So it is well defined.
ii) for $b > 0$ define $b^q$ for $q in mathbb Q; q = frac nm; n,m in mathbb Z$ as $(sqrt[m]b)^n$. Well if $q = frac nm = frac rs$ how do we know $(sqrt[m]b)^n= (sqrt[s]b)^r$? For example $q =frac 12 = frac 36$ how do we know that $sqrt b = (sqrt[6]b)^3$
I see his argument shows that the map Æ is independent of the specific choice of representative in ⟨x⟩. Is that equivalent to the map being well-defined?
In a word, yes.
He wants to say $xmapsto y; x^2 mapsto y^2; .... ;x^n-1mapsto y^n-1; emapsto e$. and if he had said that there'd be no question of being well-defined if we assume that all the $x^k; 0le k < n$ are distinct.
But if we can't assume they are distinct and we have a more general: $x^k mapsto y^k$... Well there is the possiblity that $x^k = x^k+r$ but $y^k ne y^k+r$. We have to prove that is not an issue.
Thank you for your very thoughtful answer.
– kmiyazaki
Aug 2 at 22:15
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
"I know that in general to show a map f:X→Y is well-defined, we need to show that for any x∈X, f(x)=y1 and f(x)=y2 imply that y1=y2,
That's sort of true. But as a definition for being "well-defined" it isn't .... well, defined.
Let's take a specific example of something that is not well defined:
For and $n = acdot b; n, a,b in mathbb N$ define $f(ab) = a$. That's obviously not well-defined because if we view $20$ as $1*20$ or $4*5$ or $10*2$ we'll get that maybe $f(1*20) = 1$ but $f(4*5) = 4$ and $f(10*2) = 10$ etc.
That just doesnt make any sense.
And that sort of fits your definition.
$f(20) =1$ and $f(20) = 4$ but $1ne 4$ so not well-defined... except... how can we say $f(20) = 4$, how did we decide that that time it'd pop out a $4$ but the next time $f(20) = 1$ it popped out a $1$? Do we just sit and wait for all of them?
Thing is $f$ is defined on representations and not actually on the numbers. SO to show something is well defined we must show if $a*b = n$ and $c*d = n$ are two representations of the some number then we must show that it will always be such that $f(a*b) = a$ and $f(c*d) = c$ that $a = c$.
And, of course, that is bollucks and that is whay it is not well defined.
On the other hand if something is defined on the number then... it's determined for that number. Period. If $f(n) =K$ then .... $f(n)$ will always be $K$ and it can't be anything else. So if something is defined specifically on the number and not the representation, then the issue of being well defined is not a concern.
(The nuance, of course, is recognizing when a definition is innate to the number or to the representation.)
But sometimes a representation definition is okay.
Two examples (one familiar and one probably taken for granted without question): i) Define $sqrtx$ as the number (if any) so that $y ge 0;$ and $y^2 = x$. This is well defined IF we can show that for any $y^2 = x$ and $y_1^2 = x$ and $yge 0$ and $y_1 ge 0$ then $y= y_1$. And we can prove that. (If $y_1 ne y$ then one is smaller than the other; wolog we'll assume $0 le y_1 < y$. So then $y_1^2 < y^2$. So they aren't equal). So it is well defined.
ii) for $b > 0$ define $b^q$ for $q in mathbb Q; q = frac nm; n,m in mathbb Z$ as $(sqrt[m]b)^n$. Well if $q = frac nm = frac rs$ how do we know $(sqrt[m]b)^n= (sqrt[s]b)^r$? For example $q =frac 12 = frac 36$ how do we know that $sqrt b = (sqrt[6]b)^3$
I see his argument shows that the map Æ is independent of the specific choice of representative in ⟨x⟩. Is that equivalent to the map being well-defined?
In a word, yes.
He wants to say $xmapsto y; x^2 mapsto y^2; .... ;x^n-1mapsto y^n-1; emapsto e$. and if he had said that there'd be no question of being well-defined if we assume that all the $x^k; 0le k < n$ are distinct.
But if we can't assume they are distinct and we have a more general: $x^k mapsto y^k$... Well there is the possiblity that $x^k = x^k+r$ but $y^k ne y^k+r$. We have to prove that is not an issue.
"I know that in general to show a map f:X→Y is well-defined, we need to show that for any x∈X, f(x)=y1 and f(x)=y2 imply that y1=y2,
That's sort of true. But as a definition for being "well-defined" it isn't .... well, defined.
Let's take a specific example of something that is not well defined:
For and $n = acdot b; n, a,b in mathbb N$ define $f(ab) = a$. That's obviously not well-defined because if we view $20$ as $1*20$ or $4*5$ or $10*2$ we'll get that maybe $f(1*20) = 1$ but $f(4*5) = 4$ and $f(10*2) = 10$ etc.
That just doesnt make any sense.
And that sort of fits your definition.
$f(20) =1$ and $f(20) = 4$ but $1ne 4$ so not well-defined... except... how can we say $f(20) = 4$, how did we decide that that time it'd pop out a $4$ but the next time $f(20) = 1$ it popped out a $1$? Do we just sit and wait for all of them?
Thing is $f$ is defined on representations and not actually on the numbers. SO to show something is well defined we must show if $a*b = n$ and $c*d = n$ are two representations of the some number then we must show that it will always be such that $f(a*b) = a$ and $f(c*d) = c$ that $a = c$.
And, of course, that is bollucks and that is whay it is not well defined.
On the other hand if something is defined on the number then... it's determined for that number. Period. If $f(n) =K$ then .... $f(n)$ will always be $K$ and it can't be anything else. So if something is defined specifically on the number and not the representation, then the issue of being well defined is not a concern.
(The nuance, of course, is recognizing when a definition is innate to the number or to the representation.)
But sometimes a representation definition is okay.
Two examples (one familiar and one probably taken for granted without question): i) Define $sqrtx$ as the number (if any) so that $y ge 0;$ and $y^2 = x$. This is well defined IF we can show that for any $y^2 = x$ and $y_1^2 = x$ and $yge 0$ and $y_1 ge 0$ then $y= y_1$. And we can prove that. (If $y_1 ne y$ then one is smaller than the other; wolog we'll assume $0 le y_1 < y$. So then $y_1^2 < y^2$. So they aren't equal). So it is well defined.
ii) for $b > 0$ define $b^q$ for $q in mathbb Q; q = frac nm; n,m in mathbb Z$ as $(sqrt[m]b)^n$. Well if $q = frac nm = frac rs$ how do we know $(sqrt[m]b)^n= (sqrt[s]b)^r$? For example $q =frac 12 = frac 36$ how do we know that $sqrt b = (sqrt[6]b)^3$
I see his argument shows that the map Æ is independent of the specific choice of representative in ⟨x⟩. Is that equivalent to the map being well-defined?
In a word, yes.
He wants to say $xmapsto y; x^2 mapsto y^2; .... ;x^n-1mapsto y^n-1; emapsto e$. and if he had said that there'd be no question of being well-defined if we assume that all the $x^k; 0le k < n$ are distinct.
But if we can't assume they are distinct and we have a more general: $x^k mapsto y^k$... Well there is the possiblity that $x^k = x^k+r$ but $y^k ne y^k+r$. We have to prove that is not an issue.
edited Aug 2 at 21:30
answered Aug 2 at 21:22
fleablood
60.1k22575
60.1k22575
Thank you for your very thoughtful answer.
– kmiyazaki
Aug 2 at 22:15
add a comment |Â
Thank you for your very thoughtful answer.
– kmiyazaki
Aug 2 at 22:15
Thank you for your very thoughtful answer.
– kmiyazaki
Aug 2 at 22:15
Thank you for your very thoughtful answer.
– kmiyazaki
Aug 2 at 22:15
add a comment |Â
up vote
3
down vote
You say that to show a map $f :X to Y$ is well defined we need to show that if $f(x) = y_1$ and $f(x)=y_2$ then $y_1 = y_2$. That is true.
An equivalent formulation is that if $x=y$ then we must have $f(x) = f(y)$.
This is what the proof does. Since $x^k = x^n+k = x^2n+k = cdots$ we need to check that it doesn't matter whether we define $f(x^k)$ to be $y^k$ or $y^n+k$ or ...
add a comment |Â
up vote
3
down vote
You say that to show a map $f :X to Y$ is well defined we need to show that if $f(x) = y_1$ and $f(x)=y_2$ then $y_1 = y_2$. That is true.
An equivalent formulation is that if $x=y$ then we must have $f(x) = f(y)$.
This is what the proof does. Since $x^k = x^n+k = x^2n+k = cdots$ we need to check that it doesn't matter whether we define $f(x^k)$ to be $y^k$ or $y^n+k$ or ...
add a comment |Â
up vote
3
down vote
up vote
3
down vote
You say that to show a map $f :X to Y$ is well defined we need to show that if $f(x) = y_1$ and $f(x)=y_2$ then $y_1 = y_2$. That is true.
An equivalent formulation is that if $x=y$ then we must have $f(x) = f(y)$.
This is what the proof does. Since $x^k = x^n+k = x^2n+k = cdots$ we need to check that it doesn't matter whether we define $f(x^k)$ to be $y^k$ or $y^n+k$ or ...
You say that to show a map $f :X to Y$ is well defined we need to show that if $f(x) = y_1$ and $f(x)=y_2$ then $y_1 = y_2$. That is true.
An equivalent formulation is that if $x=y$ then we must have $f(x) = f(y)$.
This is what the proof does. Since $x^k = x^n+k = x^2n+k = cdots$ we need to check that it doesn't matter whether we define $f(x^k)$ to be $y^k$ or $y^n+k$ or ...
answered Aug 2 at 20:53


Daniel Mroz
851314
851314
add a comment |Â
add a comment |Â
up vote
0
down vote
In a cyclic group Every element w is a power of x but there will be many choices of the power say r and s .So $w=x^r=x^s$ ,one must show $x^r+k=x^s+k$.
add a comment |Â
up vote
0
down vote
In a cyclic group Every element w is a power of x but there will be many choices of the power say r and s .So $w=x^r=x^s$ ,one must show $x^r+k=x^s+k$.
add a comment |Â
up vote
0
down vote
up vote
0
down vote
In a cyclic group Every element w is a power of x but there will be many choices of the power say r and s .So $w=x^r=x^s$ ,one must show $x^r+k=x^s+k$.
In a cyclic group Every element w is a power of x but there will be many choices of the power say r and s .So $w=x^r=x^s$ ,one must show $x^r+k=x^s+k$.
edited Aug 3 at 0:23
answered Aug 2 at 21:10
StuartMN
1,31349
1,31349
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870473%2fproving-that-a-relation-is-well-defined%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password