Mixing
How do we define functions on quotient sets?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Let $X$ be a set and $sim$ an equivalence relation on $X$. I know how to define the quotient set
$$ X/sim := [x] in mathcalP(X) mid x in X , $$
but I'm a bit confused about how exactly to define a function on the quotient set. I have seen it done by writing something like
$$ beginalignphicolon X/sim &to Y, \ [x] &mapsto phi([x]), endalign$$
for some set $Y$, where the definition of $phi$ makes use of the representative $x$ explicitly in some way, say $phi([x]) := psi(x)$ for some $psicolon X to Y$. So assume that we have shown that the function is well-defined.
What exactly do we mean when we write $[x]$ in the definition above? We need to use the representative to find the image of the equivalence class under $phi$, but how do we choose the representative? Do we need to appeal to the axiom of choice?
Also, I thought there might at least be cases in which we didn't need choice, e.g. if $X$ is well-ordered. We would then construct a set of representatives (without choice), map each equivalence class to its chosen representative and use that to define $phi$. But the function is not defined in terms of the representatives, but in terms of the equivalence classes themselves, so we presumably still need to show that the image of some equivalence class under $phi$ is independent of the choice of representative. After all, our choice of representative is not part of the function. And it seems like that still requires choosing a generic element, but I'm very unsure whether that requires choice or not.
In general, I think I'm very confused about when we are making a choice that requires the axiom
equivalence-relations axiom-of-choice quotient-spaces
edited Jul 17 at 23:04
Michael Hardy
204k23186462
asked Jul 17 at 21:42
Danny Hansen
464
add a comment |Â
up vote
3
down vote
favorite
Let $X$ be a set and $sim$ an equivalence relation on $X$. I know how to define the quotient set
$$ X/sim := [x] in mathcalP(X) mid x in X , $$
but I'm a bit confused about how exactly to define a function on the quotient set. I have seen it done by writing something like
$$ beginalignphicolon X/sim &to Y, \ [x] &mapsto phi([x]), endalign$$
for some set $Y$, where the definition of $phi$ makes use of the representative $x$ explicitly in some way, say $phi([x]) := psi(x)$ for some $psicolon X to Y$. So assume that we have shown that the function is well-defined.
What exactly do we mean when we write $[x]$ in the definition above? We need to use the representative to find the image of the equivalence class under $phi$, but how do we choose the representative? Do we need to appeal to the axiom of choice?
Also, I thought there might at least be cases in which we didn't need choice, e.g. if $X$ is well-ordered. We would then construct a set of representatives (without choice), map each equivalence class to its chosen representative and use that to define $phi$. But the function is not defined in terms of the representatives, but in terms of the equivalence classes themselves, so we presumably still need to show that the image of some equivalence class under $phi$ is independent of the choice of representative. After all, our choice of representative is not part of the function. And it seems like that still requires choosing a generic element, but I'm very unsure whether that requires choice or not.
In general, I think I'm very confused about when we are making a choice that requires the axiom
equivalence-relations axiom-of-choice quotient-spaces
edited Jul 17 at 23:04
Michael Hardy
204k23186462
asked Jul 17 at 21:42
Danny Hansen
464
$[x]$ denotes the equivalence class of the element $x$. So, $[x] = y : x sim y $
– gd1035
Jul 17 at 21:45
Closely related: math.stackexchange.com/questions/2110908/…
– Eric Wofsey
Jul 17 at 22:06
1
It appears that you noticed that writing X/sim would result in too much space between $X$ and $sim,$ so you manually added some negative space. But the natural way to remedy the problem is to write X/sim, so that you see $X/sim.$ A moment's thought may tell you why it works that way.
– Michael Hardy
Jul 17 at 23:06
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Let $X$ be a set and $sim$ an equivalence relation on $X$. I know how to define the quotient set
$$ X/sim := [x] in mathcalP(X) mid x in X , $$
but I'm a bit confused about how exactly to define a function on the quotient set. I have seen it done by writing something like
$$ beginalignphicolon X/sim &to Y, \ [x] &mapsto phi([x]), endalign$$
for some set $Y$, where the definition of $phi$ makes use of the representative $x$ explicitly in some way, say $phi([x]) := psi(x)$ for some $psicolon X to Y$. So assume that we have shown that the function is well-defined.
What exactly do we mean when we write $[x]$ in the definition above? We need to use the representative to find the image of the equivalence class under $phi$, but how do we choose the representative? Do we need to appeal to the axiom of choice?
Also, I thought there might at least be cases in which we didn't need choice, e.g. if $X$ is well-ordered. We would then construct a set of representatives (without choice), map each equivalence class to its chosen representative and use that to define $phi$. But the function is not defined in terms of the representatives, but in terms of the equivalence classes themselves, so we presumably still need to show that the image of some equivalence class under $phi$ is independent of the choice of representative. After all, our choice of representative is not part of the function. And it seems like that still requires choosing a generic element, but I'm very unsure whether that requires choice or not.
In general, I think I'm very confused about when we are making a choice that requires the axiom
equivalence-relations axiom-of-choice quotient-spaces
edited Jul 17 at 23:04
Michael Hardy
204k23186462
asked Jul 17 at 21:42
Danny Hansen
464
Let $X$ be a set and $sim$ an equivalence relation on $X$. I know how to define the quotient set
$$ X/sim := [x] in mathcalP(X) mid x in X , $$
but I'm a bit confused about how exactly to define a function on the quotient set. I have seen it done by writing something like
$$ beginalignphicolon X/sim &to Y, \ [x] &mapsto phi([x]), endalign$$
for some set $Y$, where the definition of $phi$ makes use of the representative $x$ explicitly in some way, say $phi([x]) := psi(x)$ for some $psicolon X to Y$. So assume that we have shown that the function is well-defined.
What exactly do we mean when we write $[x]$ in the definition above? We need to use the representative to find the image of the equivalence class under $phi$, but how do we choose the representative? Do we need to appeal to the axiom of choice?
Also, I thought there might at least be cases in which we didn't need choice, e.g. if $X$ is well-ordered. We would then construct a set of representatives (without choice), map each equivalence class to its chosen representative and use that to define $phi$. But the function is not defined in terms of the representatives, but in terms of the equivalence classes themselves, so we presumably still need to show that the image of some equivalence class under $phi$ is independent of the choice of representative. After all, our choice of representative is not part of the function. And it seems like that still requires choosing a generic element, but I'm very unsure whether that requires choice or not.
In general, I think I'm very confused about when we are making a choice that requires the axiom
equivalence-relations axiom-of-choice quotient-spaces
edited Jul 17 at 23:04
Michael Hardy
204k23186462
asked Jul 17 at 21:42
Danny Hansen
464
edited Jul 17 at 23:04
Michael Hardy
204k23186462
edited Jul 17 at 23:04
Michael Hardy
204k23186462
edited Jul 17 at 23:04
Michael Hardy
204k23186462
204k23186462
asked Jul 17 at 21:42
Danny Hansen
464
asked Jul 17 at 21:42
Danny Hansen
464
asked Jul 17 at 21:42
Danny Hansen
464
464
$[x]$ denotes the equivalence class of the element $x$. So, $[x] = y : x sim y $
– gd1035
Jul 17 at 21:45
Closely related: math.stackexchange.com/questions/2110908/…
– Eric Wofsey
Jul 17 at 22:06
1
It appears that you noticed that writing X/sim would result in too much space between $X$ and $sim,$ so you manually added some negative space. But the natural way to remedy the problem is to write X/sim, so that you see $X/sim.$ A moment's thought may tell you why it works that way.
– Michael Hardy
Jul 17 at 23:06
add a comment |Â
$[x]$ denotes the equivalence class of the element $x$. So, $[x] = y : x sim y $
– gd1035
Jul 17 at 21:45
Closely related: math.stackexchange.com/questions/2110908/…
– Eric Wofsey
Jul 17 at 22:06
1
It appears that you noticed that writing X/sim would result in too much space between $X$ and $sim,$ so you manually added some negative space. But the natural way to remedy the problem is to write X/sim, so that you see $X/sim.$ A moment's thought may tell you why it works that way.
– Michael Hardy
Jul 17 at 23:06
$[x]$ denotes the equivalence class of the element $x$. So, $[x] = y : x sim y $
– gd1035
Jul 17 at 21:45
$[x]$ denotes the equivalence class of the element $x$. So, $[x] = y : x sim y $
– gd1035
Jul 17 at 21:45
Closely related: math.stackexchange.com/questions/2110908/…
– Eric Wofsey
Jul 17 at 22:06
Closely related: math.stackexchange.com/questions/2110908/…
– Eric Wofsey
Jul 17 at 22:06
1
1
It appears that you noticed that writing X/sim would result in too much space between $X$ and $sim,$ so you manually added some negative space. But the natural way to remedy the problem is to write X/sim, so that you see $X/sim.$ A moment's thought may tell you why it works that way.
– Michael Hardy
Jul 17 at 23:06
It appears that you noticed that writing X/sim would result in too much space between $X$ and $sim,$ so you manually added some negative space. But the natural way to remedy the problem is to write X/sim, so that you see $X/sim.$ A moment's thought may tell you why it works that way.
– Michael Hardy
Jul 17 at 23:06
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
When you write $[x]$, this is a very explicit and very concrete subset of $X$. So when you want to define $phi([x])$, you really want to define it for the equivalence class.
This is fine, and no use of the axiom of choice is needed. However, if your definition of $phi([x])$ somehow depends on $x$, then you need to verify that for $x'in[x]$, the definition yields the same result. This is what it means to be well-defined.
So for example, $phi([x])=[x]$ does not depend on $[x]$, it's just the identity function, and it's easier to see as $phi(A)=A$ for $Ain X/sim$, for that matter. But something like $[x]+[y]=[x+y]$, certainly depends on the values of $x$ and $y$, and you want to show that $+$ as defined on $X$ behaves nicely with respect to $sim$. This requires, in the majority of cases, no choice. Since you only need to work one or two equivalence classes at a time, so you're only choosing two members from a non-empty set. No choice is used for that.
Using representatives is a tricky thing, though. While on its own, the existence of a system of representative from an arbitrary equivalence relation is the enough to prove the full axiom of choice, it is worth noting that you already assumed that $phi$ is well-defined. In that case $psi(x)$ is literally defined as $phi([x])$, which is the other way around and no choice was used for that. Of course, I suspect that you meant that first you chose representatives, then you had the function $psi$ and then you defined $phi([x])=psi(x')$, where $x'$ is the representative for $[x]$. But if that's not the case, and you first had $phi$, and only then defined $psi$, then choice was not used at all.
answered Jul 17 at 21:59
Asaf Karagila♦
292k31403733
1
I found an old answer of yours that clarify why if you work with finite number of equivalence classes at a time you don't need choice: math.stackexchange.com/questions/85153/…
– Holo
Jul 17 at 22:15
I think your suspicion is correct. I mean to say something like: Take a function $psi$ on $X$, choose a representative $x'$ for $[x]$, and define $phi([x]) = psi(x')$. (I really mean that $phi$ makes explicit reference to representatives, like in your example with addition, but I think defining $phi$ in terms of $psi$ captures what I mean.) But to be sure: In the opposite case no choice is used, but in this case, since I am choosing a representative of a single equivalence class, choice is not used here either? Just want to make sure, since you seem to be emphasising the opposite case.
– Danny Hansen
Jul 18 at 12:59
1
@Danny: If you define $phi$ globally by first choosing representatives, choice is necessary. If you define $phi([x])$ in terms of $x$, then you need to argue that indeed this definition does not depend on the choice of $x$. In practice, these definitions only depend on $x$ (or some other finitely many representatives), and then choice is not needed since ZF lets us choose from finitely many non-empty sets at the same time. If you define $psi$ in terms of $phi$, then no choice is necessary, was my point.
– Asaf Karagila♦
Jul 18 at 13:02
add a comment |Â
up vote
3
down vote
The axiom of choice is not needed here (assuming you can define your function $psi:Xto Y$ without it and the resulting function $phi$ is well-defined). Explicitly, define $$S=([x],psi(x)):xin Xsubseteq X/simtimes Y.$$
This is a perfectly well-defined set of ordered pairs and no choice is needed to define it. If this set is actually the graph of a function (in other words, for every element $ain X/sim times Y$ there exists a unique $bin Y$ such that $(a,b)in S$), then that function is the function $phi$ you are trying to define.
So to check that we have defined a function, we just need to check that $S$ is the graph of a function. For any $ain X/sim$, there exists $xin a$, and then $a=[x]$ so $(a,psi(x))=([x],psi(x))in S$. So for any $ain X/sim$, there exists at least one $bin Y$ such that $(a,b)in S$. We now just have to show this $b$ is unique. So suppose $(a,b)$ and $(a,c)$ are both elements of $S$. By definition of $S$, this means there exist $x,yin X$ such that $(a,b)=([x],psi(x))$ and $(a,c)=([y],psi(y))$. We need to know that $b=c$ under these circumstances. In other words, we need to know that whenever $[x]=[y]$, we have $psi(x)=psi(y)$.
Or, in other words, we need to know that whenever $xsim y$, we have $psi(x)=psi(y)$. In other words, we need to check that our function $psi$ always gives the same output on two equivalent inputs, so that defining $phi([x])=psi(x)$ gives a well-defined output that is independent of the representative $x$ chosen for the equivalence class $a=[x]$.
So, in this situation we do indeed get a function $phi$. Given any $ain X/sim$, we can evaluate $phi(a)$ by choosing any $xin a$ (so that then $a=[x]$) and then we have $phi(a)=psi(x)$. We get the same answer no matter what element $xin a$ we choose, using our assumption about the function $psi$.
To put it another way, we can avoid using the axiom of choice by just making all choices simultaneously and then checking that the result is well-defined. That's what our set $S$ above does: it defines $phi([x])=psi(x)$ for all possible representatives $x$ of an equivalence class, without singling out any choice. Then we just have to check that this really is a function.
Now, where does the axiom of choice come in? It comes in when you don't actually have a function $psi$ satisfying this property at all, but still want to somehow define a function $phi$. In other words, you want to define $phi(a)=psi(x)$ for some $xin a$, but $psi(x)$ will actually give a different answer depending on what $xin a$ you choose so the construction above does not define a function.
In this case, what you do instead is use a choice function (via the axiom of choice or otherwise) $p:X/simto X$ such that $p(a)in a$ for each $ain X/sim$, and then define $phi(a)=psi(p(a))$. That is, we define $phi(a)$ to be $psi(x)$ where $x$ is our specific representative of $a$ that is chosen by the choice function $p$, rather than any arbitrary element of $a$. When we do this construction, we do not have to check that anything is well-defined, since $phi$ is defined as a composition of two functions and therefore is automatically a function.
answered Jul 17 at 22:25
Eric Wofsey
162k12189300
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
When you write $[x]$, this is a very explicit and very concrete subset of $X$. So when you want to define $phi([x])$, you really want to define it for the equivalence class.
This is fine, and no use of the axiom of choice is needed. However, if your definition of $phi([x])$ somehow depends on $x$, then you need to verify that for $x'in[x]$, the definition yields the same result. This is what it means to be well-defined.
So for example, $phi([x])=[x]$ does not depend on $[x]$, it's just the identity function, and it's easier to see as $phi(A)=A$ for $Ain X/sim$, for that matter. But something like $[x]+[y]=[x+y]$, certainly depends on the values of $x$ and $y$, and you want to show that $+$ as defined on $X$ behaves nicely with respect to $sim$. This requires, in the majority of cases, no choice. Since you only need to work one or two equivalence classes at a time, so you're only choosing two members from a non-empty set. No choice is used for that.
Using representatives is a tricky thing, though. While on its own, the existence of a system of representative from an arbitrary equivalence relation is the enough to prove the full axiom of choice, it is worth noting that you already assumed that $phi$ is well-defined. In that case $psi(x)$ is literally defined as $phi([x])$, which is the other way around and no choice was used for that. Of course, I suspect that you meant that first you chose representatives, then you had the function $psi$ and then you defined $phi([x])=psi(x')$, where $x'$ is the representative for $[x]$. But if that's not the case, and you first had $phi$, and only then defined $psi$, then choice was not used at all.
answered Jul 17 at 21:59
Asaf Karagila♦
292k31403733
1
I found an old answer of yours that clarify why if you work with finite number of equivalence classes at a time you don't need choice: math.stackexchange.com/questions/85153/…
– Holo
Jul 17 at 22:15
I think your suspicion is correct. I mean to say something like: Take a function $psi$ on $X$, choose a representative $x'$ for $[x]$, and define $phi([x]) = psi(x')$. (I really mean that $phi$ makes explicit reference to representatives, like in your example with addition, but I think defining $phi$ in terms of $psi$ captures what I mean.) But to be sure: In the opposite case no choice is used, but in this case, since I am choosing a representative of a single equivalence class, choice is not used here either? Just want to make sure, since you seem to be emphasising the opposite case.
– Danny Hansen
Jul 18 at 12:59
1
@Danny: If you define $phi$ globally by first choosing representatives, choice is necessary. If you define $phi([x])$ in terms of $x$, then you need to argue that indeed this definition does not depend on the choice of $x$. In practice, these definitions only depend on $x$ (or some other finitely many representatives), and then choice is not needed since ZF lets us choose from finitely many non-empty sets at the same time. If you define $psi$ in terms of $phi$, then no choice is necessary, was my point.
– Asaf Karagila♦
Jul 18 at 13:02
add a comment |Â
up vote
3
down vote
When you write $[x]$, this is a very explicit and very concrete subset of $X$. So when you want to define $phi([x])$, you really want to define it for the equivalence class.
This is fine, and no use of the axiom of choice is needed. However, if your definition of $phi([x])$ somehow depends on $x$, then you need to verify that for $x'in[x]$, the definition yields the same result. This is what it means to be well-defined.
So for example, $phi([x])=[x]$ does not depend on $[x]$, it's just the identity function, and it's easier to see as $phi(A)=A$ for $Ain X/sim$, for that matter. But something like $[x]+[y]=[x+y]$, certainly depends on the values of $x$ and $y$, and you want to show that $+$ as defined on $X$ behaves nicely with respect to $sim$. This requires, in the majority of cases, no choice. Since you only need to work one or two equivalence classes at a time, so you're only choosing two members from a non-empty set. No choice is used for that.
Using representatives is a tricky thing, though. While on its own, the existence of a system of representative from an arbitrary equivalence relation is the enough to prove the full axiom of choice, it is worth noting that you already assumed that $phi$ is well-defined. In that case $psi(x)$ is literally defined as $phi([x])$, which is the other way around and no choice was used for that. Of course, I suspect that you meant that first you chose representatives, then you had the function $psi$ and then you defined $phi([x])=psi(x')$, where $x'$ is the representative for $[x]$. But if that's not the case, and you first had $phi$, and only then defined $psi$, then choice was not used at all.
answered Jul 17 at 21:59
Asaf Karagila♦
292k31403733
1
I found an old answer of yours that clarify why if you work with finite number of equivalence classes at a time you don't need choice: math.stackexchange.com/questions/85153/…
– Holo
Jul 17 at 22:15
I think your suspicion is correct. I mean to say something like: Take a function $psi$ on $X$, choose a representative $x'$ for $[x]$, and define $phi([x]) = psi(x')$. (I really mean that $phi$ makes explicit reference to representatives, like in your example with addition, but I think defining $phi$ in terms of $psi$ captures what I mean.) But to be sure: In the opposite case no choice is used, but in this case, since I am choosing a representative of a single equivalence class, choice is not used here either? Just want to make sure, since you seem to be emphasising the opposite case.
– Danny Hansen
Jul 18 at 12:59
1
@Danny: If you define $phi$ globally by first choosing representatives, choice is necessary. If you define $phi([x])$ in terms of $x$, then you need to argue that indeed this definition does not depend on the choice of $x$. In practice, these definitions only depend on $x$ (or some other finitely many representatives), and then choice is not needed since ZF lets us choose from finitely many non-empty sets at the same time. If you define $psi$ in terms of $phi$, then no choice is necessary, was my point.
– Asaf Karagila♦
Jul 18 at 13:02
add a comment |Â
up vote
3
down vote
up vote
3
down vote
When you write $[x]$, this is a very explicit and very concrete subset of $X$. So when you want to define $phi([x])$, you really want to define it for the equivalence class.
This is fine, and no use of the axiom of choice is needed. However, if your definition of $phi([x])$ somehow depends on $x$, then you need to verify that for $x'in[x]$, the definition yields the same result. This is what it means to be well-defined.
So for example, $phi([x])=[x]$ does not depend on $[x]$, it's just the identity function, and it's easier to see as $phi(A)=A$ for $Ain X/sim$, for that matter. But something like $[x]+[y]=[x+y]$, certainly depends on the values of $x$ and $y$, and you want to show that $+$ as defined on $X$ behaves nicely with respect to $sim$. This requires, in the majority of cases, no choice. Since you only need to work one or two equivalence classes at a time, so you're only choosing two members from a non-empty set. No choice is used for that.
Using representatives is a tricky thing, though. While on its own, the existence of a system of representative from an arbitrary equivalence relation is the enough to prove the full axiom of choice, it is worth noting that you already assumed that $phi$ is well-defined. In that case $psi(x)$ is literally defined as $phi([x])$, which is the other way around and no choice was used for that. Of course, I suspect that you meant that first you chose representatives, then you had the function $psi$ and then you defined $phi([x])=psi(x')$, where $x'$ is the representative for $[x]$. But if that's not the case, and you first had $phi$, and only then defined $psi$, then choice was not used at all.
answered Jul 17 at 21:59
Asaf Karagila♦
292k31403733
When you write $[x]$, this is a very explicit and very concrete subset of $X$. So when you want to define $phi([x])$, you really want to define it for the equivalence class.
This is fine, and no use of the axiom of choice is needed. However, if your definition of $phi([x])$ somehow depends on $x$, then you need to verify that for $x'in[x]$, the definition yields the same result. This is what it means to be well-defined.
So for example, $phi([x])=[x]$ does not depend on $[x]$, it's just the identity function, and it's easier to see as $phi(A)=A$ for $Ain X/sim$, for that matter. But something like $[x]+[y]=[x+y]$, certainly depends on the values of $x$ and $y$, and you want to show that $+$ as defined on $X$ behaves nicely with respect to $sim$. This requires, in the majority of cases, no choice. Since you only need to work one or two equivalence classes at a time, so you're only choosing two members from a non-empty set. No choice is used for that.
Using representatives is a tricky thing, though. While on its own, the existence of a system of representative from an arbitrary equivalence relation is the enough to prove the full axiom of choice, it is worth noting that you already assumed that $phi$ is well-defined. In that case $psi(x)$ is literally defined as $phi([x])$, which is the other way around and no choice was used for that. Of course, I suspect that you meant that first you chose representatives, then you had the function $psi$ and then you defined $phi([x])=psi(x')$, where $x'$ is the representative for $[x]$. But if that's not the case, and you first had $phi$, and only then defined $psi$, then choice was not used at all.
answered Jul 17 at 21:59
Asaf Karagila♦
292k31403733
answered Jul 17 at 21:59
Asaf Karagila♦
292k31403733
answered Jul 17 at 21:59
Asaf Karagila♦
292k31403733
answered Jul 17 at 21:59
Asaf Karagila♦
292k31403733
292k31403733
1
I found an old answer of yours that clarify why if you work with finite number of equivalence classes at a time you don't need choice: math.stackexchange.com/questions/85153/…
– Holo
Jul 17 at 22:15
I think your suspicion is correct. I mean to say something like: Take a function $psi$ on $X$, choose a representative $x'$ for $[x]$, and define $phi([x]) = psi(x')$. (I really mean that $phi$ makes explicit reference to representatives, like in your example with addition, but I think defining $phi$ in terms of $psi$ captures what I mean.) But to be sure: In the opposite case no choice is used, but in this case, since I am choosing a representative of a single equivalence class, choice is not used here either? Just want to make sure, since you seem to be emphasising the opposite case.
– Danny Hansen
Jul 18 at 12:59
1
@Danny: If you define $phi$ globally by first choosing representatives, choice is necessary. If you define $phi([x])$ in terms of $x$, then you need to argue that indeed this definition does not depend on the choice of $x$. In practice, these definitions only depend on $x$ (or some other finitely many representatives), and then choice is not needed since ZF lets us choose from finitely many non-empty sets at the same time. If you define $psi$ in terms of $phi$, then no choice is necessary, was my point.
– Asaf Karagila♦
Jul 18 at 13:02
add a comment |Â
1
I found an old answer of yours that clarify why if you work with finite number of equivalence classes at a time you don't need choice: math.stackexchange.com/questions/85153/…
– Holo
Jul 17 at 22:15
I think your suspicion is correct. I mean to say something like: Take a function $psi$ on $X$, choose a representative $x'$ for $[x]$, and define $phi([x]) = psi(x')$. (I really mean that $phi$ makes explicit reference to representatives, like in your example with addition, but I think defining $phi$ in terms of $psi$ captures what I mean.) But to be sure: In the opposite case no choice is used, but in this case, since I am choosing a representative of a single equivalence class, choice is not used here either? Just want to make sure, since you seem to be emphasising the opposite case.
– Danny Hansen
Jul 18 at 12:59
1
@Danny: If you define $phi$ globally by first choosing representatives, choice is necessary. If you define $phi([x])$ in terms of $x$, then you need to argue that indeed this definition does not depend on the choice of $x$. In practice, these definitions only depend on $x$ (or some other finitely many representatives), and then choice is not needed since ZF lets us choose from finitely many non-empty sets at the same time. If you define $psi$ in terms of $phi$, then no choice is necessary, was my point.
– Asaf Karagila♦
Jul 18 at 13:02
1
1
I found an old answer of yours that clarify why if you work with finite number of equivalence classes at a time you don't need choice: math.stackexchange.com/questions/85153/…
– Holo
Jul 17 at 22:15
I found an old answer of yours that clarify why if you work with finite number of equivalence classes at a time you don't need choice: math.stackexchange.com/questions/85153/…
– Holo
Jul 17 at 22:15
I think your suspicion is correct. I mean to say something like: Take a function $psi$ on $X$, choose a representative $x'$ for $[x]$, and define $phi([x]) = psi(x')$. (I really mean that $phi$ makes explicit reference to representatives, like in your example with addition, but I think defining $phi$ in terms of $psi$ captures what I mean.) But to be sure: In the opposite case no choice is used, but in this case, since I am choosing a representative of a single equivalence class, choice is not used here either? Just want to make sure, since you seem to be emphasising the opposite case.
– Danny Hansen
Jul 18 at 12:59
I think your suspicion is correct. I mean to say something like: Take a function $psi$ on $X$, choose a representative $x'$ for $[x]$, and define $phi([x]) = psi(x')$. (I really mean that $phi$ makes explicit reference to representatives, like in your example with addition, but I think defining $phi$ in terms of $psi$ captures what I mean.) But to be sure: In the opposite case no choice is used, but in this case, since I am choosing a representative of a single equivalence class, choice is not used here either? Just want to make sure, since you seem to be emphasising the opposite case.
– Danny Hansen
Jul 18 at 12:59
1
1
@Danny: If you define $phi$ globally by first choosing representatives, choice is necessary. If you define $phi([x])$ in terms of $x$, then you need to argue that indeed this definition does not depend on the choice of $x$. In practice, these definitions only depend on $x$ (or some other finitely many representatives), and then choice is not needed since ZF lets us choose from finitely many non-empty sets at the same time. If you define $psi$ in terms of $phi$, then no choice is necessary, was my point.
– Asaf Karagila♦
Jul 18 at 13:02
@Danny: If you define $phi$ globally by first choosing representatives, choice is necessary. If you define $phi([x])$ in terms of $x$, then you need to argue that indeed this definition does not depend on the choice of $x$. In practice, these definitions only depend on $x$ (or some other finitely many representatives), and then choice is not needed since ZF lets us choose from finitely many non-empty sets at the same time. If you define $psi$ in terms of $phi$, then no choice is necessary, was my point.
– Asaf Karagila♦
Jul 18 at 13:02
add a comment |Â
up vote
3
down vote
The axiom of choice is not needed here (assuming you can define your function $psi:Xto Y$ without it and the resulting function $phi$ is well-defined). Explicitly, define $$S=([x],psi(x)):xin Xsubseteq X/simtimes Y.$$
This is a perfectly well-defined set of ordered pairs and no choice is needed to define it. If this set is actually the graph of a function (in other words, for every element $ain X/sim times Y$ there exists a unique $bin Y$ such that $(a,b)in S$), then that function is the function $phi$ you are trying to define.
So to check that we have defined a function, we just need to check that $S$ is the graph of a function. For any $ain X/sim$, there exists $xin a$, and then $a=[x]$ so $(a,psi(x))=([x],psi(x))in S$. So for any $ain X/sim$, there exists at least one $bin Y$ such that $(a,b)in S$. We now just have to show this $b$ is unique. So suppose $(a,b)$ and $(a,c)$ are both elements of $S$. By definition of $S$, this means there exist $x,yin X$ such that $(a,b)=([x],psi(x))$ and $(a,c)=([y],psi(y))$. We need to know that $b=c$ under these circumstances. In other words, we need to know that whenever $[x]=[y]$, we have $psi(x)=psi(y)$.
Or, in other words, we need to know that whenever $xsim y$, we have $psi(x)=psi(y)$. In other words, we need to check that our function $psi$ always gives the same output on two equivalent inputs, so that defining $phi([x])=psi(x)$ gives a well-defined output that is independent of the representative $x$ chosen for the equivalence class $a=[x]$.
So, in this situation we do indeed get a function $phi$. Given any $ain X/sim$, we can evaluate $phi(a)$ by choosing any $xin a$ (so that then $a=[x]$) and then we have $phi(a)=psi(x)$. We get the same answer no matter what element $xin a$ we choose, using our assumption about the function $psi$.
To put it another way, we can avoid using the axiom of choice by just making all choices simultaneously and then checking that the result is well-defined. That's what our set $S$ above does: it defines $phi([x])=psi(x)$ for all possible representatives $x$ of an equivalence class, without singling out any choice. Then we just have to check that this really is a function.
Now, where does the axiom of choice come in? It comes in when you don't actually have a function $psi$ satisfying this property at all, but still want to somehow define a function $phi$. In other words, you want to define $phi(a)=psi(x)$ for some $xin a$, but $psi(x)$ will actually give a different answer depending on what $xin a$ you choose so the construction above does not define a function.
In this case, what you do instead is use a choice function (via the axiom of choice or otherwise) $p:X/simto X$ such that $p(a)in a$ for each $ain X/sim$, and then define $phi(a)=psi(p(a))$. That is, we define $phi(a)$ to be $psi(x)$ where $x$ is our specific representative of $a$ that is chosen by the choice function $p$, rather than any arbitrary element of $a$. When we do this construction, we do not have to check that anything is well-defined, since $phi$ is defined as a composition of two functions and therefore is automatically a function.
answered Jul 17 at 22:25
Eric Wofsey
162k12189300
add a comment |Â
up vote
3
down vote
The axiom of choice is not needed here (assuming you can define your function $psi:Xto Y$ without it and the resulting function $phi$ is well-defined). Explicitly, define $$S=([x],psi(x)):xin Xsubseteq X/simtimes Y.$$
This is a perfectly well-defined set of ordered pairs and no choice is needed to define it. If this set is actually the graph of a function (in other words, for every element $ain X/sim times Y$ there exists a unique $bin Y$ such that $(a,b)in S$), then that function is the function $phi$ you are trying to define.
So to check that we have defined a function, we just need to check that $S$ is the graph of a function. For any $ain X/sim$, there exists $xin a$, and then $a=[x]$ so $(a,psi(x))=([x],psi(x))in S$. So for any $ain X/sim$, there exists at least one $bin Y$ such that $(a,b)in S$. We now just have to show this $b$ is unique. So suppose $(a,b)$ and $(a,c)$ are both elements of $S$. By definition of $S$, this means there exist $x,yin X$ such that $(a,b)=([x],psi(x))$ and $(a,c)=([y],psi(y))$. We need to know that $b=c$ under these circumstances. In other words, we need to know that whenever $[x]=[y]$, we have $psi(x)=psi(y)$.
Or, in other words, we need to know that whenever $xsim y$, we have $psi(x)=psi(y)$. In other words, we need to check that our function $psi$ always gives the same output on two equivalent inputs, so that defining $phi([x])=psi(x)$ gives a well-defined output that is independent of the representative $x$ chosen for the equivalence class $a=[x]$.
So, in this situation we do indeed get a function $phi$. Given any $ain X/sim$, we can evaluate $phi(a)$ by choosing any $xin a$ (so that then $a=[x]$) and then we have $phi(a)=psi(x)$. We get the same answer no matter what element $xin a$ we choose, using our assumption about the function $psi$.
To put it another way, we can avoid using the axiom of choice by just making all choices simultaneously and then checking that the result is well-defined. That's what our set $S$ above does: it defines $phi([x])=psi(x)$ for all possible representatives $x$ of an equivalence class, without singling out any choice. Then we just have to check that this really is a function.
Now, where does the axiom of choice come in? It comes in when you don't actually have a function $psi$ satisfying this property at all, but still want to somehow define a function $phi$. In other words, you want to define $phi(a)=psi(x)$ for some $xin a$, but $psi(x)$ will actually give a different answer depending on what $xin a$ you choose so the construction above does not define a function.
In this case, what you do instead is use a choice function (via the axiom of choice or otherwise) $p:X/simto X$ such that $p(a)in a$ for each $ain X/sim$, and then define $phi(a)=psi(p(a))$. That is, we define $phi(a)$ to be $psi(x)$ where $x$ is our specific representative of $a$ that is chosen by the choice function $p$, rather than any arbitrary element of $a$. When we do this construction, we do not have to check that anything is well-defined, since $phi$ is defined as a composition of two functions and therefore is automatically a function.
answered Jul 17 at 22:25
Eric Wofsey
162k12189300
add a comment |Â
up vote
3
down vote
up vote
3
down vote
The axiom of choice is not needed here (assuming you can define your function $psi:Xto Y$ without it and the resulting function $phi$ is well-defined). Explicitly, define $$S=([x],psi(x)):xin Xsubseteq X/simtimes Y.$$
This is a perfectly well-defined set of ordered pairs and no choice is needed to define it. If this set is actually the graph of a function (in other words, for every element $ain X/sim times Y$ there exists a unique $bin Y$ such that $(a,b)in S$), then that function is the function $phi$ you are trying to define.
So to check that we have defined a function, we just need to check that $S$ is the graph of a function. For any $ain X/sim$, there exists $xin a$, and then $a=[x]$ so $(a,psi(x))=([x],psi(x))in S$. So for any $ain X/sim$, there exists at least one $bin Y$ such that $(a,b)in S$. We now just have to show this $b$ is unique. So suppose $(a,b)$ and $(a,c)$ are both elements of $S$. By definition of $S$, this means there exist $x,yin X$ such that $(a,b)=([x],psi(x))$ and $(a,c)=([y],psi(y))$. We need to know that $b=c$ under these circumstances. In other words, we need to know that whenever $[x]=[y]$, we have $psi(x)=psi(y)$.
Or, in other words, we need to know that whenever $xsim y$, we have $psi(x)=psi(y)$. In other words, we need to check that our function $psi$ always gives the same output on two equivalent inputs, so that defining $phi([x])=psi(x)$ gives a well-defined output that is independent of the representative $x$ chosen for the equivalence class $a=[x]$.
So, in this situation we do indeed get a function $phi$. Given any $ain X/sim$, we can evaluate $phi(a)$ by choosing any $xin a$ (so that then $a=[x]$) and then we have $phi(a)=psi(x)$. We get the same answer no matter what element $xin a$ we choose, using our assumption about the function $psi$.
To put it another way, we can avoid using the axiom of choice by just making all choices simultaneously and then checking that the result is well-defined. That's what our set $S$ above does: it defines $phi([x])=psi(x)$ for all possible representatives $x$ of an equivalence class, without singling out any choice. Then we just have to check that this really is a function.
Now, where does the axiom of choice come in? It comes in when you don't actually have a function $psi$ satisfying this property at all, but still want to somehow define a function $phi$. In other words, you want to define $phi(a)=psi(x)$ for some $xin a$, but $psi(x)$ will actually give a different answer depending on what $xin a$ you choose so the construction above does not define a function.
In this case, what you do instead is use a choice function (via the axiom of choice or otherwise) $p:X/simto X$ such that $p(a)in a$ for each $ain X/sim$, and then define $phi(a)=psi(p(a))$. That is, we define $phi(a)$ to be $psi(x)$ where $x$ is our specific representative of $a$ that is chosen by the choice function $p$, rather than any arbitrary element of $a$. When we do this construction, we do not have to check that anything is well-defined, since $phi$ is defined as a composition of two functions and therefore is automatically a function.
answered Jul 17 at 22:25
Eric Wofsey
162k12189300
The axiom of choice is not needed here (assuming you can define your function $psi:Xto Y$ without it and the resulting function $phi$ is well-defined). Explicitly, define $$S=([x],psi(x)):xin Xsubseteq X/simtimes Y.$$
This is a perfectly well-defined set of ordered pairs and no choice is needed to define it. If this set is actually the graph of a function (in other words, for every element $ain X/sim times Y$ there exists a unique $bin Y$ such that $(a,b)in S$), then that function is the function $phi$ you are trying to define.
So to check that we have defined a function, we just need to check that $S$ is the graph of a function. For any $ain X/sim$, there exists $xin a$, and then $a=[x]$ so $(a,psi(x))=([x],psi(x))in S$. So for any $ain X/sim$, there exists at least one $bin Y$ such that $(a,b)in S$. We now just have to show this $b$ is unique. So suppose $(a,b)$ and $(a,c)$ are both elements of $S$. By definition of $S$, this means there exist $x,yin X$ such that $(a,b)=([x],psi(x))$ and $(a,c)=([y],psi(y))$. We need to know that $b=c$ under these circumstances. In other words, we need to know that whenever $[x]=[y]$, we have $psi(x)=psi(y)$.
Or, in other words, we need to know that whenever $xsim y$, we have $psi(x)=psi(y)$. In other words, we need to check that our function $psi$ always gives the same output on two equivalent inputs, so that defining $phi([x])=psi(x)$ gives a well-defined output that is independent of the representative $x$ chosen for the equivalence class $a=[x]$.
So, in this situation we do indeed get a function $phi$. Given any $ain X/sim$, we can evaluate $phi(a)$ by choosing any $xin a$ (so that then $a=[x]$) and then we have $phi(a)=psi(x)$. We get the same answer no matter what element $xin a$ we choose, using our assumption about the function $psi$.
To put it another way, we can avoid using the axiom of choice by just making all choices simultaneously and then checking that the result is well-defined. That's what our set $S$ above does: it defines $phi([x])=psi(x)$ for all possible representatives $x$ of an equivalence class, without singling out any choice. Then we just have to check that this really is a function.
Now, where does the axiom of choice come in? It comes in when you don't actually have a function $psi$ satisfying this property at all, but still want to somehow define a function $phi$. In other words, you want to define $phi(a)=psi(x)$ for some $xin a$, but $psi(x)$ will actually give a different answer depending on what $xin a$ you choose so the construction above does not define a function.
In this case, what you do instead is use a choice function (via the axiom of choice or otherwise) $p:X/simto X$ such that $p(a)in a$ for each $ain X/sim$, and then define $phi(a)=psi(p(a))$. That is, we define $phi(a)$ to be $psi(x)$ where $x$ is our specific representative of $a$ that is chosen by the choice function $p$, rather than any arbitrary element of $a$. When we do this construction, we do not have to check that anything is well-defined, since $phi$ is defined as a composition of two functions and therefore is automatically a function.
answered Jul 17 at 22:25
Eric Wofsey
162k12189300
edited Jul 17 at 22:31
answered Jul 17 at 22:25
Eric Wofsey
162k12189300
answered Jul 17 at 22:25
Eric Wofsey
162k12189300
answered Jul 17 at 22:25
Eric Wofsey
162k12189300
162k12189300
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%2f2854959%2fhow-do-we-define-functions-on-quotient-sets%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
$[x]$ denotes the equivalence class of the element $x$. So, $[x] = y : x sim y $
– gd1035
Jul 17 at 21:45
Closely related: math.stackexchange.com/questions/2110908/…
– Eric Wofsey
Jul 17 at 22:06
1
It appears that you noticed that writing X/sim would result in too much space between $X$ and $sim,$ so you manually added some negative space. But the natural way to remedy the problem is to write X/sim, so that you see $X/sim.$ A moment's thought may tell you why it works that way.
– Michael Hardy
Jul 17 at 23:06