If R1 and R2 are (Boolean) rings, then I can show that the set of all finite, disjoint unions of Cartesian products A1 X A2, A1 in R1, A2 in R2, is a (Boolean) ring. Then by induction it is simple to show that if R1, ..., Rn are rings then the set of all finite, disjoint unions of Cartesian products
(...(A1 X A2) X A3 ) ... X An), A1 in R1, ..., An in Rn
is a ring. What I don't understand is how one then makes the leap to inferring that the set of all finite, disjoint union of Cartesian products of the form A1 X A2 X ... X An is also a ring (in fact the "same" ring?) Clearly there exists a bijection between say the ordered triplet ((x1,x2),x3) and the ordered triplet (x1,x2,x3) but I don't see that this by itself is enough to show the necessary equivalence without using non-rigorous, hand waving arguments.
Can anyone fill in the missing piece of logic here? (I've never taken an algebra class)
On Mon, 1 Dec 2008, sto wrote: > If R1 and R2 are (Boolean) rings, then I can show that the set of all finite, > disjoint unions of Cartesian products A1 X A2, A1 in R1, A2 in R2, is a > (Boolean) ring. Then by induction it is simple to show that if R1, ..., Rn > are rings then the set of all finite, disjoint unions of Cartesian products
> (...(A1 X A2) X A3 ) ... X An), A1 in R1, ..., An in Rn
> is a ring. What I don't understand is how one then makes the leap to > inferring that the set of all finite, disjoint union of Cartesian products of > the form A1 X A2 X ... X An is also a ring (in fact the "same" ring?) Clearly > there exists a bijection between say the ordered triplet ((x1,x2),x3) and the > ordered triplet (x1,x2,x3) but I don't see that this by itself is enough to > show the necessary equivalence without using non-rigorous, hand waving > arguments.
One does not jump from the finite to the infinite without an infinite boost.
> Can anyone fill in the missing piece of logic here? (I've never taken an > algebra class)
Let { Rj | j in I } be a collection of rings indexed by some index set I.
Define R = prod_j Rj as the infinite product of the Rj's. and define the operations + and * pointwise. That is if x = prod_j xj in R, then define x + y = prod_j xj + prod_j yj = prod_j (xj + yj) and similar with *
Show R with the so defined operations is a ring. This is a standard algebraic construction.
prod_j Rj = { f:I -> \/_j Rj | for all j in I, f(j) in Rj }
> On Mon, 1 Dec 2008, sto wrote: >> If R1 and R2 are (Boolean) rings, then I can show that the set of all finite, >> disjoint unions of Cartesian products A1 X A2, A1 in R1, A2 in R2, is a >> (Boolean) ring. Then by induction it is simple to show that if R1, ..., Rn >> are rings then the set of all finite, disjoint unions of Cartesian products >> (...(A1 X A2) X A3 ) ... X An), A1 in R1, ..., An in Rn >> is a ring. What I don't understand is how one then makes the leap to >> inferring that the set of all finite, disjoint union of Cartesian products of >> the form A1 X A2 X ... X An is also a ring (in fact the "same" ring?) Clearly >> there exists a bijection between say the ordered triplet ((x1,x2),x3) and the >> ordered triplet (x1,x2,x3) but I don't see that this by itself is enough to >> show the necessary equivalence without using non-rigorous, hand waving >> arguments. > One does not jump from the finite to the infinite without an infinite boost.
Irrelevant: he's not doing so. You've completely misunderstood his question.
On Tue, 2 Dec 2008, Brian M. Scott wrote: > <ma...@rdrop.remove.com> wrote in >> On Mon, 1 Dec 2008, sto wrote:
>>> If R1 and R2 are (Boolean) rings, then I can show that the set of all >>> finite, disjoint unions of Cartesian products A1 X A2, A1 in R1, A2 in >>> R2, is a (Boolean) ring. Then by induction it is simple to show that >>> if R1, ..., Rn are rings then the set of all finite, disjoint unions >>> of Cartesian products
Huh? Do you mean { (a,b) | a in R1, b in R2 } is a ring? Yes it is.
>>> (...(A1 X A2) X A3 ) ... X An), A1 in R1, ..., An in Rn
>>> is a ring. What I don't understand is how one then makes the leap to >>> inferring that the set of all finite, disjoint union of Cartesian >>> products of the form A1 X A2 X ... X An is also a ring (in fact the >>> "same" ring?) Clearly there exists a bijection between say the ordered >>> triplet ((x1,x2),x3) and the ordered triplet (x1,x2,x3) but I don't >>> see that this by itself is enough to show the necessary equivalence >>> without using non-rigorous, hand waving arguments.
I don't know what you're saying. Are you asking if { ((a,b),c) | a in R1, b in R2, c in R3) } = { (a,(b,c)) | a in R1, b in R2, c in R3) }
No, they aren't equal, they're isomorphic, ie algebraic equivalent as rings.
Otherwise use the function definition of tuples. AxBxC = { f:{ 1,2,3 } -> A\/B\/C | f(1) in A, f(2) in B, f(3) in C } (x,y,z) = { (1,x), (2,y), (3,z) } (x1,.. x_n) = { (j,xj) | j = 1,.. n
>> One does not jump from the finite to the infinite without an infinite boost.
> Irrelevant: he's not doing so. You've completely misunderstood his > question.
Do you understand what he's saying? The construction I suggested still remains a way to avoid induction. What do you think he's saying?
> On Tue, 2 Dec 2008, Brian M. Scott wrote: >> <ma...@rdrop.remove.com> wrote in >>> On Mon, 1 Dec 2008, sto wrote: >>>> If R1 and R2 are (Boolean) rings, then I can show that the set of all >>>> finite, disjoint unions of Cartesian products A1 X A2, A1 in R1, A2 in >>>> R2, is a (Boolean) ring. Then by induction it is simple to show that >>>> if R1, ..., Rn are rings then the set of all finite, disjoint unions >>>> of Cartesian products > Huh? Do you mean { (a,b) | a in R1, b in R2 } is a ring? [...]
No, he doesn't.
[...]
>>> One does not jump from the finite to the infinite >>> without an infinite boost. >> Irrelevant: he's not doing so. You've completely misunderstood his >> question. > Do you understand what he's saying? [...]
Yes. With luck I might make time today to post an answer, if no one beats me to it.
> On Tue, 2 Dec 2008, Brian M. Scott wrote: >> <ma...@rdrop.remove.com> wrote in >>> On Mon, 1 Dec 2008, sto wrote:
>>>> If R1 and R2 are (Boolean) rings, then I can show that the set of >>>> all finite, disjoint unions of Cartesian products A1 X A2, A1 in R1, >>>> A2 in R2, is a (Boolean) ring. Then by induction it is simple to >>>> show that if R1, ..., Rn are rings then the set of all finite, >>>> disjoint unions of Cartesian products
> Huh? Do you mean { (a,b) | a in R1, b in R2 } is a ring? Yes it is.
Thanks.
What I mean is let's say I construct a proof (which I did) that given two rings R1 and R2 the class of finite, disjoint unions of ordered pairs (a,b), a in R1, b in R2 is a ring. Then I want to generalize that proof to the class of finite, disjoint unions of ordered n-tuples (a,b,c,d...), a in R1, b in R2, c in R3... Here n is an integer, so the n-tuple is finite.
It is simple to show by induction that the n-tuples (((a,b),c),d),...) are a ring, but these are not the same as the n-tuples (a,b,c,d...) How do you get from the induction proof for (((a,b),c),d)....) to stating that the same theorem is valid for (a,b,c,d...)?
> I don't know what you're saying. Are you asking if > { ((a,b),c) | a in R1, b in R2, c in R3) } > = > { (a,(b,c)) | a in R1, b in R2, c in R3) }
> No, they aren't equal, they're isomorphic, > ie algebraic equivalent as rings.
I think this is related to the answer to my question. After randomly digging through the library for some time, I've now settled on a book on abstract algebra which talks about homomorphisms and isomorphisms on rings. It seems to me that if I can show that there exists a bijection between (((a,b),c),d,.....) and (a,b,c,d...) that preserves set union and set difference then that would somehow be sufficient to imply that both sets "obey the same algebra", and I can then infer that (a,b,c,d...) is a ring directly from the fact that I have proved that (((a,b),c),d...) is a ring? Or maybe not.
This seems to be some kind of standard algebraic technique.
>>> One does not jump from the finite to the infinite without an infinite >>> boost.
>> Irrelevant: he's not doing so. You've completely misunderstood his >> question.
I haven't looked at the infinite case yet. Here n is strictly finite.
> > On Tue, 2 Dec 2008, Brian M. Scott wrote: >> <ma...@rdrop.remove.com> wrote in >>> On Mon, 1 Dec 2008, sto wrote: >> >>>> If R1 and R2 are (Boolean) rings, then I can show that the set of all finite, disjoint unions of Cartesian products A1 X A2, A1 in R1, A2 in R2, is a (Boolean) ring. Then by induction it is simple to show that if R1, ..., Rn are rings then the set of all finite, disjoint unions of Cartesian products >> > Huh? Do you mean { (a,b) | a in R1, b in R2 } is a ring? Yes it is. > Thanks.
What I mean is let's say I construct a proof (which I did) that given two rings R1 and R2 the class of finite, disjoint unions of ordered pairs (a,b), a in R1, b in R2 is a ring. Then I want to generalize that proof to the class of finite, disjoint unions of ordered n-tuples (a,b,c,d...), a in R1, b in R2, c in R3... Here n is an integer, so the n-tuple is finite.
It is simple to show by induction that the n-tuples (((a,b),c),d),...) are a ring, but these are not the same as the n-tuples (a,b,c,d...) How do you get from the induction proof for (((a,b),c),d)....) to stating that the same theorem is valid for (a,b,c,d...)?
>> > I don't know what you're saying. Are you asking if > { ((a,b),c) | a in R1, b in R2, c in R3) } > = > { (a,(b,c)) | a in R1, b in R2, c in R3) } > > No, they aren't equal, they're isomorphic, > ie algebraic equivalent as rings. >
I think this is related to the answer to my question. After randomly digging through the library for some time, I've now settled on a book on abstract algebra which talks about homomorphisms and isomorphisms on rings. It seems to me that if I can show that there exists a bijection between (((a,b),c),d,.....) and (a,b,c,d...) that preserves set union and set difference then that would somehow be sufficient to imply that both sets "obey the same algebra", and I can then infer that (a,b,c,d...) is a ring directly from the fact that I have proved that (((a,b),c),d...) is a ring? Or maybe not.
This seems to be some kind of standard algebraic technique.
>>> One does not jump from the finite to the infinite without an infinite boost. >> >> Irrelevant: he's not doing so. You've completely misunderstood his question.
I haven't looked at the infinite case yet. Here n is strictly finite.
sto wrote: >> Huh? Do you mean { (a,b) | a in R1, b in R2 } is a ring? Yes it is.
> What I mean is let's say I construct a proof (which I did) that given > two rings R1 and R2 the class of finite, disjoint unions of ordered > pairs (a,b), a in R1, b in R2 is a ring. Then I want to generalize that > proof to the class of finite, disjoint unions of ordered n-tuples > (a,b,c,d...), a in R1, b in R2, c in R3... Here n is an integer, so the > n-tuple is finite.
> It is simple to show by induction that the n-tuples (((a,b),c),d),...) > are a ring, but these are not the same as the n-tuples (a,b,c,d...) How > do you get from the induction proof for (((a,b),c),d)....) to stating > that the same theorem is valid for (a,b,c,d...)?
Forget that last post. After looking at some algebra books I see my question has to be stated in a completely different manner. When I refer to the term "ring" what I really should be saying is a ring of subsets of given set. I define a ring R_ as a nonempty class of subsets of a given set X which is closed under the formation of unions and differences. (I think this becomes a ring in the usual algebraic sense if we define an operation * to be set intersection and an operation + to be symmetric difference.) So the way I should have phrased my question is that I first prove the following theorem:
Thm 1: If R1_ and R2_ are rings of subsets of the sets W1 and W2 respectively, then the class R_ of all finite, disjoint unions of rectangles of the form A1 x A2, where A1 in R1_ and A2 in R2_, is a ring.
Having proved this, it then becomes easily to generalize by induction to the following result:
Thm 2:If R1_, R2_, ..., Rn_ are rings of subsets of the sets W1, W2, ..., Wn, then the class R_ of all finite, disjoint unions of rectangles of the form (...(A1 x A2) x A3) ..... x An-1) x An), is a ring.
But that is not the final result I want. The result I want is that the class of all finite disjoint union of rectangles of the form A1 x A2 x .... x An is a ring. This set is not the same as (...(A1 x A2) x A3) ..... x An-1) x An). How do I get from Thm 2 to the final result I want?
As far as I know, I could construct the bijection
p: (...(A1 x A2) x A3) ..... x An-1) x An) -> A1 x A2 x .... x An
and realize that it preserves set intersection and set difference (and everything else for that matter). But how does the fact that this bijection has these properties actually imply that the rectangles A1 x A2 x ..... x An and (...(A1 x A2) x A3) ..... x An-1) x An) share the property of being a ring?
On Tue, 2 Dec 2008, sto wrote: > William Elliot wrote: >> On Tue, 2 Dec 2008, Brian M. Scott wrote: >>>> On Mon, 1 Dec 2008, sto wrote:
> What I mean is let's say I construct a proof (which I did) that given two > rings R1 and R2 the class of finite, disjoint unions of ordered pairs (a,b), > a in R1, b in R2 is a ring. Then I want to generalize that proof to the > class of finite, disjoint unions of ordered n-tuples (a,b,c,d...), a in R1, b > in R2, c in R3... Here n is an integer, so the n-tuple is finite.
When A subset R1xR2, A is a set of ordered pairs. When A,B subset R1xR2 and A /\ B = nulset, then A \/ B is a disjoint union of ordered pairs?
When a,b in R1, u,v in R2 and (a,u) /\ (b,v) = nulset then (a,u) \/ (b,v) is a disjoint union of ordered pairs?
> It is simple to show by induction that the n-tuples (((a,b),c),d),...) are a > ring, but these are not the same as the n-tuples (a,b,c,d...) How do you get > from the induction proof for (((a,b),c),d)....) to stating that the same > theorem is valid for (a,b,c,d...)?
>> I don't know what you're saying. Are you asking if >> { ((a,b),c) | a in R1, b in R2, c in R3) } >> = >> { (a,(b,c)) | a in R1, b in R2, c in R3) }
>> No, they aren't equal, they're isomorphic, >> ie algebraic equivalent as rings.
> I think this is related to the answer to my question. After randomly > digging through the library for some time, I've now settled on a book on > abstract algebra which talks about homomorphisms and isomorphisms on > rings. It seems to me that if I can show that there exists a bijection > between (((a,b),c),d,.....) and (a,b,c,d...) that preserves set union > and set difference then that would somehow be sufficient to imply that > both sets "obey the same algebra", and I can then infer that > (a,b,c,d...) is a ring directly from the fact that I have proved that > (((a,b),c),d...) is a ring? Or maybe not.
I suppose.
> This seems to be some kind of standard algebraic technique.
What kind of rings are your talking about?
A Boolean ring is an ordinary algebraic ring with the added condition that all elements are idempotent. The elements of a Boolean ring don't have to be subsets of some set. Every Boolean ring embeds into a product of Z_2's.
Another sense of ring is a ring over a set S which is a subset of P(S) that's closed under unions and relative complements. Sigma rings over S are rings over S that are closed under countable unions.
William Elliot wrote: > What kind of rings are your talking about?
> A Boolean ring is an ordinary algebraic ring with the added > condition that all elements are idempotent. The elements of > a Boolean ring don't have to be subsets of some set. > Every Boolean ring embeds into a product of Z_2's.
> Another sense of ring is a ring over a set S which > is a subset of P(S) that's closed under unions and > relative complements. Sigma rings over S are rings > over S that are closed under countable unions.
> ----
I was talking about a ring R_ of subsets of a given set W, where a ring is a class of subsets of W that is closed under unions and set differences. I now realize there are all sorts of other rings in algebra that have nothing to do with sets. So my question has to be completely re-stated as follows:
> Forget that last post. After looking at some algebra books I see my > question has to be stated in a completely different manner. When I > refer to the term "ring" what I really should be saying is a ring of > subsets of given set. I define a ring R_ as a nonempty class of subsets > of a given set X which is closed under the formation of unions and > differences. (I think this becomes a ring in the usual algebraic sense > if we define an operation * to be set intersection and an operation + to > be symmetric difference.) So the way I should have phrased my question > is that I first prove the following theorem: > > Thm 1: If R1_ and R2_ are rings of subsets of the sets W1 and W2 > respectively, then the class R_ of all finite, disjoint unions of > rectangles of the form A1 x A2, where A1 in R1_ and A2 in R2_, is a ring. > > Having proved this, it then becomes easily to generalize by induction to > the following result: > > Thm 2:If R1_, R2_, ..., Rn_ are rings of subsets of the sets W1, W2, > ...., Wn, then the class R_ of all finite, disjoint unions of rectangles > of the form (...(A1 x A2) x A3) ..... x An-1) x An), is a ring. > > But that is not the final result I want. The result I want is that the > class of all finite disjoint union of rectangles of the form A1 x A2 x > ..... x An is a ring. This set is not the same as (...(A1 x A2) x A3) > ...... x An-1) x An). How do I get from Thm 2 to the final result I want? > > As far as I know, I could construct the bijection > > p: (...(A1 x A2) x A3) ..... x An-1) x An) -> A1 x A2 x .... x An > > where p( (a1, a2), a3), ... , an) ) = (a1, a2, ... , an) > > and realize that it preserves set intersection and set difference (and > everything else for that matter). But how does the fact that this > bijection has these properties actually imply that the rectangles A1 x > A2 x ..... x An and (...(A1 x A2) x A3) ..... x An-1) x An) share the > property of being a ring?