Posts tagged with bijection










This post should give you the feeling of bijecting between domains without knowing a lot of mathematics. Which is part of getting the intuitive feeling of mathematics with less work.

Besides automorphisms, there’s another interesting kind of bijection. I’ll try to give you the feeling of bijecting between different domains (a kind of analogy) without requiring much prior knowledge.

Like I said yesterday, a bijection is an invertible total mapping. It ≥ covers ↓ the target and ≤ injects ↑ one-to-one into the target. This is thinking of spaces as wholes—deductive thinking—rather than example-by-example thinking. (There’s a joke about an engineer and a mathematician who are friends and go to a talk about 47-dimensional geometry. The engineer after the talk tells the mathematician friend that it was hard to visualise 47 dimensions; how did you do it? The mathematician replies “Oh, it’s easy. I simply considered the problem in arbitrary N dimensions and then set N=47!” I used to be frustrated by this way of thinking but after X years, it finally makes sense and is better for some things.)

So, graphically, a bijection is surjective/covering/ ≥ / 

image

and injective/one-to-one (not one-to-many)/ ≤ /  ↑
image
.

This amounts to a mathematical way of saying two things are “the same”, when of course there are a lot of ways in which that could be meant. The equation x=x is the least interesting one so “sameness” has to be more broad than “literally the same”. The same like how? Bijection as a concept opens the door to ≥1 kinds of comparison.

 

That was a definition. Now on to the example which should give you the feeling of bijecting across domains and the feeling of payoff after you come up with an unintuitive bijection.

Let’s talk about an “ideal city” where the streets make a perfectly rectangular lattice. I’m standing at 53rd St & 140th Ave and I want to walk/bike/cab to 60th St & 147th Ave.

How many short ways can I take to get there?

The first abstraction I would do from real life to a drawing is to centre the data. A common theme in statistics and mathematically it’s like removing the origin. I can actually ignore everything except the 7×7 block between me and my destination to the northeast.

image

(By the way, by “short” paths I mean not circling around any more than necessary. Obviously I could take infinitely more and more circuitous routes to the point of circling the Earth 10 times before I get there. But I’m trying not to go out of my way here.)

image

Now the problem looks smaller. Just go from bottom left corner to top right corner.

I drew one shortest path in red and two others in black. To me it would be boring to go north, north, north, north, north, north, north, east, east, east, east, east, east, east. But if I want to count all the ways of making snakey red-like paths then I should bracket the possibilities by those two black ones.

When I try to draw or mentally imagine all the snakey paths, I lose track—looking for patterns (like permute, then anti-inner-permute, but also pro-inner-anti-inner-inner-permute…these are words I make up to myself) that I probably could see if I understood the fundamental theorem of combinatorics, but I’ve never been able to fully see the additive pattern.

But, I know a shortcut. This is where the bijection comes in.

image

Every one of these paths is isomorphic to a rearrangement of the letters NNNNNNNEEEEEEE.

Eureka!

 

Every time I “flip” one of the corners in the picture—which is how I was creating new snakes in between the black brackets—that’s just like interchanging an N and an E.

Of course! It’s so obvious in hindsight.

And now here’s the payoff. Rearrangements of strings of letters like AAABBBCCCCD are already a solved problem.

I explained how to count combinatorial rearrangements of letters here. It’s 1026 words long.

The way to get the following formula is to [1] derive a trick for over-counting, [2] over-count and then [3] quotient using the same trick.

image

Now,

  • since the rearrangements of AAAAAAABBBBBBB are isomorphic to the rearrangements of NNNNNNNEEEEEEE,
  • and since the rearrangements of NNNNNNNEEEEEEE are isomorphic to the short paths I could take through the city to my destination,

the correct answer to my original question—how many short ways to go 7 blocks east and 7 blocks north—is 14!/7!/7!.

I asked the Berkeley Calculator the answer to that one and it told me 3432. Kind of glad I didn’t count those out by hand.

 

