Mixing
To what extent can I “disjointize†an arbitary collection of sets?
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Let $A_1,A_2,dotsc$ be a collection of sets, which may or may not already be disjoint, and define $B_1=A_1,B_n+1=A_n+1setminusbigcup_ile nA_i$ for $nge1$. Then $B_1,B_2,dotsc$ is disjoint and $bigcup^infty A_i=bigcup^infty B_i$. Now I'm curious if this works given an arbitrary collection of sets $A_i$, $iin I$, where $I$ is ANY index set. I'm thinking, why not take steal the structure of the original index set for the new one?
Define $J=I$ and $B_j=A_i$ for some $jin J$ and any $iin I$, then define $B_k=A_lsetminusbigcup_j B_j$ where for every new $B_k$ defined, $lin I$ s.t. $l$ not already chosen and $j$ ranges over the $B_j$ already defined. Then $B_j$, $jin J$, is disjoint and $bigcup_iin IA_i=bigcup_jin JB_j$.
But all this seems very sketchy. For $I=mathbbN$, the method of "disjointizing" $A_i$ seems to work in the that defining the sets $B_i$ is "complete" (so the $B_i$'s exist), i.e. in the sense that we somehow exhaust $iinmathbbN$, and that the $B_i$'s are unique, since the next $B_n+1$ is uniquely determined by the $le$ relation on $mathbbN$. (I believe we can un-unique them by matching $J=I$ if the second method if it works). But an index set $I$ could have zero structure and any cardinality, and then we need a method to keep track of already chosen elements.
My question is: Does the second method work, i.e. do the $B_i$'s exist? If they do, I don't think they're unique, but it doesn't matter since all we want is disjointness.
elementary-set-theory proof-verification proof-writing induction
asked Jul 28 at 18:17
palmpo
1651113
add a comment |Â
up vote
4
down vote
favorite
Let $A_1,A_2,dotsc$ be a collection of sets, which may or may not already be disjoint, and define $B_1=A_1,B_n+1=A_n+1setminusbigcup_ile nA_i$ for $nge1$. Then $B_1,B_2,dotsc$ is disjoint and $bigcup^infty A_i=bigcup^infty B_i$. Now I'm curious if this works given an arbitrary collection of sets $A_i$, $iin I$, where $I$ is ANY index set. I'm thinking, why not take steal the structure of the original index set for the new one?
Define $J=I$ and $B_j=A_i$ for some $jin J$ and any $iin I$, then define $B_k=A_lsetminusbigcup_j B_j$ where for every new $B_k$ defined, $lin I$ s.t. $l$ not already chosen and $j$ ranges over the $B_j$ already defined. Then $B_j$, $jin J$, is disjoint and $bigcup_iin IA_i=bigcup_jin JB_j$.
But all this seems very sketchy. For $I=mathbbN$, the method of "disjointizing" $A_i$ seems to work in the that defining the sets $B_i$ is "complete" (so the $B_i$'s exist), i.e. in the sense that we somehow exhaust $iinmathbbN$, and that the $B_i$'s are unique, since the next $B_n+1$ is uniquely determined by the $le$ relation on $mathbbN$. (I believe we can un-unique them by matching $J=I$ if the second method if it works). But an index set $I$ could have zero structure and any cardinality, and then we need a method to keep track of already chosen elements.
My question is: Does the second method work, i.e. do the $B_i$'s exist? If they do, I don't think they're unique, but it doesn't matter since all we want is disjointness.
elementary-set-theory proof-verification proof-writing induction
asked Jul 28 at 18:17
palmpo
1651113
The $B_i$ of the second method exist, though you cannot list them in general. The arbitrary union of sets is well defined as well as the difference of two sets.
– Javi
Jul 28 at 18:35
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Let $A_1,A_2,dotsc$ be a collection of sets, which may or may not already be disjoint, and define $B_1=A_1,B_n+1=A_n+1setminusbigcup_ile nA_i$ for $nge1$. Then $B_1,B_2,dotsc$ is disjoint and $bigcup^infty A_i=bigcup^infty B_i$. Now I'm curious if this works given an arbitrary collection of sets $A_i$, $iin I$, where $I$ is ANY index set. I'm thinking, why not take steal the structure of the original index set for the new one?
Define $J=I$ and $B_j=A_i$ for some $jin J$ and any $iin I$, then define $B_k=A_lsetminusbigcup_j B_j$ where for every new $B_k$ defined, $lin I$ s.t. $l$ not already chosen and $j$ ranges over the $B_j$ already defined. Then $B_j$, $jin J$, is disjoint and $bigcup_iin IA_i=bigcup_jin JB_j$.
But all this seems very sketchy. For $I=mathbbN$, the method of "disjointizing" $A_i$ seems to work in the that defining the sets $B_i$ is "complete" (so the $B_i$'s exist), i.e. in the sense that we somehow exhaust $iinmathbbN$, and that the $B_i$'s are unique, since the next $B_n+1$ is uniquely determined by the $le$ relation on $mathbbN$. (I believe we can un-unique them by matching $J=I$ if the second method if it works). But an index set $I$ could have zero structure and any cardinality, and then we need a method to keep track of already chosen elements.
My question is: Does the second method work, i.e. do the $B_i$'s exist? If they do, I don't think they're unique, but it doesn't matter since all we want is disjointness.
elementary-set-theory proof-verification proof-writing induction
asked Jul 28 at 18:17
palmpo
1651113
Let $A_1,A_2,dotsc$ be a collection of sets, which may or may not already be disjoint, and define $B_1=A_1,B_n+1=A_n+1setminusbigcup_ile nA_i$ for $nge1$. Then $B_1,B_2,dotsc$ is disjoint and $bigcup^infty A_i=bigcup^infty B_i$. Now I'm curious if this works given an arbitrary collection of sets $A_i$, $iin I$, where $I$ is ANY index set. I'm thinking, why not take steal the structure of the original index set for the new one?
Define $J=I$ and $B_j=A_i$ for some $jin J$ and any $iin I$, then define $B_k=A_lsetminusbigcup_j B_j$ where for every new $B_k$ defined, $lin I$ s.t. $l$ not already chosen and $j$ ranges over the $B_j$ already defined. Then $B_j$, $jin J$, is disjoint and $bigcup_iin IA_i=bigcup_jin JB_j$.
But all this seems very sketchy. For $I=mathbbN$, the method of "disjointizing" $A_i$ seems to work in the that defining the sets $B_i$ is "complete" (so the $B_i$'s exist), i.e. in the sense that we somehow exhaust $iinmathbbN$, and that the $B_i$'s are unique, since the next $B_n+1$ is uniquely determined by the $le$ relation on $mathbbN$. (I believe we can un-unique them by matching $J=I$ if the second method if it works). But an index set $I$ could have zero structure and any cardinality, and then we need a method to keep track of already chosen elements.
My question is: Does the second method work, i.e. do the $B_i$'s exist? If they do, I don't think they're unique, but it doesn't matter since all we want is disjointness.
elementary-set-theory proof-verification proof-writing induction
asked Jul 28 at 18:17
palmpo
1651113
asked Jul 28 at 18:17
palmpo
1651113
asked Jul 28 at 18:17
palmpo
1651113
asked Jul 28 at 18:17
palmpo
1651113
1651113
The $B_i$ of the second method exist, though you cannot list them in general. The arbitrary union of sets is well defined as well as the difference of two sets.
– Javi
Jul 28 at 18:35
add a comment |Â
The $B_i$ of the second method exist, though you cannot list them in general. The arbitrary union of sets is well defined as well as the difference of two sets.
– Javi
Jul 28 at 18:35
The $B_i$ of the second method exist, though you cannot list them in general. The arbitrary union of sets is well defined as well as the difference of two sets.
– Javi
Jul 28 at 18:35
The $B_i$ of the second method exist, though you cannot list them in general. The arbitrary union of sets is well defined as well as the difference of two sets.
– Javi
Jul 28 at 18:35
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
6
down vote
accepted
The property of $mathbbN$ which allows us to do what you want is the fact that it is well-ordered. For those not familiar:
Definition: An order $leqslant$ on a set $A$ is a well-ordering if it satisfies the following conditions:
- $aleqslant a$ for each $ain A$ (reflexivity),
- For each $a,bin A$, either $aleqslant b$ or $bleqslant a$ holds (comperability),
- $aleqslant b$ and $bleqslant a$ implies $a=b$ for each $a,bin A$ (symmetry),
- $aleqslant b$ and $bleqslant c$ implies $aleqslant c$ for each $a,b,cin A$ (transitivity),
- For each $Ssubseteq A$, $S$ has a least element; that is, there is some $sin S$ such that $sleqslant a$ for each $ain S$ (well-ordering).
There is a theorem, the Well-Ordering Theorem, which is equivalent to the axiom of choice, which states that every set can be well-ordered. Using this theorem we may "disjointize" any collection of sets.
Let $mathcal A= A_i_iin I$ be a collection of sets indexed by the the set $I$. We will construct the sets $B_i$, which have the desired property that $$bigcup_iin I B_i=bigcup_iin I A_i,$$ using a process called transfinite induction. Let $leqslant$ be a well-ordering of $I$. Let $a$ be the least element of $I$ and write $B_a=A_a.$ Now let $iin I$ be such that for each $j< i$ we have constructed pairwise disjoint sets $B_j$ from the collection $mathcalA.$ Then let $B_i=A_isetminus bigcup_j<i A_j$. It is clear that $B_icap B_j=varnothing$ for each $j<i$. Since $B_isubseteq A_i$ for each $iin I$, we have $$bigcup_iin I B_isubseteqbigcup_iin I A_i.$$ To see the reverse inclusion, observe that for each $xinbigcup_iin I A_i$, the set $C_x=iin I;subseteq I$ has a least element $j$ and that $xin B_j,$ so $$bigcup_iin I B_isupseteqbigcup_iin I A_i,$$ giving equality of the two sets.
At first it may seem that transfinite induction works even with sets which are only totally ordered, such as the closed unit interval $[0,1].$ However, this is not the case. To see this, I recommend reading the proof that transfinite induction works. Intuitively, without a well-ordering, one has trouble "moving on to the next element" while performing the induction. I used the first chapter of Munkres' Topology, but there may be better sources. I enjoyed Munkres because he goes through a good amount of material, and the supplementary exercises at the end of nearly every chapter are challenging and illuminating.
answered Jul 28 at 19:04
D. Brogan
463311
1
Thanks for mentioning what's specifically needed. If I'm on the right track, your defining of $B_i$ for any $iin I$ requires $B_j$ already defined for $j<i$ and eventually we hit $B_m$ for the least element $m$ of $I$, which we need well-ordering property to exist for infinite sets $I$ (else induct on $I$ finite). And the motivation would be that for any $B_i$, you want to exclude ("set-differencing") at least all the sets that were excluded for defining $B_j$, $j<i$.
– palmpo
Jul 28 at 21:03
Now that I think of it, it seems like if we have a path from a starting element to an ending element, we don't need well-ordering property. i.e. a set $I$ s.t. for any two $i,jin I$, there is some $k_alphain I$ s.t. $iRk_alpha R...Rk_beta j$.
– palmpo
Jul 28 at 21:10
I apologize for all these questions but I want to know what I can get away with, excluding choice. I don't know much about choice and it seems unintuitive like cheating, since you get something for free. Choice gives us a single well-order (possibly out of many) but at least for a fixed well-order, the $B_i$'s defined are unique. Is there another definition of $B_i$'s that disjointize a set without choice, not caring about uniqueness of the $B_i$'s generated?
– palmpo
Jul 28 at 21:20
Unless I'm mistaken, you do indeed need a well-ordering. I skipped some steps (which I will edit in after writing this comment), but the actual process by which one constructs the sets $B_i$ is called transfinite induction. It is a generalization of the usual mathematical induction one encounters with the natural numbers, and requires the set being inducted over to be well-ordered.
– D. Brogan
Jul 28 at 21:20
I understand the hesitation to use choice. At first it does seem like cheating, what with all the unintuitive results such as the Banach-Tarski Paradox or even the Well-Ordering Theorem following from it. However, even if one wishes to avoid it, this is an inherently set-theoretic question; moreover one in which we are dealing with arbitrary cardinalities. Choice is almost guaranteed to appear under those conditions.
– D. Brogan
Jul 28 at 21:24
 |Â
show 2 more comments
up vote
3
down vote
To complement D. Brogan's excellent answer, note that if we assume that every indexed family of sets can be disjointized, then we can prove the axiom of choice. So "every union can be disjointized" is an equivalent formulation of AC.
To see this, suppose we have a family $A_i_iin I$ of disjoint non-empty sets, and we want to find $b_i_iin I$ such that $b_iin A_i$. (This is one of several well-known equivalent formulations of the axiom of choice).
Without loss of generality we can assume that $I$ is disjoint from each of the $A_i$s.
Now consider the family $$ i,b mid iin I, bin A_i $$
and disjointize it. Let $b_i$ be the unique $bin A_i$ such that $i,b$ is in the disjointized family.
answered Jul 28 at 20:01
Henning Makholm
225k16290516
1
Thanks for the additional info, I keep encountering AC when I have to deal with sets without any structure and it just solves all the problems away.
– palmpo
Jul 28 at 21:24
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
The property of $mathbbN$ which allows us to do what you want is the fact that it is well-ordered. For those not familiar:
Definition: An order $leqslant$ on a set $A$ is a well-ordering if it satisfies the following conditions:
- $aleqslant a$ for each $ain A$ (reflexivity),
- For each $a,bin A$, either $aleqslant b$ or $bleqslant a$ holds (comperability),
- $aleqslant b$ and $bleqslant a$ implies $a=b$ for each $a,bin A$ (symmetry),
- $aleqslant b$ and $bleqslant c$ implies $aleqslant c$ for each $a,b,cin A$ (transitivity),
- For each $Ssubseteq A$, $S$ has a least element; that is, there is some $sin S$ such that $sleqslant a$ for each $ain S$ (well-ordering).
There is a theorem, the Well-Ordering Theorem, which is equivalent to the axiom of choice, which states that every set can be well-ordered. Using this theorem we may "disjointize" any collection of sets.
Let $mathcal A= A_i_iin I$ be a collection of sets indexed by the the set $I$. We will construct the sets $B_i$, which have the desired property that $$bigcup_iin I B_i=bigcup_iin I A_i,$$ using a process called transfinite induction. Let $leqslant$ be a well-ordering of $I$. Let $a$ be the least element of $I$ and write $B_a=A_a.$ Now let $iin I$ be such that for each $j< i$ we have constructed pairwise disjoint sets $B_j$ from the collection $mathcalA.$ Then let $B_i=A_isetminus bigcup_j<i A_j$. It is clear that $B_icap B_j=varnothing$ for each $j<i$. Since $B_isubseteq A_i$ for each $iin I$, we have $$bigcup_iin I B_isubseteqbigcup_iin I A_i.$$ To see the reverse inclusion, observe that for each $xinbigcup_iin I A_i$, the set $C_x=iin I;subseteq I$ has a least element $j$ and that $xin B_j,$ so $$bigcup_iin I B_isupseteqbigcup_iin I A_i,$$ giving equality of the two sets.
At first it may seem that transfinite induction works even with sets which are only totally ordered, such as the closed unit interval $[0,1].$ However, this is not the case. To see this, I recommend reading the proof that transfinite induction works. Intuitively, without a well-ordering, one has trouble "moving on to the next element" while performing the induction. I used the first chapter of Munkres' Topology, but there may be better sources. I enjoyed Munkres because he goes through a good amount of material, and the supplementary exercises at the end of nearly every chapter are challenging and illuminating.
answered Jul 28 at 19:04
D. Brogan
463311
1
Thanks for mentioning what's specifically needed. If I'm on the right track, your defining of $B_i$ for any $iin I$ requires $B_j$ already defined for $j<i$ and eventually we hit $B_m$ for the least element $m$ of $I$, which we need well-ordering property to exist for infinite sets $I$ (else induct on $I$ finite). And the motivation would be that for any $B_i$, you want to exclude ("set-differencing") at least all the sets that were excluded for defining $B_j$, $j<i$.
– palmpo
Jul 28 at 21:03
Now that I think of it, it seems like if we have a path from a starting element to an ending element, we don't need well-ordering property. i.e. a set $I$ s.t. for any two $i,jin I$, there is some $k_alphain I$ s.t. $iRk_alpha R...Rk_beta j$.
– palmpo
Jul 28 at 21:10
I apologize for all these questions but I want to know what I can get away with, excluding choice. I don't know much about choice and it seems unintuitive like cheating, since you get something for free. Choice gives us a single well-order (possibly out of many) but at least for a fixed well-order, the $B_i$'s defined are unique. Is there another definition of $B_i$'s that disjointize a set without choice, not caring about uniqueness of the $B_i$'s generated?
– palmpo
Jul 28 at 21:20
Unless I'm mistaken, you do indeed need a well-ordering. I skipped some steps (which I will edit in after writing this comment), but the actual process by which one constructs the sets $B_i$ is called transfinite induction. It is a generalization of the usual mathematical induction one encounters with the natural numbers, and requires the set being inducted over to be well-ordered.
– D. Brogan
Jul 28 at 21:20
I understand the hesitation to use choice. At first it does seem like cheating, what with all the unintuitive results such as the Banach-Tarski Paradox or even the Well-Ordering Theorem following from it. However, even if one wishes to avoid it, this is an inherently set-theoretic question; moreover one in which we are dealing with arbitrary cardinalities. Choice is almost guaranteed to appear under those conditions.
– D. Brogan
Jul 28 at 21:24
 |Â
show 2 more comments
up vote
6
down vote
accepted
The property of $mathbbN$ which allows us to do what you want is the fact that it is well-ordered. For those not familiar:
Definition: An order $leqslant$ on a set $A$ is a well-ordering if it satisfies the following conditions:
- $aleqslant a$ for each $ain A$ (reflexivity),
- For each $a,bin A$, either $aleqslant b$ or $bleqslant a$ holds (comperability),
- $aleqslant b$ and $bleqslant a$ implies $a=b$ for each $a,bin A$ (symmetry),
- $aleqslant b$ and $bleqslant c$ implies $aleqslant c$ for each $a,b,cin A$ (transitivity),
- For each $Ssubseteq A$, $S$ has a least element; that is, there is some $sin S$ such that $sleqslant a$ for each $ain S$ (well-ordering).
There is a theorem, the Well-Ordering Theorem, which is equivalent to the axiom of choice, which states that every set can be well-ordered. Using this theorem we may "disjointize" any collection of sets.
Let $mathcal A= A_i_iin I$ be a collection of sets indexed by the the set $I$. We will construct the sets $B_i$, which have the desired property that $$bigcup_iin I B_i=bigcup_iin I A_i,$$ using a process called transfinite induction. Let $leqslant$ be a well-ordering of $I$. Let $a$ be the least element of $I$ and write $B_a=A_a.$ Now let $iin I$ be such that for each $j< i$ we have constructed pairwise disjoint sets $B_j$ from the collection $mathcalA.$ Then let $B_i=A_isetminus bigcup_j<i A_j$. It is clear that $B_icap B_j=varnothing$ for each $j<i$. Since $B_isubseteq A_i$ for each $iin I$, we have $$bigcup_iin I B_isubseteqbigcup_iin I A_i.$$ To see the reverse inclusion, observe that for each $xinbigcup_iin I A_i$, the set $C_x=iin I;subseteq I$ has a least element $j$ and that $xin B_j,$ so $$bigcup_iin I B_isupseteqbigcup_iin I A_i,$$ giving equality of the two sets.
At first it may seem that transfinite induction works even with sets which are only totally ordered, such as the closed unit interval $[0,1].$ However, this is not the case. To see this, I recommend reading the proof that transfinite induction works. Intuitively, without a well-ordering, one has trouble "moving on to the next element" while performing the induction. I used the first chapter of Munkres' Topology, but there may be better sources. I enjoyed Munkres because he goes through a good amount of material, and the supplementary exercises at the end of nearly every chapter are challenging and illuminating.
answered Jul 28 at 19:04
D. Brogan
463311
1
Thanks for mentioning what's specifically needed. If I'm on the right track, your defining of $B_i$ for any $iin I$ requires $B_j$ already defined for $j<i$ and eventually we hit $B_m$ for the least element $m$ of $I$, which we need well-ordering property to exist for infinite sets $I$ (else induct on $I$ finite). And the motivation would be that for any $B_i$, you want to exclude ("set-differencing") at least all the sets that were excluded for defining $B_j$, $j<i$.
– palmpo
Jul 28 at 21:03
Now that I think of it, it seems like if we have a path from a starting element to an ending element, we don't need well-ordering property. i.e. a set $I$ s.t. for any two $i,jin I$, there is some $k_alphain I$ s.t. $iRk_alpha R...Rk_beta j$.
– palmpo
Jul 28 at 21:10
I apologize for all these questions but I want to know what I can get away with, excluding choice. I don't know much about choice and it seems unintuitive like cheating, since you get something for free. Choice gives us a single well-order (possibly out of many) but at least for a fixed well-order, the $B_i$'s defined are unique. Is there another definition of $B_i$'s that disjointize a set without choice, not caring about uniqueness of the $B_i$'s generated?
– palmpo
Jul 28 at 21:20
Unless I'm mistaken, you do indeed need a well-ordering. I skipped some steps (which I will edit in after writing this comment), but the actual process by which one constructs the sets $B_i$ is called transfinite induction. It is a generalization of the usual mathematical induction one encounters with the natural numbers, and requires the set being inducted over to be well-ordered.
– D. Brogan
Jul 28 at 21:20
I understand the hesitation to use choice. At first it does seem like cheating, what with all the unintuitive results such as the Banach-Tarski Paradox or even the Well-Ordering Theorem following from it. However, even if one wishes to avoid it, this is an inherently set-theoretic question; moreover one in which we are dealing with arbitrary cardinalities. Choice is almost guaranteed to appear under those conditions.
– D. Brogan
Jul 28 at 21:24
 |Â
show 2 more comments
up vote
6
down vote
accepted
up vote
6
down vote
accepted
The property of $mathbbN$ which allows us to do what you want is the fact that it is well-ordered. For those not familiar:
Definition: An order $leqslant$ on a set $A$ is a well-ordering if it satisfies the following conditions:
- $aleqslant a$ for each $ain A$ (reflexivity),
- For each $a,bin A$, either $aleqslant b$ or $bleqslant a$ holds (comperability),
- $aleqslant b$ and $bleqslant a$ implies $a=b$ for each $a,bin A$ (symmetry),
- $aleqslant b$ and $bleqslant c$ implies $aleqslant c$ for each $a,b,cin A$ (transitivity),
- For each $Ssubseteq A$, $S$ has a least element; that is, there is some $sin S$ such that $sleqslant a$ for each $ain S$ (well-ordering).
There is a theorem, the Well-Ordering Theorem, which is equivalent to the axiom of choice, which states that every set can be well-ordered. Using this theorem we may "disjointize" any collection of sets.
Let $mathcal A= A_i_iin I$ be a collection of sets indexed by the the set $I$. We will construct the sets $B_i$, which have the desired property that $$bigcup_iin I B_i=bigcup_iin I A_i,$$ using a process called transfinite induction. Let $leqslant$ be a well-ordering of $I$. Let $a$ be the least element of $I$ and write $B_a=A_a.$ Now let $iin I$ be such that for each $j< i$ we have constructed pairwise disjoint sets $B_j$ from the collection $mathcalA.$ Then let $B_i=A_isetminus bigcup_j<i A_j$. It is clear that $B_icap B_j=varnothing$ for each $j<i$. Since $B_isubseteq A_i$ for each $iin I$, we have $$bigcup_iin I B_isubseteqbigcup_iin I A_i.$$ To see the reverse inclusion, observe that for each $xinbigcup_iin I A_i$, the set $C_x=iin I;subseteq I$ has a least element $j$ and that $xin B_j,$ so $$bigcup_iin I B_isupseteqbigcup_iin I A_i,$$ giving equality of the two sets.
At first it may seem that transfinite induction works even with sets which are only totally ordered, such as the closed unit interval $[0,1].$ However, this is not the case. To see this, I recommend reading the proof that transfinite induction works. Intuitively, without a well-ordering, one has trouble "moving on to the next element" while performing the induction. I used the first chapter of Munkres' Topology, but there may be better sources. I enjoyed Munkres because he goes through a good amount of material, and the supplementary exercises at the end of nearly every chapter are challenging and illuminating.
answered Jul 28 at 19:04
D. Brogan
463311
The property of $mathbbN$ which allows us to do what you want is the fact that it is well-ordered. For those not familiar:
Definition: An order $leqslant$ on a set $A$ is a well-ordering if it satisfies the following conditions:
- $aleqslant a$ for each $ain A$ (reflexivity),
- For each $a,bin A$, either $aleqslant b$ or $bleqslant a$ holds (comperability),
- $aleqslant b$ and $bleqslant a$ implies $a=b$ for each $a,bin A$ (symmetry),
- $aleqslant b$ and $bleqslant c$ implies $aleqslant c$ for each $a,b,cin A$ (transitivity),
- For each $Ssubseteq A$, $S$ has a least element; that is, there is some $sin S$ such that $sleqslant a$ for each $ain S$ (well-ordering).
There is a theorem, the Well-Ordering Theorem, which is equivalent to the axiom of choice, which states that every set can be well-ordered. Using this theorem we may "disjointize" any collection of sets.
Let $mathcal A= A_i_iin I$ be a collection of sets indexed by the the set $I$. We will construct the sets $B_i$, which have the desired property that $$bigcup_iin I B_i=bigcup_iin I A_i,$$ using a process called transfinite induction. Let $leqslant$ be a well-ordering of $I$. Let $a$ be the least element of $I$ and write $B_a=A_a.$ Now let $iin I$ be such that for each $j< i$ we have constructed pairwise disjoint sets $B_j$ from the collection $mathcalA.$ Then let $B_i=A_isetminus bigcup_j<i A_j$. It is clear that $B_icap B_j=varnothing$ for each $j<i$. Since $B_isubseteq A_i$ for each $iin I$, we have $$bigcup_iin I B_isubseteqbigcup_iin I A_i.$$ To see the reverse inclusion, observe that for each $xinbigcup_iin I A_i$, the set $C_x=iin I;subseteq I$ has a least element $j$ and that $xin B_j,$ so $$bigcup_iin I B_isupseteqbigcup_iin I A_i,$$ giving equality of the two sets.
At first it may seem that transfinite induction works even with sets which are only totally ordered, such as the closed unit interval $[0,1].$ However, this is not the case. To see this, I recommend reading the proof that transfinite induction works. Intuitively, without a well-ordering, one has trouble "moving on to the next element" while performing the induction. I used the first chapter of Munkres' Topology, but there may be better sources. I enjoyed Munkres because he goes through a good amount of material, and the supplementary exercises at the end of nearly every chapter are challenging and illuminating.
answered Jul 28 at 19:04
D. Brogan
463311
edited Jul 28 at 21:39
answered Jul 28 at 19:04
D. Brogan
463311
answered Jul 28 at 19:04
D. Brogan
463311
answered Jul 28 at 19:04
D. Brogan
463311
463311
1
Thanks for mentioning what's specifically needed. If I'm on the right track, your defining of $B_i$ for any $iin I$ requires $B_j$ already defined for $j<i$ and eventually we hit $B_m$ for the least element $m$ of $I$, which we need well-ordering property to exist for infinite sets $I$ (else induct on $I$ finite). And the motivation would be that for any $B_i$, you want to exclude ("set-differencing") at least all the sets that were excluded for defining $B_j$, $j<i$.
– palmpo
Jul 28 at 21:03
Now that I think of it, it seems like if we have a path from a starting element to an ending element, we don't need well-ordering property. i.e. a set $I$ s.t. for any two $i,jin I$, there is some $k_alphain I$ s.t. $iRk_alpha R...Rk_beta j$.
– palmpo
Jul 28 at 21:10
I apologize for all these questions but I want to know what I can get away with, excluding choice. I don't know much about choice and it seems unintuitive like cheating, since you get something for free. Choice gives us a single well-order (possibly out of many) but at least for a fixed well-order, the $B_i$'s defined are unique. Is there another definition of $B_i$'s that disjointize a set without choice, not caring about uniqueness of the $B_i$'s generated?
– palmpo
Jul 28 at 21:20
Unless I'm mistaken, you do indeed need a well-ordering. I skipped some steps (which I will edit in after writing this comment), but the actual process by which one constructs the sets $B_i$ is called transfinite induction. It is a generalization of the usual mathematical induction one encounters with the natural numbers, and requires the set being inducted over to be well-ordered.
– D. Brogan
Jul 28 at 21:20
I understand the hesitation to use choice. At first it does seem like cheating, what with all the unintuitive results such as the Banach-Tarski Paradox or even the Well-Ordering Theorem following from it. However, even if one wishes to avoid it, this is an inherently set-theoretic question; moreover one in which we are dealing with arbitrary cardinalities. Choice is almost guaranteed to appear under those conditions.
– D. Brogan
Jul 28 at 21:24
 |Â
show 2 more comments
1
Thanks for mentioning what's specifically needed. If I'm on the right track, your defining of $B_i$ for any $iin I$ requires $B_j$ already defined for $j<i$ and eventually we hit $B_m$ for the least element $m$ of $I$, which we need well-ordering property to exist for infinite sets $I$ (else induct on $I$ finite). And the motivation would be that for any $B_i$, you want to exclude ("set-differencing") at least all the sets that were excluded for defining $B_j$, $j<i$.
– palmpo
Jul 28 at 21:03
Now that I think of it, it seems like if we have a path from a starting element to an ending element, we don't need well-ordering property. i.e. a set $I$ s.t. for any two $i,jin I$, there is some $k_alphain I$ s.t. $iRk_alpha R...Rk_beta j$.
– palmpo
Jul 28 at 21:10
I apologize for all these questions but I want to know what I can get away with, excluding choice. I don't know much about choice and it seems unintuitive like cheating, since you get something for free. Choice gives us a single well-order (possibly out of many) but at least for a fixed well-order, the $B_i$'s defined are unique. Is there another definition of $B_i$'s that disjointize a set without choice, not caring about uniqueness of the $B_i$'s generated?
– palmpo
Jul 28 at 21:20
Unless I'm mistaken, you do indeed need a well-ordering. I skipped some steps (which I will edit in after writing this comment), but the actual process by which one constructs the sets $B_i$ is called transfinite induction. It is a generalization of the usual mathematical induction one encounters with the natural numbers, and requires the set being inducted over to be well-ordered.
– D. Brogan
Jul 28 at 21:20
I understand the hesitation to use choice. At first it does seem like cheating, what with all the unintuitive results such as the Banach-Tarski Paradox or even the Well-Ordering Theorem following from it. However, even if one wishes to avoid it, this is an inherently set-theoretic question; moreover one in which we are dealing with arbitrary cardinalities. Choice is almost guaranteed to appear under those conditions.
– D. Brogan
Jul 28 at 21:24
1
1
Thanks for mentioning what's specifically needed. If I'm on the right track, your defining of $B_i$ for any $iin I$ requires $B_j$ already defined for $j<i$ and eventually we hit $B_m$ for the least element $m$ of $I$, which we need well-ordering property to exist for infinite sets $I$ (else induct on $I$ finite). And the motivation would be that for any $B_i$, you want to exclude ("set-differencing") at least all the sets that were excluded for defining $B_j$, $j<i$.
– palmpo
Jul 28 at 21:03
Thanks for mentioning what's specifically needed. If I'm on the right track, your defining of $B_i$ for any $iin I$ requires $B_j$ already defined for $j<i$ and eventually we hit $B_m$ for the least element $m$ of $I$, which we need well-ordering property to exist for infinite sets $I$ (else induct on $I$ finite). And the motivation would be that for any $B_i$, you want to exclude ("set-differencing") at least all the sets that were excluded for defining $B_j$, $j<i$.
– palmpo
Jul 28 at 21:03
Now that I think of it, it seems like if we have a path from a starting element to an ending element, we don't need well-ordering property. i.e. a set $I$ s.t. for any two $i,jin I$, there is some $k_alphain I$ s.t. $iRk_alpha R...Rk_beta j$.
– palmpo
Jul 28 at 21:10
Now that I think of it, it seems like if we have a path from a starting element to an ending element, we don't need well-ordering property. i.e. a set $I$ s.t. for any two $i,jin I$, there is some $k_alphain I$ s.t. $iRk_alpha R...Rk_beta j$.
– palmpo
Jul 28 at 21:10
I apologize for all these questions but I want to know what I can get away with, excluding choice. I don't know much about choice and it seems unintuitive like cheating, since you get something for free. Choice gives us a single well-order (possibly out of many) but at least for a fixed well-order, the $B_i$'s defined are unique. Is there another definition of $B_i$'s that disjointize a set without choice, not caring about uniqueness of the $B_i$'s generated?
– palmpo
Jul 28 at 21:20
I apologize for all these questions but I want to know what I can get away with, excluding choice. I don't know much about choice and it seems unintuitive like cheating, since you get something for free. Choice gives us a single well-order (possibly out of many) but at least for a fixed well-order, the $B_i$'s defined are unique. Is there another definition of $B_i$'s that disjointize a set without choice, not caring about uniqueness of the $B_i$'s generated?
– palmpo
Jul 28 at 21:20
Unless I'm mistaken, you do indeed need a well-ordering. I skipped some steps (which I will edit in after writing this comment), but the actual process by which one constructs the sets $B_i$ is called transfinite induction. It is a generalization of the usual mathematical induction one encounters with the natural numbers, and requires the set being inducted over to be well-ordered.
– D. Brogan
Jul 28 at 21:20
Unless I'm mistaken, you do indeed need a well-ordering. I skipped some steps (which I will edit in after writing this comment), but the actual process by which one constructs the sets $B_i$ is called transfinite induction. It is a generalization of the usual mathematical induction one encounters with the natural numbers, and requires the set being inducted over to be well-ordered.
– D. Brogan
Jul 28 at 21:20
I understand the hesitation to use choice. At first it does seem like cheating, what with all the unintuitive results such as the Banach-Tarski Paradox or even the Well-Ordering Theorem following from it. However, even if one wishes to avoid it, this is an inherently set-theoretic question; moreover one in which we are dealing with arbitrary cardinalities. Choice is almost guaranteed to appear under those conditions.
– D. Brogan
Jul 28 at 21:24
I understand the hesitation to use choice. At first it does seem like cheating, what with all the unintuitive results such as the Banach-Tarski Paradox or even the Well-Ordering Theorem following from it. However, even if one wishes to avoid it, this is an inherently set-theoretic question; moreover one in which we are dealing with arbitrary cardinalities. Choice is almost guaranteed to appear under those conditions.
– D. Brogan
Jul 28 at 21:24
 |Â
show 2 more comments
up vote
3
down vote
To complement D. Brogan's excellent answer, note that if we assume that every indexed family of sets can be disjointized, then we can prove the axiom of choice. So "every union can be disjointized" is an equivalent formulation of AC.
To see this, suppose we have a family $A_i_iin I$ of disjoint non-empty sets, and we want to find $b_i_iin I$ such that $b_iin A_i$. (This is one of several well-known equivalent formulations of the axiom of choice).
Without loss of generality we can assume that $I$ is disjoint from each of the $A_i$s.
Now consider the family $$ i,b mid iin I, bin A_i $$
and disjointize it. Let $b_i$ be the unique $bin A_i$ such that $i,b$ is in the disjointized family.
answered Jul 28 at 20:01
Henning Makholm
225k16290516
1
Thanks for the additional info, I keep encountering AC when I have to deal with sets without any structure and it just solves all the problems away.
– palmpo
Jul 28 at 21:24
add a comment |Â
up vote
3
down vote
To complement D. Brogan's excellent answer, note that if we assume that every indexed family of sets can be disjointized, then we can prove the axiom of choice. So "every union can be disjointized" is an equivalent formulation of AC.
To see this, suppose we have a family $A_i_iin I$ of disjoint non-empty sets, and we want to find $b_i_iin I$ such that $b_iin A_i$. (This is one of several well-known equivalent formulations of the axiom of choice).
Without loss of generality we can assume that $I$ is disjoint from each of the $A_i$s.
Now consider the family $$ i,b mid iin I, bin A_i $$
and disjointize it. Let $b_i$ be the unique $bin A_i$ such that $i,b$ is in the disjointized family.
answered Jul 28 at 20:01
Henning Makholm
225k16290516
1
Thanks for the additional info, I keep encountering AC when I have to deal with sets without any structure and it just solves all the problems away.
– palmpo
Jul 28 at 21:24
add a comment |Â
up vote
3
down vote
up vote
3
down vote
To complement D. Brogan's excellent answer, note that if we assume that every indexed family of sets can be disjointized, then we can prove the axiom of choice. So "every union can be disjointized" is an equivalent formulation of AC.
To see this, suppose we have a family $A_i_iin I$ of disjoint non-empty sets, and we want to find $b_i_iin I$ such that $b_iin A_i$. (This is one of several well-known equivalent formulations of the axiom of choice).
Without loss of generality we can assume that $I$ is disjoint from each of the $A_i$s.
Now consider the family $$ i,b mid iin I, bin A_i $$
and disjointize it. Let $b_i$ be the unique $bin A_i$ such that $i,b$ is in the disjointized family.
answered Jul 28 at 20:01
Henning Makholm
225k16290516
To complement D. Brogan's excellent answer, note that if we assume that every indexed family of sets can be disjointized, then we can prove the axiom of choice. So "every union can be disjointized" is an equivalent formulation of AC.
To see this, suppose we have a family $A_i_iin I$ of disjoint non-empty sets, and we want to find $b_i_iin I$ such that $b_iin A_i$. (This is one of several well-known equivalent formulations of the axiom of choice).
Without loss of generality we can assume that $I$ is disjoint from each of the $A_i$s.
Now consider the family $$ i,b mid iin I, bin A_i $$
and disjointize it. Let $b_i$ be the unique $bin A_i$ such that $i,b$ is in the disjointized family.
answered Jul 28 at 20:01
Henning Makholm
225k16290516
answered Jul 28 at 20:01
Henning Makholm
225k16290516
answered Jul 28 at 20:01
Henning Makholm
225k16290516
answered Jul 28 at 20:01
Henning Makholm
225k16290516
225k16290516
1
Thanks for the additional info, I keep encountering AC when I have to deal with sets without any structure and it just solves all the problems away.
– palmpo
Jul 28 at 21:24
add a comment |Â
1
Thanks for the additional info, I keep encountering AC when I have to deal with sets without any structure and it just solves all the problems away.
– palmpo
Jul 28 at 21:24
1
1
Thanks for the additional info, I keep encountering AC when I have to deal with sets without any structure and it just solves all the problems away.
– palmpo
Jul 28 at 21:24
Thanks for the additional info, I keep encountering AC when I have to deal with sets without any structure and it just solves all the problems away.
– palmpo
Jul 28 at 21:24
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%2f2865467%2fto-what-extent-can-i-disjointize-an-arbitary-collection-of-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
The $B_i$ of the second method exist, though you cannot list them in general. The arbitrary union of sets is well defined as well as the difference of two sets.
– Javi
Jul 28 at 18:35