Up to, equivalence and mod. (Read at your peril)

[Ben]

So, lately I have been using the slightly jargonistic term "up to", as in "up to isomorphism", which has caused some misunderstanding. So let me explain.

 

Well, superficially, it is simple; the phrase "up to" merely refers to a sort of relaxed form of identity. 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 [math]\sim[/math] that satisfies

 

reflexivity: [math]x \sim x[/math]

 

symmetry: [math]x \sim y \Rightarrow y \sim x[/math]

 

transitivity: if [math]x \sim y[/math] and [math]y \sim z[/math] then [math] x \sim z[/math].

 

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 [math]x \sim x' \sim x''[/math] then the set [math]\{x,x',x''\}[/math] is referred to as, say [math][x][/math], where the typical element [math]x[/math] 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; [math]\{2,4,6,...\}[/math] as the equivalence class [math][2][/math]. The partition induced thereby leaves the set [math]\{1,3,5,..\} \in [1][/math] "remaining".

 

Just as each element in [math][2][/math] can be found by adding 2 to some other element in [math][2][/math], so each element in [math][1][/math] can be likewise found. We call these the even and odd positive integers.

 

Isomorphism, say between vector spaces, 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.

 

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 [math]X/\sim[/math].

 

There is a bit of theory that insists that, if any function on [math]X/\sim[/math] is to be well-defined, then it must be insensitive to which element of an equivalence class it takes as input; that is [math]f([x]) = [y][/math] for all [math]x,x',x''.... \in [x][/math] and some [math]y,y',y'',.... \in [y][/math], which to some extent justifies the claim that equivalent spaces may be regarded as equal.

 

There is a somewhat related notion of modulo, or "mod" for short. But this post is already over-long, let it wait

[lemit]

I have something terrible to confess. I can't read formulae. I hope I'll be allowed to continue here in spite of that.

 

I made my confession because I found it fascinating linguistically that the term "up to" could be used in any technical capacity. Could you explain your post in the ever-popular "For Dummies" format? That will probably take care of my fascination.

 

Thanks.

 

--lemit

[Ben]

I have something terrible to confess. I can't read formulae.

Yes, it is a foreign language that simply has to be learned, more like Chinese, say, than French

I hope I'll be allowed to continue here in spite of that.

Of course, dear boy, why ever not?

 

I found it fascinating linguistically that the term "up to" could be used in any technical capacity.

 

Let me try to answer your direct question.

 

I have a collection here of identically sized balls, but each of a different colour. If (and only if) I decide that all I care about is size, then I will say that these balls are identical "up to colour".

 

Likewise, if they all are the same colour but different sizes, and all I care about is colour, I will say they are identical "up to size".

 

It really is as simple as that, but many things in math (as in life, I guess) boil down to this simple assertion: when saying that 2 things are equal, unless we mean they are literally the same object, we need to be rather specific about the sort of "equality" we are talking about. And even then, it's not always easy to define what is meant by "literally the same object".

 

This is mainstream in math; possibly philosophically rather deep, I wouldn't know. Ughh. My late father was a philosopher, which kind of turned me off the subject......

 

PS by edit

 

When my eldest was very little, a fond aunt asked how far she could count; "All the way from one", says she.

 

So, using the equivalence relation I described, I will now show you how to count "all the way from one".

 

Ready?

 

[math][1], \,[2][/math].

 

Done!!

[lemit]

If your analogy of the balls was not weak, that's a terrible thing to do with language, because "up to" implies preclusion of all possibilities proceeding from the point being alluded to. In other words, when you say the two balls are identical "up to color," you are saying they will not be identical in any other way that might be described subsequently, e.g. density, texture, smell.

 

But that reads like philosophy, doesn't it? Sorry.

 

Am I discussing what you are discussing? If so, I'm getting really interested in it. If not, I want the chance to correctly feel what I feel now.

 

Thanks.

 

--lemit

[Qfwfq]

In other words, when you say the two balls are identical "up to color," you are saying they will not be identical in any other way that might be described subsequently, e.g. density, texture, smell.

Evven better: might not. But then... if they aren't not (meaning they are) then they could be called equal, not just equivalent according to that particular relation. If the two balls share size and also colour, density, texture, smell, &c. are they the same ball? If they are, they also have the same position so, if they aren't, that's at least one thing in which they're not identical.

 

Anyone game for some academic frothing on this topic? :phones:

[Ben]

Not really, but consider the following. I have an object on my desk, and another in my pocket which is in every way indistinguishable. I ask you to close your eyes a while, and then ask you to tell me if I have switched objects, id est is it the same object.

 

I know, but you cannot know. What then is meant by "the same"? Assuming I hadn't switched, nonetheless time has passed, so my "same" object now has different spacetime coordinates. Is it really the same?

 

I give up.....!

 

So anyway, there is a notion strongly related to that of "up to" that applies only to the integers, [math]Z[/math].

 

Let's return to the even and odd integers. Recall an even integer is any such that can be exactly divided by 2. We will give these guys their correct collective name as [math]2Z[/math].

 

I now define the odds as [math]2Z \pm 1[/math]. Now, just as every even integer differs form some other even integer by some integer multiple of [math]2[/math], then likewise the odds, obviously. Well, we can give a single definition for both these equivalence classes as:

 

if [math]2[/math] divides [math]a - b[/math] exactly (i.e. no remainder), for all [math]a, b \in Z[/math], then [math]a,\,\, b[/math] are in the same equivalence class, in this case either odd or even. This generalizes to any integer divisor.

 