So, the payoff came from (1) knowing some other solved problem and (2) bijecting my problem onto the one with the known solution method.

But does it work in New York? Even though NYC is kind of like a square lattice, there may be a huge building making some of the blocks not accessible.

image

Or maybe ∃ a “Central Park” where you can cut a diagonal path.
image

And things like “Broadway” that cut diagonally across the city.

image

And some dead ends in certain ranges of the ciudad. And places called The Flat Iron Building where roads meet in a sharp V.

image

So my clever discovery doesn’t quite work in a non-square world.

 

However now I maybe also gave you a microcosm of mathematical modelling. The barriers and the shortcuts could be added to a computer program that counts the paths. We could keep adjusting things and adding more bits of reality and make the computer calculate the difference. But the “basic insight”, I feel, is lacking there. After all I could have written a computer program to permute the letters NNNNNNNEEEEEEE or even just literally model the paths in the first place. (At least with such a small problem.) But then there would be no Eureka moment. I think it’s in this sort of way that mathematicians mean their world is more beautiful than the real one.

As mathematical modellers we inherit deep basic insights—like the Poisson process and the Gaussian as two limits of a binary branching process—and try to construct a convoluted sculpture using those profound insights as the basis. For example maybe I could stitch together a bunch of square lattice pieces together. Maybe for instance two square lattices representing different boroughs and connected only by a single congested bridge. Since I solved the square lattice analytically, the computational extensions will be less mysterious to me if I use the understood pieces. Unless I can be smart enough to figure out how to count triangles & multi-block industrial buildings & shortcuts & construction roadblocks and find an equally excellent insight into how the various discrepancies change the number at the end of my computation (rather than just reading it off and having an answer but no wisdom), I’m left using the excellent insight as a starting point and doing some dirty computations from there—no wisdom at all, no map, just scrapping in the wilderness—a lot of firepower and no idea how to use it. I might as well be spraying a tree with a shotgun instead of cutting the V with an axe and letting its weight do the work.




  • I cheated on you. ∄ way to restore the original pure trust of our early relationship.
  • The broken glass. Even with glue we couldn’t put it back to be the same original glass.
  • I got old. ∄ potion to restore my lost youth.
  • Adam & Eve ate from the tree of the knowledge of good & evil. They could not unlearn what they learned.
  • “Be … careful what you put in that head because you will never, ever get it out.” ― Thomas Cardinal Wolsey
  • We polluted the lake with our sewage runoff. The algal blooms choked off the fish. ∄ way to restore it.
  • Phase change. And the phase boundary can only be traversed one direction (or the backwards direction costs vastly more energy). The marble rolls off the table, the leg poisoned by gangrene. The father dies at war. The unkind words can’t be unsaid.

#semigroups




going the long way
What does it mean when mathematicians talk about a bijection or homomorphism?
Imagine you want to get from X to X′ but you don’t know how. Then you find a "different way of looking at the same thing" using ƒ. (Map the stuff with ƒ to another space Y, then do something else over in image ƒ, then take a journey over there, and then return back with ƒ ⁻¹.)
The fact that a bijection can show you something in a new way that suddenly makes the answer to the question so obvious, is the basis of the jokes on www.theproofistrivial.com.


In a given category the homomorphisms Hom ∋ ƒ preserve all the interesting properties. Linear maps, for example (except when det=0) barely change anything—like if your government suddenly added another zero to the end of all currency denominations, just a rescaling—so they preserve most interesting properties and therefore any linear mapping to another domain could be inverted back so anything you discover over in the new domain (image of ƒ) can be used on the original problem.
All of these fancy-sounding maps are linear:
Fourier transform
Laplace transform
taking the derivative
Box-Müller
They sound fancy because whilst they leave things technically equivalent in an objective sense, the result looks very different to people. So then we get to use intuition or insight that only works in say the spectral domain, and still technically be working on the same original problem.

Pipe the problem somewhere else, look at it from another angle, solve it there, unpipe your answer back to the original viewpoint/space.
 
