Notices
Results 1 to 22 of 22

Thread: What's mod up to?

  1. #1 What's mod up to? 
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    So, I promised to explain the slightly jargonistic term "up to".

    Well, superficially, it is simple; it merely refers to a sort of relaxed form of equality. In order to explains this, I am going to make it seem extremely technical, but I am only doing it this way as I thought it might amuse some of you to see something that might not be too familiar.

    The term "up to" is invariably followed by some sort of qualifier; this qualifier refers to an equivalence relation. That is, there is a relation on the set in question under which equivalent elements can be considered to be the same.

    Let me explain. An equivalence relation on a set (which may, or may not, have additional structure) is a relation that satisfies

    reflexivity:

    symmetry:

    transitivity: if and then .

    Just to calm a few nerves (perhaps) I should say straight away that equality "=" is just such a relation, as you may easily check. I will give further examples later.

    Elements of a set that are so related form what is called an equivalence class, so if, say and , then the set is referred to as, say , where the typical element is called a class representative.

    Now the property of transitivity means that no element of our total set can be in more that one equivalence class, which thus induces a partition of this set - that is, a "division" into totally disjoint subsets. Here's a familiar example: consider the positive integers exactly divisible by 2 - as an equivalence class . The partition induced thereby leaves the set "remaining". Just as each element in can be found by adding 2 to some other element in , so each element in can be likewise found. We call these the even and odd positive integers.

    Isomorphism (and its up-market friends homeomorphism, diffeomorphism etc) is an equivalence relation as defined. So I may have the expression "up to isomorphism", to mean that for the purpose at hand, isomorphic vector spaces may be regarded as equal (homeomorphic for top. spaces, diffeomorphic for diff. manifolds). I actually insisted on the slightly stronger condition of naturally isomorphic - I gave my reasons.

    The partition I referred to now becomes a partition on the universe of vector spaces, or, as I would prefer to call it, the "category" of such spaces.

    Now the set (structured or not) formed from the entire collection of classes under some equivalence relation is called the quotient set and is written . There is a bit of theory that insists that, if any function on is to be well-defined, then it must be insensitive to which element of an equivalence class it takes as input; that is for all and some , which to some extent justifies the claim that equivalent spaces may be regarded as equal.

    A propos my earlier example, there is a somewhat related notion of modulo, or "mod" for short. But this post is already over-long, let it wait.


    Reply With Quote  
     

  2.  
     

  3. #2  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Hopefully this isn't stupid but are and isomorphic?

    Could we perhaps write the equivalence class as ?


    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  4. #3  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Hopefully this isn't stupid but are and isomorphic?

    Could we perhaps write the equivalence class as ?
    Certainly they are isomorphic in the category of sets -- both are countably infinite. f(n)=n+1 is one isomorphism for n=1,3,5,...
    Reply With Quote  
     

  5. #4  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, got it. The phrase that's used in my book is "one-to-one correspondence," which makes sense with what you said.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  6. #5  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Quote Originally Posted by DrRocket
    Certainly they are isomorphic in the category of sets -- both are countably infinite. f(n)=n+1 is one isomorphism for n=1,3,5,...
    A propos this remark.....

    The set of all integers is an abelian group under the closed operation of addition, identity = 0 and with inverse defined for all .

    The set of even integers, call it , defined by exact divisibility by 2 is also a group under the same conditions (actually is a more appropriate notation), since 0/2 =0, no remainder, and any even integer added to any other is even. It is a (normal) subgroup of .

    The set of all odd integers, defined by is not a group - addition is not a closed operation. It therefore cannot be a group under addition. (Exercise - how about under multiplication?). Therefore there can be no bijective group homomorphism , ie. these sets are not isomorphic as groups.

    But they are isomorphic as sets.

    If we wanted to impress our girlfriends, we might say there is a forgetful functor U from the category of groups onto the category of sets, such that .

    But then, girls aren't that easily impressed, are they?
    Reply With Quote  
     

  7. #6  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    That definitely won't impress my girlfriend...she doesn't even like math. haha.

    The odd integers are a group under multiplication. Not sure how to really prove it though... Just using words to describe what I'm thinking, I'd say that an odd number times an odd number is an odd number because...say if we have , we have groups of or groups of , so we can go to the middle group and look at it, but it consists of an odd number of elements, so it's not evenly divisible itself...so we can't evenly divide the product. I don't know if I even needed to do that, but it's how I looked a little more into it than just looking at random examples of odd integers multiplied together.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  8. #7  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Quote Originally Posted by Chemboy
    The odd integers are a group under multiplication.
    No, it isnít. Itís only a semigroup with identity.
    Reply With Quote  
     

  9. #8  
    Forum Masters Degree organic god's Avatar
    Join Date
    Feb 2008
    Location
    London
    Posts
    567
    That definitely won't impress my girlfriend...she doesn't even like math.
    dump her ass
    everything is mathematical.
    Reply With Quote  
     

  10. #9  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    organic god, don't you think it would be pretty shallow to do that? haha.

    ok, I see that the odd integers aren't a group under multiplication. And the even integers aren't a group under multiplication either, right? Because they lack an inverse and identity, so they're a semigroup.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  11. #10  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Jane: Bad girl!! It was set as an exercise.

    Chemboy: A semigroup with identity is called a monoid. Clearly every group is a monoid, equally clearly, the converse is false,
    Reply With Quote  
     

  12. #11  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    yeah... I went on Wiki and now I have the definitions of magma, semigroup, monoid, and group in my head. I think I'm going to like abstract algebra when I get there someday...
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  13. #12  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    WARNING!!. So far, in my self-aggrandizing "tutorials"(actually they were never inyended as such), I have been very sparing in my assignment of exercises. This is about to change, as I am a firm believer in the learning-by-doing philosophy.

    So, let's return to the even and odd integers. Recall I defined an even integer as any such that can be exactly divided by 2. We will give these guys their correct collective name now as .

    I then defined the odds as . Recall I also said that, just as every even integer differs form some other even integer by some integer multiple of , likewise the odds. Well, we can give a single definition for both these equivalence classes as:

    if divides exactly, for all , then are in the same equivalence class, in this case either odd or even. This generalizes to any integer divisor. (Show)

    One writes iff .

    It can be shown that, for any integer that this induces a partition of into exactly equivalence classes (the enclosing pipes refer to absolute value, btw). This is an exercise; first show there are indeed (non-empty) disjoint sets under this partition, then that they are equivalence classes. HINT: use the fact that for any . I suppose you may also use , but be very careful with the cancellation law here.

    Supplementary: do we care about the sign on in ?

    why (not)?
    Reply With Quote  
     

  14. #13  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Give me a little time to work on this... I'm going to right now and hopefully I'll have an answer by tonight.

    EDIT: I'm having a hard time with this... I'm trying to think about how the elements of one equivalence class are found by setting the in equal to . Will that get me anywhere? I'm not at all accustomed to this type of problem yet, I need a lot more practice with them.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  15. #14  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    I'm a bit surprised to hear you are having trouble - maybe you are "over-thinking" the problems. All you need are the known rules of integer arithmetic and the definitions I gave.

    So, here's what I did for the first part, just to get you on track.

    We want to show that for any and all that the definition of modulo is satisfied.

    The integers are closed under addition. So let , an integer.

    We also know that any integer can be factored. So let . But this implies that which in turn implies that , But by construction, so, for any there is some such that , which allows our definition to be true in general.

    In order to proceed, you need to show that . Any ideas? It really is quite easy. HINT: What is 1500h? How is it related to 0300h? (Or do you not use the 24h clock in the US?)
    Reply With Quote  
     

  16. #15  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I absolutely understand the idea and how it works, I just kind of suck at proving things and generalizing. I'll work on it. We go by 12 hours in the US but I'm fine with the way you put it. Have to do something now but I'll get to this as soon as I can.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  17. #16  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Before anyone reads any further, I warn you I have had a really bad day; I am not in the best of moods..........

    Those who express an interest in manifolds, topology, and other sorts of so-called "higher math" would do well do get the basics right first. This means, for example, knowing to construct proofs using elementary integer arithmetic - this is all that is being asked here..

    Let me give one last very heavy hint; if I say that , I mean (as does the rest of the world) that is an exact divisor of , i.e. no remainder.

    So is it true, or is it not, that ? Is it true, or is it not, that ? What, in the present context, do you conclude from this?

    Sorry for my aggression; I have explained myself.
    Reply With Quote  
     

  18. #17  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Guitarist
    Before anyone reads any further, I warn you I have had a really bad day; I am not in the best of moods..........

    Those who express an interest in manifolds, topology, and other sorts of so-called "higher math" would do well do get the basics right first. This means, for example, knowing to construct proofs using elementary integer arithmetic - this is all that is being asked here..

    Let me give one last very heavy hint; if I say that , I mean (as does the rest of the world) that is an exact divisor of , i.e. no remainder.

    So is it true, or is it not, that ? Is it true, or is it not, that ? What, in the present context, do you conclude from this?

    Sorry for my aggression; I have explained myself.
    But n + 0 = n also. Now we can get Jane to address the issues of +0 vs -0 vs just plain ol' 0. :wink:

    Hope your day got better by time you see this.
    Reply With Quote  
     

  19. #18  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    I thank you for that kind hope; the knowledge one is not the only sucker whose pension fund has been gambled away by some over-paid sufferer from Portnoy's complaint is cold comfort (queue for free soup will be longer....)

    But yeah, OK, I was being sloppy.. "Subtraction" is not a defined operation in a commutative ring, rather the usual notation strictly refers to addition of an inverse. Since zero doesn't have an inverse, or rather is its own inverse, so to speak, I should really have that . However it is usual, for any non-zero integer, to write .

    Then and most specifically yet which implies our partition into no more than distinct classes.

    These classes are equivalence classes. Since , then

    (reflexivity);

    if then so, when and then (symmetry);

    if and then so that, if and then (transitivity)

    There is a wee theorem of Fermat that states that, if is prime, then for any integer then . A nice proof by induction on . Unless someone wants to pre-empt me, I will show it later
    Reply With Quote  
     

  20. #19  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Having, by implication, given Chemboy a royal roasting, I now find myself having to admit to being stuck with F's Little Thm; so embarrassing! I did once know how to do this, but have forgotten.

    Fermat's little theorem: if prime, then for any integer , then . Induction is supposed to work, a method I confess I was always a little skeptical about; it seems I am in a minority of one!

    Fix , and let be the proposition that the thm is true for the nth integer.

    Base cases: are self evident. Now consider .

    We recall from school that by the binomial thm, every term in the expansion is divisible by with the exception of the first and last; these are and .

    Then obviously , by the definition.

    All is well so far, I trust. But how do I prove that this implies that , which would be the proposition ? I assume by transitivity, right? That is , but I cannot get it to work.

    What have I missed?
    Reply With Quote  
     

  21. #20  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    You missed the inductive hypothesis .
    Reply With Quote  
     

  22. #21  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Doh! Thanks, Jane.

    You (and others) may be forgiven for concluding that the skepticism about inductive proofs I voiced earlier was due to my lack of understanding of how they work.

    I concede the partial truth of this, happily now historical.

    Incidentally, readers may be interested to know that Jane's use of is pretty standard, and one says that "a is congruent to b mod n". I started using "=" as I didn't want to pre-empt the conclusion that this is an equivalence relation, so I decided to stick with it.
    Reply With Quote  
     

  23. #22  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Guitarist
    Doh! Thanks, Jane.

    You (and others) may be forgiven for concluding that the skepticism about inductive proofs I voiced earlier was due to my lack of understanding of how they work.

    I concede the partial truth of this, happily now historical.

    Incidentally, readers may be interested to know that Jane's use of is pretty standard, and one says that "a is congruent to b mod n". I started using "=" as I didn't want to pre-empt the conclusion that this is an equivalence relation, so I decided to stick with it.
    I doubt that there is much confusion here, but in my experience "=" is the most misunderstood and abused symbol in mathematics, as least by neophytes. It seems to occur as a random connective whenever students don't know what else to use.

    But "=" means "is". In the manner in which you are using it, "=" does in fact mean "is" since you have the qualifier "(mod n)", which of course does presuppose that "mod n" is an equivalence relation. If you need some lesser relation, you can't go wrong with "~" which is a wonderfully ambiguous connective.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •