Modular Arithmetic

[Treadstone]

did modular addition and multiplication today in my proofs II class and i was wondering if there are modular set products. I was thinking since mod operations create equivilance classes, which are sets, if there were an special things to do with mod set products or if they even exist.

[matt grime]

What relation do you think "modular set products" ought ot have to modular arithmetic? I mean are you trying to generalize a perceived relationship between set products and ordinary arithemetic, and if so what relationship is that? (This isn't vacuous, by the way, but I'd like to see what you think you're getting at)

[Treadstone]

i dont know, lol, i was just thinking...i'll think some more and see what i come up with...but for now...

 

modular operation create equivalence classes, which are partitians of larger sets. Set products are, in terms of Cartesian products (and this could be wrong), are relations on sets where by 1 set is made dependent on another set, ie XxY yeilds elements that are (x,y) like in a function where y is dependent on x.

 

So a modular set production would take a large set, put it into partitians and then relate the partitians (set producting the mod)? Or would it partitian relations (moding the set product)? This is where i dont know if what i thinking is interesting and novel or useless and nonsensical .....i'll post more when i get to thinking about it more, i gotta head to proofs II class

[matt grime]

I don't think that it is true to say that the y in (x,y) is dependent on x. Firstly, I don't understand what you mean by dependent on in this context. The product of two sets is defined for all sets, and is the collection of all ordered pairs of elements, so you give me (?,y) and I can't tell you what ? is except that it is some element of X, and moreover that such a pair exists for every ? in X.

 

You appear to be getting at partitions of sets. Which is equivalence relations. One such equivalence relation is modulo arthmetic. You're just partitioning a set, it's not called modulo product as modulo stuff is a special example of this kind of behaviour.

 

What I thought you might be getting at is if X and Y are two finite sets of cardinality p and q respectively, then the cardinality of XxY is the product of p and q.

[Treadstone]

with the (x,y) dependency thing, i might be mixing up notations...for example, in the ordered pair (x,y) as it pertains the function f(x)=y, y would be dependent on x and through the relation f you would get the pair (x,y). Perhaps this is not the same as set product.

 

But there is modulo arithmetic, such as addition of equivalence classes. If we define the operation (+3) as modular addition of eq classes charactorized by the remainder after division by 3 or a multple of 3 then

 

[1] (+3) [2] = [1 + 2] = [3] = [0]

 

because [1] = {...,-5,-2,1,4,2...}

[2] = {...,-4,-1,2,5,...}

[0] = {...,-6,-3,0,3,6,...}

 

notice that [0] = [3], [6], [9] or any other class [3n]

you can construct similar equality lists for [2] and [1].

 

At any rate, i was trying to figure out that since there are modular arithmetic operation like the mod+, and mod* if there was a mod set product....did i clearify my question better?

[matt grime]

A function is a subset of the product XxY but certainly isn't all XxY.

 

A product is not a function.

 

You've still not given me any way of understanding what it is you think that ordinary multiplication has to do with set products that makes this generalization reasonable. Ie what are you trying to abstract to the modulo case.

 

in modulo arithmetic when you add together two elements x+y you need to demonstrate the answer is independent of whichever choice of representative of the equivalence class you choose.

 

What if X and Y weren't sets of integers. what would you want XmodxY to even mean?

[Treadstone]

i dont think you're understanding my purpose for the post lol....simply put after being exposed to modular addtion, such as the example above, and modular multiplication...i was wondering if there is modular set product and if so what it did.

[matt grime]

And I thnk it is valid to ask why you think there ought to be a modular set product.

 

What relation between the product of integers and the product of sets do you think exists? (There is one, but I want to know what you think).

 

Also, no one refers to 2*3 = 1 mod 5 as being the modular product of 2 and 3, they would say the product of 2 and 3 mod 5 is, and you can mod out anything by anything pretty much if you felt like it.

 

For instance the product of the circle S^1 with the unit interval [0,1] modulo the relation (x,0) ~ (y,0) for all x,y in S^1 and (x,1)~(y,1) for all x,y in S^1 is essentially the same as the unit sphere in R^3.

[Treadstone]

What relation between the product of integers and the product of sets do you think exists?

 

let me think about that...i'm glad you told me there is one...i wasnt sure if you were trying to make me think of one, knowing there wasnt, just to shoot me down, lol

[matt grime]

To whet your appetite some more, how about this?

 

 

http://www.dpmms.cam.ac.uk/~wtg10/commutative.html

[Treadstone]

Most people would probably say that 395x428 and 428x395 both count the number of points in a 395-by-428 rectangular grid. If you rotate such a grid through 90 degrees then you turn it into a 428-by-395 rectangular grid but you clearly leave the number of points unchanged.

 

this is similar to a lot of proofs that Euclid used before calculus and other rigorous type math was found.

 

If A is a set of cardinality m and B is a set of cardinality n, then the Cartesian product AxB has cardinality mn

 

so then...a set which contains all the elements of the product of two sets would have a cardinality equal to the procuct of the original two sets. So that kinda makes sense...graphicly a set product has the dimensions equal to that of the lengths of the sets that made it up (well in really loose terms anyway). So the overall contents of that 'set product shape' would have an area, which we could probably call its contents, equal to that of the product of the lengths of the sets that made it up.....damn and now i have to go to work, i'll look over the rest when i get back tonight.

 

Thanks!

[matt grime]

If the sets are finite.

[Treadstone]

alright, let me take a wack at it...though it could be more questions and thoughts than actual answers..edit**as i write this i become less and less sure about it, lol, please be kind...

 

the product of integers can be defined as...

 

na=a+a+a+a...n times so 5a=a+a+a+a+a

 

So can we define a set product similarly? AxB would be...B+B+B+B...A times? what is B+B? I dont think there is a direct relation such as this because i dont think B+B makes any sense.

 

So...AxB = {(a1,b) , (a2,b) , ... , (ak,b)} where k is the cardinality of A (thinking that that the cardinality is how many things are in A) and b is an element of B, though in this case none of the b's equal each other (i didnt want to associate a1 and b1 but rather the first element in A, a1, with some element in B, b)

 

So...to relate that to modulo operations...let (*d) = modulo multiplication with the base of d, and let (x*d) be modulo set product with a base of d.

 

m(*d)n = n+n+n+n+...+n m times then put into its equivalence class that coresponds

to d which would be...

(n+n+n+n+...+n m times)/d + q = mn | m,n,d,q are intergers and q is the eq class

 

A(x*d)B = {(a1,b) , (a2,b) , ... , (ak,b)} where k is the cardinality of A, then put into

eq classes that corespond with d...but what would that

mean? would d need to be a set, D? so the eq classes would

be based on another set product of the (AxB)xD? Now i'm

kinda stuck and i have to get going to my OR class...

 

Thanks for helping me with this, i really appreciate it. Just out of curiousity, what is your math background, you remind me of a prof..which isnt a bad thing

 

Nathan

[matt grime]

na=a+a+a+a...n times so 5a=a+a+a+a+a

 

So can we define a set product similarly? AxB would be...B+B+B+B...A times? what is B+B? I dont think there is a direct relation such as this because i dont think B+B makes any sense.

 

Indeed it doesn't since you've not defined what you think + means for sets. There is the idea of Union of sets. What do you know about Rings? Sets form a ring under the operations union and symmetric difference' date=' but union is actually the multiplication operation. and symmetric difference the addition.

 

 

 

So...AxB = {(a1,b) , (a2,b) , ... , (ak,b)} where k is the cardinality of A (thinking that that the cardinality is how many things are in A) and b is an element of B, though in this case none of the b's equal each other (i didnt want to associate a1 and b1 but rather the first element in A, a1, with some element in B, b)

 

 

Firstly that isn't AxB, that is some subset of AxB. And if you didnt' want the b's to all be equal then you should have used different letters. The set you've written down clearly has cardinality k, not k*card(B) as would be required.

 

Also, sets aren't ordered. There is no "first" element of a set in any canonical sense.

 

So...to relate that to modulo operations...let (*d) = modulo multiplication with the base of d, and let (x*d) be modulo set product with a base of d.

 

As i keep saying, one doesn't say the "modulo multiplication", one says "multiplication modulo". the modulo comes aftewards if you like. you've not defined modulo set product so how can you talk about it as if you had?

 

 

 

m(*d)n = n+n+n+n+...+n m times then put into its equivalence class that coresponds

to d which would be...

(n+n+n+n+...+n m times)/d + q = mn | m,n,d,q are intergers and q is the eq class

 

A(x*d)B = {(a1,b) , (a2,b) , ... , (ak,b)} where k is the cardinality of A, then put into

eq classes that corespond with d...but what would that

mean? would d need to be a set, D? so the eq classes would

be based on another set product of the (AxB)xD? Now i'm

kinda stuck and i have to get going to my OR class...

 

Thanks for helping me with this, i really appreciate it. Just out of curiousity, what is your math background, you remind me of a prof..which isnt a bad thing

 

Nathan

 

 

 

If I remind you of a prof there may be some reason for that, though I am not a professor.

 

 

You're hung up on multiplying sets as if they're numbers. They aren't numbers. Just because two things have a similar name doesn't mean there is anything more than a formal similarity between them.

 

I can take two sets, take their product, and then take the "mod an equivalence relation", I can take them "mod a relation" anyway. What is important in modulo arithmetic (forgetting the set stuff) is that taking the equivalence classes preserves the algebraic operations and is independent of the choice of representative of the equivalence class. That is

 

[a]=[ab]

 

 

In order for this to make sense in terms of sets in a direct correlation I would need a multiplication of sets, and an addition of sets to preserve under the relation. But set product isn't it! the product of sets isn't a multiplication of sets in the algebraic sense: it has no identity element.

 

So, you're mixing up a couple of ideas here.

[Treadstone]

There is the idea of Union of sets. What do you know about Rings? Sets form a ring under the operations union and symmetric difference, but union is actually the multiplication operation. and symmetric difference the addition.

 

i am familar with unions of sets and we just started talking about rings so i know a little about the + and * used in rings, though they dont have to be the same + and * as in interger stuff. Basicly, i know the def'n of rings, the 5 ring axioms, and a little about morphisms (homo and iso)...but thats about it.

 

In order for this to make sense in terms of sets in a direct correlation I would need a multiplication of sets, and an addition of sets to preserve under the relation.

 

thinking about rings and such, if i define a ring as (AxB, +,*,z) such that the + and * put items from AxB into eq classes and still satisfy the ring axioms, would that be more along the right track of figureing out set product modulo? Oh, i write the z for 0 so i make sure not to mix up the 'zero' item in the ring with the integer 0....and you still havent told me your math background

[matt grime]

You can and should always write 0 for the additive identity in any ring.

 

I don't think you're going in a the right direction at all. The product of arbitrary sets has nothing to do with multiplication really.

Moreover, multiplication of integers modulo some number does not in itself define any equivalence classes as your last post seems to imply you think.

 

The equivalence classes are defined first, then we show that these equivalence classses inherit the structure of a ring where the * comes from the * in the integers. We are not actually taking any _set_ products at all.

 

You do this a lot in mathematics, and you'll often hear us say two things are equal modulo a third as a short hand of saying two things are the same up to their differences, where their differences aren't important.

 

For instance, suppose we try to solve a set of simultaneous equations in matric form Ax=b, and suppose that A is singular, and that there are many solutions. Let u and v be two solutions, then A(u-v)=b-b=0 and we might say that any two solutions are equivalent modulo the "kernel" of A. (The kernel being the set of solutions to Ax=0).

 

You know about linear algebra right? Well, you can show that the kernel of A is a vector space, and that modulo the kernel all answers are equivalent.

[Treadstone]

i am proficient in linear algebra...though forigve me if this post is short, as i just finsihed doing 6 sections worth of diff eq and proofs homework and my brain in a little fried. We just started doing rings, could you give me something to look for in the lectures that might help me figure out what set product modulo is?

[matt grime]

You can take any set and tak it modulo something. The result is a set of sets of equivalence classes.

 

It may happen to be that that original set is a product of two sets, but the result is not a modulo set product, it is the product of sets modulo something, and the "product" has nothing a priori to do with the "modulo" just as it has nothing to do with the product in modulo arithmetic!

 

So I can't give you what you're after because it doesn't exist.

 

At the risk of repeating myself, when you do [2]*[3]=[1] mod(5) you are not taking the cartesian product of the sets of equivalence classes of 2 and 3 and equating

them.

 

modding out by an equivalence relation happens all the time. You may do something like it in the ring theory course if you were to say take the ring of polynomials in one variable and mod out by an ideal.