For example: the Gaussian (normal) cumulative distribution function is monotone, hence injective (one-to-one), hence invertible.

By contrast the Gaussian probability distribution function (the “default” way of looking at a “normal Bell Curve”) fails the horizontal line test, hence is many-to-one, hence cannot be totally inverted.

So in this case, integrating once ∫[pdf] = cdf made the function “mathematically nicer” without changing its interesting qualities or altering its inherent nature.
 
Or here’s an example from calc 101: u-substitution. You’re essentially saying “Instead of solving this integral, how about if I solve a different one which is exactly equivalent?” The →ƒ in the top diagram is the u-substitution itself. The “main verb” is doing the integral. U-substituters avoid doing the hard integral, go the long way, and end up doing something much easier.

 
Or in physics—like tensors and Schrödinger solving and stuff.Physicists look for substitutions that make the computation they have to do more tractable. Try solving a Schrödinger PDE for hydrogen’s first electron s¹in xyz coordinates (square grid)—then try solving it in spherical coordinates (longitude & latitude on expanding shells). Since the natural symmetry of the s¹ orbital is spherical, changing basis to polar coords makes life much easier.

 
Likewise one of the goals of tensor analysis is to not be tied to any particular basis—so long as the basis doesn’t trip over itself, you should be free to switch between bases to get different jobs done. Terry Tao talks about something like this under the keyword “spending symmetry”—if you use up your basis isomorphism, you need to give it back before you can use it again.
"Going the long way" can be easier than trying to solve a problem directly.

going the long way

What does it mean when mathematicians talk about a bijection or homomorphism?

Imagine you want to get from X to X′ but you don’t know how. Then you find a "different way of looking at the same thing" using ƒ. (Map the stuff with ƒ to another space Y, then do something else over in image ƒ, then take a journey over there, and then return back with ƒ ⁻¹.)

The fact that a bijection can show you something in a new way that suddenly makes the answer to the question so obvious, is the basis of the jokes on www.theproofistrivial.com.

image
image
image



In a given category the homomorphisms Hom ∋ ƒ preserve all the interesting properties. Linear maps, for example (except when det=0) barely change anything—like if your government suddenly added another zero to the end of all currency denominations, just a rescaling—so they preserve most interesting properties and therefore any linear mapping to another domain could be inverted back so anything you discover over in the new domain (image of ƒ) can be used on the original problem.

All of these fancy-sounding maps are linear:

They sound fancy because whilst they leave things technically equivalent in an objective sense, the result looks very different to people. So then we get to use intuition or insight that only works in say the spectral domain, and still technically be working on the same original problem.

image

Pipe the problem somewhere else, look at it from another angle, solve it there, unpipe your answer back to the original viewpoint/space.

 

For example: the Gaussian (normal) cumulative distribution function is monotone, hence injective (one-to-one), hence invertible.

image

By contrast the Gaussian probability distribution function (the “default” way of looking at a “normal Bell Curve”) fails the horizontal line test, hence is many-to-one, hence cannot be totally inverted.

image

So in this case, integrating once ∫[pdf] = cdf made the function “mathematically nicer” without changing its interesting qualities or altering its inherent nature.

 

Or here’s an example from calc 101: u-substitution. You’re essentially saying “Instead of solving this integral, how about if I solve a different one which is exactly equivalent?” The →ƒ in the top diagram is the u-substitution itself. The “main verb” is doing the integral. U-substituters avoid doing the hard integral, go the long way, and end up doing something much easier.