One writes [math]a\equiv b\,(\text{mod}\,n)[/math] iff [math] n|(a-b)[/math].

 

It can be shown that, for any integer [math]n[/math] that this induces a partition of [math]Z[/math] into exactly [math]|n|[/math] equivalence classes (the enclosing pipes refer to absolute value, btw).

[sanctus]

if [math]2[/math] divides [math] a - b[/math] exactly (i.e. no remainder), for all[math] a, b \in Z[/math]

 

Fun typo, because such integers do not exist, I guess you just wanted to say for [math]a,b \in Z[/math] :-)

[Ben]

Well, you are generous to describe it as a typo. It was actually an act of stupidity on my part.

 

So yes, you are correct, I expressed myself poorly.

[Qfwfq]

Don't worry Ben just edit out the bit that shouldn't be there.

 

Anyway the two balls can't be the same ball if they're not in the same place at the same time. If you can't otherwise tell which is which then they're identical apart from position.

[Nootropic]

From my understanding, isomorphism is taken with respect to a structure that is defined on an object. For example, if we consider the integers with the usual operation of addition, denoted by (Z, +) then if we consider any nontrivial subgroup which is given by some nZ for some n > 1 then by sending any integer m to n*m we actually obtain a group isomorphism (so it's actually true that every nontrivial subgroup is isomorphic to each other). However, when discussing rings (in particular, if you work in commutative ring theory like I do, rings always have an identity) these two structures are in fact not isomorphic (if you consider my previous parenthetical remark, you can see this immediately by noticing that nZ does not contain an identity; if you insist that it is not necessary that a ring have an identity it's a bit trickier). And also, if you notice the map that sends m to n*m is also not a ring isomorphism (it's not even a ring homomorphism!).

 

So when discussing basketballs, if we are discussing one part of the structure, such as color, then two basketballs of the same color would be isomorphic (regardless of other structure). As another example of how structure determines this, consider the field of real numbers R and form the vector space V of sequences of real numbers in which all but a finite number of elements of the sequence are nonzero (addition defined component-wise and scalar multiplication in the obvious way). Then if you consider the vector space R[x] (polynomials with coefficients that are real numbers) where addition and scalar multiplication are normally defined, this actually turns out to be isomorphic to V as vector spaces. However, if we in turn define a ring structure on V by defining multiplication of sequences component-wise, then there is no way for this be a ring isomorphism when multiplication on R[x] is defined in the normal way of multiplying polynomials (the former is not an integral domain, while R[x] is).

 

So in short, what I'm saying is, one must specify what structure you are defining an isomorphism on.

[Ben]

Well, I agree with all of this. So, although my post was merely intended to explain the various sorts of "equality" that sets may have up to any equivalence relation, I thank you for your clarification about isomorphism.

 

Incidentally: Every text I have ever seen invariably introduces isomorphism first, just as you explained it, and then subsequently goes on to explain homomorphism.

 

This seems perverse to me; surely a better approach would be first to describe homomorphism as a mapping that respects operation(s) and identity(s), and then simply state that this mapping will be an isomorphism iff it is a bijection?

[Nootropic]

Well it's certainly of interest to note that on the set of structures you define the notion of an isomorphism on, you can actually define an equivalence relation by saying A ~ B iff A is isomorphic to B. Though this isn't much of an interest, it's kind of a special case of the notion of an equivalence relation.

 

As for textbooks, most textbooks I've read (if I remember correctly...) introduce the idea of a homomorphism before isomorphism, but honestly, it's not that large of a pedagogical disadvantage (and may even, in fact, be an advantage to some). The reasoning behind introducing an isomorphism first is that you can use easy examples to demonstrate this whole idea of "structure-preserving". For example, you might want to see show that Z/12Z is isomorphic to Z/4Z x Z/3Z (as groups). Now an easy way of going about doing this is comparing operation tables and in this way you sort of define a "map", which just so happens to be a bijection as well, but the important part is for your students (or whomever you are teaching) is to see the way in which the operation (in this case, addition) is "essentially" the same. Now it might be a little more difficult to use Z/12Z and Z/6Z and demonstrate a homomorphism from Z/6Z into Z/12Z by means of a group table. I find that this sort of elementary comparison between simple algebraic objects tends to give students a better initial grasp when they don't have to worry about things differing in size. Either way though, it's not nearly as important as something like whether or not you should introduce groups or rings first.

[Qfwfq]

So in short, what I'm saying is, one must specify what structure you are defining an isomorphism on.

Certainly. I was meaning to say a few words on this and give a very simple yet cute example where the operations in each structure are quite heterogeneous; the exponential is an isomorphism between [imath]\mathbb{R}[/imath] with ordinary addition and the positive reals with ordinary multiplication. Nobody in their right mind would say these two structures are equal.

 

Every text I have ever seen invariably introduces isomorphism first, just as you explained it, and then subsequently goes on to explain homomorphism.

I quite agree with you in finding this perverse, my courses gave endomorphism, isomorphism and automorphism as specific cases of homomorphism.

 

Well it's certainly of interest to note that on the set of structures you define the notion of an isomorphism on, you can actually define an equivalence relation by saying A ~ B iff A is isomorphic to B. Though this isn't much of an interest, it's kind of a special case of the notion of an equivalence relation.

This is kinda what Ben did, just to give an example of equivalence relation.

 

I also meant to say that an equivalence class of isomorphic structures are sometimes said to be an abstract structure, of which each class member is said to be a concrete representation.