-3
$\begingroup$

Define a permutation or autojection A as a function which bijects from a set X to itself.

Define a binary algebra or magma as a set with a binary operation on it.

Let un-subscripted Hindu-Arabic numerals to denote binary operations.

Conjecture: For every binary algera $N_{1}$=(N, 1) on a set N with with n elements, where n belongs to {2, 3, ...} (equivalently, n equals any natural number greater than 1), there exists an algebra $N_{2}$=(N, 2) (not necessarily distinct from $N_{1}$) such that if A indicates any autojection on N, then A qualifies as an automorphism between $N_{1}$ and some $N_{2}$ (not between every $N_{1}$ and every $N_{2}$).

Question 1: Is this conjecture correct?

Question 2: If correct, how does one prove this conjecture?

This seems true intuitively to me, and it comes as true by definition that A indicates an autojection. So, it would seem that only the homomorphic equation xy1A=xAyA2 would need verified. But, how does one do verify it here, or ensure that the homomorphic equation holds with A as an autojection?

  • 0
    Is a binary algebra just a monoid?2011-06-19
  • 1
    @Matt: No, it is a [magma](http://en.wikipedia.org/wiki/Magma_(algebra)).2011-06-19
  • 0
    @Zev Thanks Zev, I forgot about that term. That said, I like "binary algebra" better, since it more naturally leads, in my opinion, to the notion of a trinary or unary, or n-ary algebra.2011-06-19
  • 6
    @Doug Spoonwood: Personal choices as to the names of things are only useful when one is talking to oneself. A similar comment could be made about personal notational choices.2011-06-19
  • 9
    "Autojection"? You seem to be very, very determined to be not understood both with your vocabulary and your notation: you will probably be happy to know that you are doing great in that front :)2011-06-19
  • 3
    Doug Spoonwood: If we are actually serious about the solution of a problem, we will ask a question in the language of the community. I assume that you are indeed serious about the things that you do, and am willing to give some attention to real problems. But not to trivialities hiding under non-standard notation.2011-06-19
  • 0
    @Mariano I don't know any standard term for a bijection which maps any set back onto itself. The term has gotten used before http://www.google.com/search?q=autojection&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a. What term would you prefer which is not "automorphism"? Also, if one wants to *suggest* that a generalization of sorts might exist for algebras of other types, how does the term "magma" suggest this? @user6312 What may seem trivial from one perspective may not qualify as trivial from another. The rule of substitution of logic looks trivial, but it isn't.2011-06-19
  • 3
    @Doug: I see absolutely no problem with "bijection from a set to itself". I could understand your desire to find a shortcut to that phrase if you were writing a 400 book on the subject, but you only wrote 991 characters in which you used the neologism three times. In any case, «xy1A=xAyA2» is really in a league of its own :)2011-06-19
  • 0
    @Mariano Maybe I should just smile, but since I used the phrase three times I didn't have to write "a bijection from a set to itself" three times. We already have the term "automorphism" for a map from an algebra to another algebra where the carriers come as the same. Also, xy1A=xAyA2 becomes A(x1y)=2(AxAy)... but see here the notation strictly speaking isn't in infix, nor in prefix notation, since unary functions only happens before or after an argument.2011-06-19
  • 2
    @Doug, «xy1A=xAyA2» is perfectly good notation, apart from the fact that is completely different from the notation *essentially everyone* uses to write what it means. The Best Notation In The Universe is useless if it is an impediment to communication.2011-06-19
  • 0
    @Mariano Suffix and prefix notational schemes require fewer symbols to interpret. The only real impediment here comes as lack of familiarity with reading and writing them.2011-06-20
  • 2
    @Doug: the only real impediment is that, apart from you, no one else uses that notation!2011-06-20
  • 0
    @Mariano The Schaum's Outline of Group Theory does use reverse Polish notation, Paul Cohn uses it in spots in his Universal Algebra, Jan Lukasiewicz wrote his papers and books almost entirely in Polish notation, Stanislaw Jaskowski used Polish notation in the first papers on natural deduction, Arthur Prior used Polish notation, and see here http://www.clas.ufl.edu/users/jzeman/modallogic/, and *every* time *anyone* uses a unary operation of any sort that person either uses prefix (Polish) or suffix (reverse Polish) notation for that operation. So I hope you were joking.2011-06-20
  • 6
    I am not joking! The Number One Rule Of Communication is **know who you are talking to**, and you surely don't think Jan Lukasiewicz is reading this site... Take the time to browse a bit in this site and please show me **one** example of anyone using reverse polish notation and integers to denote operations! I have been involved in mathematics for almost two decades now, and I have **never** seen anyone alive do that.2011-06-20
  • 1
    In any case, this is really pointless. You are of course free to do your best to be not understood.2011-06-20
  • 0
    @Mariano Plenty of people here understood what I wrote, as evidenced by the kind responses here (Zev's answer pointed out a legitimate error in my original post, since I forgot to say "some" in a key spot). Evidently both my vocabulary and notation got understood.2011-06-21
  • 3
    I guess you did not find any example.2011-06-21
  • 8
    @Doug: Plenty of people did you the *extreme favor* of spending more than they ought of their time trying to puzzle you out. That you would take this as evidence that you did the right thing is just one more piece of evidence that the workings of your brain are essentially disjoint from mine. You might want to ask them if they found it easy or difficult to puzzle you out or not before bringing them forth as witnesses on your behalf.2011-06-21
  • 0
    @Mariano Though it's not an example of exactly what you asked, Polish notation for operations did get used in the accepted answer here http://math.stackexchange.com/questions/42459/help-with-law-of-excluded-middle/42482#42482. Also, every use of the factorial notation uses RPN, so here's but one example of RPN getting used http://math.stackexchange.com/questions/18576/summation-of-a-factorial. If you use lower-case letters for variables and constants, it comes as clear that numerals come as a different type. So, xyA and xy1 I would think equally clear.2011-06-21
  • 4
    @Doug: unsurprisingly, the one example was written by... you! And yes, that was a postfix exclamation sign.2011-06-21
  • 0
    @Mariano If the first link provided an example here, then every use of factorial notation on this site provides another example.2011-06-21
  • 0
    I took the liberty of editing the question. You can coin your own terms in the body of your question if you want, but it seems absolutely pointless to do so in the title.2011-06-21
  • 1
    Instead of 'autojection' or 'bijection from a set to itself', I think it is quite standard to say 'permutation'.2011-06-21
  • 2
    I don't think that trying to seriously engage with Doug, at least with respect to this question, is going to get anyone anywhere...Actually, the word troll (which I only encountered understood recently, believe it or not) is coming to "the tip of my tongue." I'm trying not to reinforce such behavior by simply disengaging...2011-06-21
  • 0
    @wildildildlife I forgot about "permutation" used that way. That said, if you know a little etymology, "auto" means "self", and "jection" refers to a "throw".2011-06-21
  • 1
    I'm actually with Doug on a few points. e.g. 'Autojection' has the benefit that it creates an analogy with 'automorphism' and also with 'bijection,' whereas 'permutation' creates no analogies whatsoever.2013-05-26

3 Answers 3

4

Given any two sets $A$ and $B$, and a bijection $f\colon A\to B$, any $\alpha$-ary operation $\tau$ (for $\alpha\in\mathrm{Ord}$) yields an $\alpha$-ary operation $\tau'$ on $B$ defined by $$\tau'\left(\{b_i\}_{i\in\alpha}\right) = f\left(\tau\left(\{g(b_i)\}_{i\in\alpha}\right)\right),$$ where $g\colon B\to A$ is the set-theoretic inverse of $f$. Under this definition, $f\colon (A,\tau)\to (B,\tau')$ respects the operation; i.e., $$f\left(\tau(\{a_i\}_{i\in\alpha})\right) = \tau'\left(\{f(a_i)\}_{i\in \alpha}\right).$$

(This includes binary, ternary, $n$-ary, $\omega$-ary, unary, nullary, etc. operations; and of course, $B$ can be $A$).

This easily extends to any family (or even proper class) of operations defined on $A$, so that given a bijection $f\colon A\to B$ and a class $\Omega$ of operations on $A$, we can define on $B$ a family of operations of the same types as $\Omega$ that make $f$ into an $\Omega$-algebra isomorphism.

And stripped of all the formalism and all the neologisms, what this says is basically that if you change the names of all the elements, but keep the operations the same, you get an isomorphic structure. E.g., addition in the natural numbers in English is isomorphic to addition in the natural numbers in Spanish (just be careful in the translation; remember that $\text{one billion}\neq\text{un billón}$, just like $\text{library}\neq\text{librería}$.)

  • 1
    In particular, when $\alpha = 2$, this yields my construction.2011-06-19
  • 1
    @Matt: Indeed; it's a standard thing, though it can be hard to tease out the meaning when one is slogging through neologisms and idiosyncratic notation.2011-06-19
  • 1
    @Arturo: True enough. I am new, and I was unsure how you (the math SE community) handle cases where users coin their own phrases. I assumed it was OK as he did at least define all the words he invented.2011-06-19
  • 1
    @Matt: No need to explain; your answer was spot on. I just wanted to point out that it is a special case of a standard method that applies in more generality.2011-06-19
  • 0
    @Arturo I don't feel sure I follow your last paragraph. Consider the following autojection on {a, b, c} A:a->b, b->c, c->a, and operations 1 and 2 on {a, b, c} as follows 1 :aa->a, ab->b, ac->b, ba->c, bb->a, bc->c, ca->c, cb->c, cc->b Or more compactly, 1: abb,cac,ccb 2: aa->c, ab->a, ac->a, ba->c, bb->b, bc->c, ca->a, cb->a, cc->b or 2: caa,cbc,aab Then A is an automorphism between ({a, b, c}, 1) and ({a, b, c}, 2). But, have the names of the elements gotten changed and the operations kept the same, or have the operations gotten changed and the names of the elements kept the same?2011-06-19
  • 3
    @Doug You can look at it whatever way you want to look at it (which no doubt will not be the way *I* look at it). Doesn't matter whether you think of the names of the elements as changed and the operations as the same, or as the names of the operations changed and the names kept the same. Either way, it's a triviality once you strip it of the confusing neologisms and the idiosyncratic notation.2011-06-19
  • 2
    @Doug This is a simple instance of [transport of structure.](http://en.wikipedia.org/wiki/List_of_mathematical_jargon#transport_of_structure) A less trivial example is transporting the class group structure of quadratic fields from ideals to primitive binary quadratic forms - so greatly simplifying Gauss's presentation of composition of forms.2011-06-21
  • 0
    @Bill: +1. **Transport of structure** is exactly what this is. (I would say though that "transport of structure" should only be used in the trivial sense. For quadratic forms, one *could* define the group law using transport of structure from the ideal class group -- and that's what I did when I taught a course on the subject -- but that's not what Gauss did, and the fact that there is also a composition law purely on the forms side makes the subject significantly richer.)2011-06-21
5

No, the conjecture is not correct. Let $N=\{a,b\}$, and define the operation $\star\,\,:N\times N\rightarrow N$ to be the constant function to $a$. Suppose $\bullet\,\,:N\times N\rightarrow N$ is any other operation on $N$.

If the image of $\bullet$ is all of $N$, then there cannot be any isomorphisms from $(N,\star)$ to $(N,\bullet)$.

If the image of $\bullet$ is $\{a\}$ (i.e. $\bullet=\star$), the autojection $p:N\rightarrow N$ with $p(a)=b$ and $p(b)=a$ is not an isomorphism from $(N,\star)$ to $(N,\bullet)$, because $$p(a\star a)=p(a)=b\neq a= p(a)\star p(a)=p(a)\bullet p(a).$$

If the image of $\bullet$ is $\{b\}$, then the identity autojection is not an isomorphism from $(N,\star)$ to $(N,\bullet)$ for a similar reason.

  • 0
    @Zev I'll use "1" to denote the star operation above, and "2" to denote the dot operation above. If the autojection p is such that p(a)=b, p(b)=a, then p(1(x, y))=p(a)=b. So, "2" has image of {b}. So, p induces a magma from 1. If the autojection i is such that i(a)=a, i(b)=b, then "2" has image of {a}. Parts two and three just tell us that in such a case the autojection can't be p or i respectively. However, such an autojection still exists.2011-06-19
  • 1
    However the way you qualified your statement, it has to work for any autojections. Specifically it must work for p.2011-06-19
  • 1
    @Doug: Why don't you use symbols for operations? It's *much* easier to read. At any rate, your question was asking whether, for any magma $(N,\star)$, there existed another magma structure on $N$, $(N,\bullet)$, for which **any** autojection of $N$ was an isomorphism from $(N,\star)$ to $(N,\bullet)$. It doesn't matter if there exists another magma structure $(N,\bullet)$ for which there is **some** autojection that is an isomorphism from $(N,\star)$ to $(N,\bullet)$; what matters is whether all of them are.2011-06-19
  • 0
    @Zev I didn't use symbols for operations, because I don't have any way to construct an infinity of symbols like how the Hindu-Arabic numerals gives us a way to construct an infinity of operation symbols. I had what I meant in my handwritten notes, it's not quite the same, I'll fix it. Sorry about this. Thanks.2011-06-19
  • 0
    @Zev Perhaps better put, if you consider all operations on a three-element set even you have 3^9=19,683 operations around. Using stars, letters, and the like run out quickly, but natural numbers don't!2011-06-19
  • 0
    However, perhaps $\bullet _1, \bullet _2, ...$ would be better.2011-06-19
  • 1
    @Doug: But we only are referring to two operations here. If it's absolutely necessary you can use $\bullet_1$, $\bullet_2$, etc. It's much easier to think about operations using [infix notation](http://en.wikipedia.org/wiki/Infix_notation).2011-06-19
  • 0
    @Zev I don't see how it's easier, just more commonly used. Almost everyone has much more experience with infix notational schemes than a prefix or postfix scheme. But, we've digressed now.2011-06-19
  • 0
    @Doug Spoonwood: We want to find out as much as we can about the way things **are**. Is "infix" a place where one can shoot up? Postfix sounds as though there should be a law against it.2011-06-19
  • 0
    @user6312 Shoot up? I simply don't understand what you mean by that here. It should come as clear that suffix (and prefix) notational schemes require fewer symbols in general, since you never need parentheses in them. So, I'd expect that with commensurate experience using them as one has with infix, it would become easier to figure out how things are. If I say try to figure out a2(b1a) by looking at operation tables, I first have to look inside the parentheses, then I have to ignore 1 while seeing (b, a) then look up table 1. In suffix, aba12 I don't have to ignore 1 to spot (b, a).2011-06-19
  • 1
    The problem is that integers are often used in additive structures to denote repeated addition, so it could get confusing.2011-06-19
  • 0
    @Doug Spoonwood: The comment about "infix" was a local joke that wouldn't be understood elsewhere. There are linguistic hypotheses about the maximum embedding depth of human languages that give some theoretical insight about why prefix/postfix are so unpopular.2011-06-19
  • 0
    @user6312 Do you have any references that I might read on those hypotheses?2011-06-19
  • 1
    @Doug Spoonwood: The first substantial investigation was done by the linguist Yngve. I did a quick search using embedding depth, linguistics, Yngve. Lots of hits. When long ago I bumped into the Yngve hypothesis, I realized, like presumably hundreds of others, that it explains the total failure of Polish notation in logic. Nowadays it is used only by a few philosophers who never need to deal with a real mathematical problem. But computers love Polish notation. Mathematical notation, and typography, are designed to make the *structure* of formulas visually graspable, by *people*.2011-06-19
  • 0
    @user6312 From the little I've now read on that hypothesis, I don't see how it even could explain the *rarity* of Polish notation in logic. Yngve's hypothesis concerns natural language, while logic *isn't* like natural language. The complexity of natural language is usually much greater than that of a logical language. To write "visually graspable" in logical language basically requires a fuzzy or multi-valued logic, since ((x*y))1, 1(x*y), and xy*1, don't come as either graspable or not, especially when compared to each other. But logic doesn't need a "degree" concept to do something.2011-06-19
  • 0
    @Doug Spoonwood: Mathematicians write in order to communicate ideas, and use the language(s) of the mathematical community, highly specialized variants of natural languages.2011-06-19
  • 0
    I don't think that trying to seriously engage with Doug, at least with respect to this question, is going to get anyone anywhere...Actually, the word troll (which I only encountered understood recently, believe it or not) is coming to "the tip of my tongue.2011-06-21
5

What is true is that given any autojection there is a binary algebra so that the autojection is an automorphism of binary algebras. You simply define the operation so that it works with the autojection. For instance, suppose you have the binary algebra $(N, \star)$, and an autojection $A: N \rightarrow N$. Then define a new operation $\bullet$ by $a \bullet b = A^{-1}(A(a)\star A(b))$ for all $a, b \in N$.

  • 0
    I think I see how that works. But since it works, and since A is an autojection it has the inverse function which you gave above, so it follows that we have A(a.b)=A(a)*A(b). Now say we have . defined and * left unknown. Then the autojection takes the whole table for . to members of N. I think the question I have can thus get restated as does the set of pairs (A(a), A(b)) exhaust the set of pairs of NxN? If they do, then * can get defined here by an autojection.2011-06-19
  • 0
    @Doug: Yes, given any two $a,b \in N$, that formula tells you what their product should be, and it is well-defined since A is a bijection. What your conjecture (now a theorem) would be is that every autojection induces a binary operation that makes the autojection into an automorphism.2011-06-19