http://latex.codecogs.com/gif.latex?%5Cdpi%7B200%7D%20%5Cbg_white%20%5Clarge%20%5Ctext%7BProblem%3A%20integrate%20%7D%20%5Cint%20%7B8x%5E7%20-%206x%5E2%20%5Cover%20x%5E8%20-%202x%5E3%20+%2013587%7D%20%5C%20%5Cmathrm%7Bd%7Dx%20%5C%5C%20%5C%5C%20%5Crule%7B13cm%7D%7B0.4pt%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%5Ctextsc%7BClever%20person%3A%7D%20%5Ctextit%7BHow%20about%20instead%20I%20integrate%7D%20%7D%20%5Cint%20%7B1%20%5Cover%20u%7D%20%5C%20%5Cmathrm%7Bd%7Du%20%5Ctext%7B%20%5Ctextit%7B%3F%7D%7D%20%5C%5C%20%5C%5C%20%5C%5C%20%5Ctext%7B%5Ctextsc%7BQuestion%20asker%3A%7D%20%5Ctextit%7BHuh%3F%7D%7D%20%5C%5C%20%5C%5C%20%5C%5C%20%5Ctext%7B%5Ctextsc%7BClever%20person%3A%7D%20%5Ctextit%7BThey%27re%20equivalent%2C%20you%20see%3F%20Watch%21%7D%20%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%5Csmall%7B%28applies%20basis%20isomorphism%20%7D%7D%20%5Cphi%3A%20x%20%5Cmapsto%20u%20%5C%5C%20%5Ctext%7B%5Csmall%7B%20as%20well%20as%20chain%20rule%20for%20%7D%7D%20%5Cmathrm%7Bd%7D%20%5Ccirc%20%5Cphi%3A%20%5Cmathrm%7Bd%7Dx%20%5Cmapsto%20%5Cmathrm%7Bd%7Du%20%5Ctext%7B%5Csmall%7B%29%7D%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%20%5Csmall%7B%28gets%20easier%20integral%29%7D%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%20%5Csmall%7B%28does%20easier%20integral%29%7D%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%20%5Csmall%7B%28laughs%29%7D%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%20%5Csmall%7B%28transforms%20it%20back%20%7D%7D%20%5Cphi%5E%7B-1%7D%3A%20u%20%5Cmapsto%20x%20%5Ctext%7B%5Csmall%7B%29%7D%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%20%5Csmall%7B%28laughs%20again%29%7D%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%5Ctextsc%7BQuestion%20asker%3A%7D%20%5Ctextit%7BUm.%7D%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%20%5Csmall%7B%28thinks%29%7D%7D%20%5C%5C%20%5C%5C%20%5Ctext%7B%20%5Ctextit%7BUnbelievable.%20That%20worked.%20You%20must%20be%20some%20kind%20of%20clever%20person.%7D%7D

 

Or in physics—like tensors and Schrödinger solving and stuff.
|3,2,1>+|3,1,-1> Orbital Animation
Physicists look for substitutions that make the computation they have to do more tractable. Try solving a Schrödinger PDE for hydrogen’s first electron in xyz coordinates (square grid)—then try solving it in spherical coordinates (longitude & latitude on expanding shells). Since the natural symmetry of the orbital is spherical, changing basis to polar coords makes life much easier.

polar coordinates "at sea" versus rectangular coordinates "in the city"

 

Likewise one of the goals of tensor analysis is to not be tied to any particular basis—so long as the basis doesn’t trip over itself, you should be free to switch between bases to get different jobs done. Terry Tao talks about something like this under the keyword “spending symmetry”—if you use up your basis isomorphism, you need to give it back before you can use it again.

"Going the long way" can be easier than trying to solve a problem directly.







homotopy

homotopy

http://upload.wikimedia.org/wikipedia/commons/7/7e/HomotopySmall.gif

image

image


hi-res




  • "X does something whilst preserving a certain structure"
  • "There exist deformations of Y that preserve certain properties"
  • "∃ function ƒ such that P, whilst respecting Q"

This common mathematical turn of phrase sounds vague, even when the speaker has something quite clear in mind.

  

Smeet Bhatt brought up this unclarity in a recent question on Quora. Following is my answer:

It depends on the category. The idea of isomorphism varies across categories. It’s like if I ask you if two things are “similar” or not.

  • "Similar how? you ask.

Think about a children’s puzzle where they are shown wooden blocks in a variety of shapes & colours. All the blocks that have the same shape are shape-isomorphic. All the blocks of the same colour are colour-isomorphic. All the blocks are wooden so they’re material-isomorphic.

image
image

In common mathematical abstractions, you might want to preserve a property like

after some transformation φ. It’s the same idea: "The same in what way?"

As John Baez & James Dolan pointed out, when we say two things are "equal", we usually don’t mean they are literally the same. x=x is the most useless expression in mathematics, whereas more interesting formulæ express an isomorphism:

  • Something is the same about the LHS and RHS”.
  • "They are similar in the following sense".

Just what the something is that’s the same, is the structure to be preserved.

 

A related idea is that of equivalence-class. If I make an equivalence class of all sets with cardinality 4, I’m talking about “their size is equivalent”.

Of course the set \texttt{ \{turkey, vulture, dove \} } is quite different to the set \{ \forall \texttt{ cones,\ the\ plane,\ a\ sheaf\ of\ rings} \} in other respects. Again it’s about "What is the same?" and "What is different?" just like on Sesame Street.

 

Two further comments: “structure” in mathematics usually refers to a tuple or a category, both of which mean “a space" in the sense that not only is there a set with objects in it, but also the space or tuple or category has mappings relating the things together or conveying information about the things. For example a metric space is a tuple ( \texttt{ things, distances\ between\ the\ things } ). (And: having a definition of distance implies that you also have a definition of the topology (neighbourhood relationships) and geometry (angular relationships) of the space.)

In the case of a metric space, a structure-preserving map between metric spaces would not make it impossible to speak of distance in the target space. The output should still fulfill the metric-space criteria: distance should still be a meaningful thing to talk about after the mapping is done.

 

I’ve got a couple drafts in my 1500-long queue of drafts expositing some more on this topic. If I’m not too lazy then at some point in the future I’ll share some drawings of structure-preserving maps (different “samenesses”) such as the ones Daniel McLaury mentioned, also on Quora:

  • Category: Structure-preserving mapsInvertible, structure-preserving maps

  • Groups: (group) homomorphism; (group) isomorphism
  • Rings: (ring) homomorphism; (ring) isomorphism
  • Vector Spaces: linear transformation, invertible linear transformation
  • Topological Spaces: continuous map; homeomorphism
  • Differentiable Manifolds: differentiable map; diffeomorphism
  • Riemannian Manifolds: conformal map; conformal isometry




John Baez and James Dolan, From Finite Sets to Feynman Diagrams

  • an explosion of ideas
  • equality x=x is boring
  • why is 6÷2=3 ?

(Source: arxiv.org)










  • Why bicontinuity is the right condition for topological equivalence (homeomorphism): if continuity of the inverse isn’t required, then a circle could be equivalent to a line (.99999 and 0 would be neighbours) — Minute 8 or so.
  • Geometric construction (no complex numbers) of the circle group.
  • Pappos’ theorem. (Minute 31)
  • Pascal’s theorem.
  • Desargues’ theorem.
Hat tip to +Ozymandias Haynes.




[G]eometry and number[s]…are unified by the concept of a coordinate system, which allows one to convert geometric objects to numeric ones or vice versa. …

[O]ne can view the length ❘AB❘ of a line segment AB not as a number (which requires one to select a unit of length), but more abstractly as the equivalence class of all line segments that are congruent to AB.

With this perspective, ❘AB❘ no longer lies in the standard semigroup ℝ⁺, but in a more abstract semigroup (the space of line segments quotiented by congruence), with addition now defined geometrically (by concatenation of intervals) rather than numerically.

A unit of length can now be viewed as just one of many different isomorphisms Φ: ℒ → ℝ⁺ between and ℝ⁺, but one can abandon … units and just work with directly. Many statements in Euclidean geometry … can be phrased in this manner.

(Indeed, this is basically how the ancient Greeks…viewed geometry, though of course without the assistance of such modern terminology as “semigroup” or “bilinear”.)
Terence Tao

(Source: terrytao.wordpress.com)