4
$\begingroup$

Why do abstract algebra texts generally define a group something like more-or-less this...

Let * denote a binary operation on a set G.

For all x, y, z in G x*(y*z)=(x*y)*z

There exists an element 1 in G, such that for all x in G, x*1=x

For all x in G, there exists an x' in G, such that x*x'=1.

Instead of say using a definition like this:

Let * denote a binary operation, ' a unary operation, 1 a nullary operation on G (as best as I understand it, a nullary operation can get thought of a mapping from the empty set to G here, since it does hold that "if for all x belonging to the empty set, then there exists exactly one output in G", since the hypothesis in quotes comes as false, this statement always obtains.)

For all x, y , z in G x*(y*z)=(x*y)*z

For all x in G, x*1=x

For all x in G, x*x'=1

I know that S. C. Kleene's Mathematical Logic has a short section where a small few theorems of group theory get proved using something like the second definition of a group, but only a handful, and little else of group theory or any other algebra gets developed. Does anyone know of texts that study some algebraic systems like groups, rings, monoids etc. using definitions more like the second than the first? That is, study algebras not like how universal algebra texts just mention (maybe I haven't read this thoroughly enough though) several algebras and move on, but rather actually study particular algebras using definitions like the second? Additionally, I see that the Schaum's Outline of Group Theory happily uses a fair amount of reverse Polish notation. Does anyone know of any algebra texts that use either a fair amount of Polish notation, or a fair amount of reverse Polish notation?

Thanks for any help here.

$\endgroup$
9
  • 3
    $\begingroup$ A nullary operation on $G$ is, by definition, a map from $G^{\emptyset}$ to $G$. By definition, $G^{\emptyset}$ is the set of all functions from the empty set to $G$; the only function from the empty set to $G$ is $\emptyset$, so a nullary operation on $G$ is a function with domain $\{\emptyset\}$ and codomain $G$. The final effect is that a nullary operation is "equivalent" to specifying a distinguished element of $G$ (the image of the unique element of $G^{\emptyset}$). \Tour description is missing a 'mapping'; should be a mapping from the set of mappings from the empty set to G, to G $\endgroup$ May 28, 2011 at 3:01
  • 2
    $\begingroup$ @Doug: See here - for any set $A$, there is only one function from the empty set to $A$. As Arturo correctly explains, a nullary operation can be thought of as a function from "$G^0$" to $G$, where "$G^0$" denotes "$G$ cross itself 0 times", a concept which is not exactly well-defined, but which is made rigorous by the identification of $G^n$ with the collection of functions from an $n$-element set $X$ to $G$. $\endgroup$ May 28, 2011 at 5:32
  • 2
    $\begingroup$ In case you are not familiar with it, the notation $Y^X$ refers to the set of functions from $X$ to $Y$. Since $G^0=G^{\varnothing}$ is a singleton (consisting of the unique function from $\varnothing$ to $G$), the functions from $G^0$ to $G$ are in bijection with the elements of $G$, by sending a function $f:G^0\rightarrow G$ to its image $f(G^0)$, and conversely, sending an element $g$ of $G$ to the unique function $f$ sending the sole element of $G^0$ to $g$. $\endgroup$ May 28, 2011 at 5:36
  • 2
    $\begingroup$ @Doug: I introduce no restrictions, but you are getting yourself all confused. Two functions are equal if and only if they have the same domain, the same codomain, and the same value at every point of the domain. As such, there is one and only one function from the empty set to $X$, for each set $X$. "Every conceivable way of mapping" comes out to just one function. For cartesian products, the cartesian product $\pi_{i\in I}X_i$ is defined to be the set of all functions from the index set to the union of the $X_i$, with the value of $i$ in $X_i$. (cont) $\endgroup$ May 28, 2011 at 11:33
  • 2
    $\begingroup$ @Doug: (cont) So the set $G^0$ is, by definition the set of all functions from $0=\emptyset$ to $G$. As just explained, there is one and only one functions. For an ordinal $\alpha$, an $\alpha$-ary operation on $X$ is a function $X^{\alpha}\to X$, so a nullary operation is a function $X^0\to X$. Since $X^0=\{\emptyset\}$, a nullary operation on $X$ is a function $\{\emptyset\}\to X$; equivalently, a single element of $X$. $\endgroup$ May 28, 2011 at 11:35

5 Answers 5

14
$\begingroup$

In fact, if you want to define groups as a variety of $\Omega$-algebras, one does in fact define a group this way: as an algebra with signature $(2,1,0)$ and so on.

This lets you fit group theory (and later, ring theory) into the wider tapestry of Universal (or General) Algebra; see for example George Bergman's An Invititation to General Algebra and Universal Constructions.

However, as it happens, there are a lot of things which are true for groups that are not generally true for universal algebras. To consider one example, any semigroup homomorphism between two groups must in fact be a group homomorphism. This is not the case even for monoids (you can have a semigroup homomorphism between two monoids that is not a monoid homomorphism, because it does not map the identity to the identity). If you don't know groups "well enough" (and view them merely as universal algebras with signature $(2,1,0)$ and satisfying appropriate identities), then in order to check that a map between groups is a homomorphism you would need to check that it maps products to products, inverses to inverses, and the identity to the identity. In order to "get away" with just checking that it is a semigroup homomorphism, you would need to prove that this is the case... and this turns out to be essentially equivalent to performing the verification that the definition of group you quote first uniquely determines the identity and the inverses.

So, if they are equivalent, why use one and not the other? A couple of reasons: one is certainly historical inertia. Groups were originally defined only in terms of their binary operation. The second is parsimony: when you have a concept, and it's ubiquituous (as the group concept is) you want your definition to be as parsimonious as possible, because you want to make it easy to verify that a given instance is in fact a group. We could add all sorts of clauses to the definition of groups (clauses which are theorems of the standard definition) that would make further theorems much easier to prove; but that would mean that if you find a set lying on the street and you want to check if it is a group, you would need to check all the extra clauses.

Using the "usual" definition, you only need one operation and three properties. Using the universal algebra definition, you would need to check three operations, and three properties. So you end up having to do more checking to see if what you have before you is indeed a group or not. Generally, it's better to need to do less checking rather than more checking to see if the theory applies.

I don't really know any text that use prefix or suffix notation for the binary operation of a semigroup, so I can't help with the final question.


Since this came up in the comments, let's clarify a few things about "nullary operation."

First, whether you define a function as a set of ordered pairs, or you define it in terms of a domain, a codomain (and regardless of how you define codomain), and a rule that associates to every element of the domain a single element of the codomain, I think we can agree that if $f$ and $g$ are functions with the same domain and same codomain, then $f=g$ if and only if for every element $x$ in the domain, $f(x)=g(x)$.

So, if $A$ is a set, how many distinct functions are there from $\emptyset$ (the emptyset) to $A$? As you note, the condition of being a function (for every element of the domain there is one and only one element of $A$) is satisfied vacuously, so it seems like you can just take your function to be "whatever", and it will satisfy the definition.

But the point I raised in comments was that in point of fact, there is only one function because of what equality of functions means. If $f$ and $g$ are two functions with domain $\emptyset$ and codomain $A$, then $f=g$ by vacuity: for every $x\in\emptyset$, we have $f(x)=g(x)$. (Put another way, for $f$ and $g$ to be different, there would have to be an element in the empty set where $f$ and $g$ disagree; no such element, so they aren't different). That means that any two functions with domain $\emptyset$ and codomain $A$ are necessarily equal as functions. So there is one and only one function with domain $\emptyset$ and codomain $A$.

If you define a function from $X$ to $Y$ as a subset of $X\times Y$ (ordered pairs) that satisfies certain properties, then it turns out that $\emptyset$, as a function from $\emptyset$ to $A$ (as a subset of $\emptyset\times A = \emptyset$) satisfies this definition, so the function from $\emptyset$ to $A$ is $\emptyset$, the "empty function." That's why I said that there is one and only one function from the empty set to $A$.

Now, about $n$-ary (and $0$-ary or nullary) operations: generally, an $n$-ary operation on $A$ is defined to be a function from $A^n$ to $A$. So a nullary operation is a function with domain $A^0$ and codomain $A$.

What is $A^0$? Well, here it is useful to define arbitrary cartesian products: if $\{A_i\}_{i\in I}$ is a family of sets, then $\mathop{\times}\limits_{i\in I}A_i$ is defined to be the set of all functions $f\colon I\to \cup A_i$ such that $f(i)\in A_i$. For $I=\{1,2,\ldots,n\}$, this can be naturally seen to be "the same" as the idea of $n$-tuples: the $n$-tuple $(a_1,\ldots,a_n)$ is identified with the function that maps $i$ to $a_i$; and a function $f\colon I\to \cup A_i$ with $f(i)\in A_i$ can be associated with the tuple $(a_1,\ldots,a_n)$.

So instead of defining $A^n$ as the set of $n$-tuples, it makes more sense to define it as the product $\mathop{\times}\limits_{i=1}^n A$; this allows for easy generalization to other sets: for any set $I$, you can define an $I$-tuple of elements of $A$ simply by $\mathop{\times}\limits_{i\in I} A$. This is $$\mathop{\times}_{i\in I} A = \bigl\{ f\colon I\to A\bigm| f\text{ is a function}\bigr\}$$ the set of all functions from $I$ to $A$. By analogy to $A^n$, we write this as $A^I$.

Using this notation, $A^0$ is the set of all functions from $0$ to $A$; under the usual definition of the natural numbers as sets, we have $0=\emptyset$, $1=\{0\}$, $2=\{0,1\}$, etc. So $A^0$ is $$A^0 = \{ f\colon 0 \to A\mid f\text{ is a function}\} = \{f\colon\emptyset\to A\mid f\text{ is a function}\}.$$ But we just talked about this. There is one and only one function with domain $\emptyset$ and codomain $A$; so $$A^0 = \{f\colon \emptyset\to a\mid f\text{ is a function}\} = \{\emptyset\}.$$

So, a nullary operation on $A$ is a function $A^0\to A$. But $A^0 = \{\emptyset\}$. So a nullary operation on $A$ is a function $\{\emptyset\}\to A$. There is a natural correspondence between functions from a singleton to $X$ and the elements of $X$: a function $f\colon\{a\}\to X$ corresponds to the element $f(a)$; and an element $b\in X$ corresponds to the function that sends $a$ to $b$. So the nullary operations on $A$ are in one-to-one correspondence with the elements of $A$, which is why nullary operations are sometimes called "distinguished elements of $A$": you can think of a nullary function as its unique value.

In any case, a nullary operation is not a mapping form the empty set to $G$, but rather it's a mapping from the set of all mappings from the empty set to $G$, to $G$: it's a function $G^{\emptyset}\to G$.

$\endgroup$
41
  • 3
    $\begingroup$ @Doug: No, again you are getting confused. A nullary operation is not a function with domain the emptyset, just like a binary operation is not a function with domain $\{1,2\}$. An $n$-ary operation has, as domain, a set of function, namely, the functions from $n$ to $A$. A nullary operation has as domain the set $A^0$, which is not empty, it's a set whose only element is the empty set (a bag that contains an empty bag is not itself empty). There is only one function from the empty set to $A$. But you cannot say that "there exists only one nullary function in the 'abstract sense'". $\endgroup$ May 29, 2011 at 1:49
  • 2
    $\begingroup$ @Doug: I did not claim "there is only one nullary function". You seem to think I did, but I did not. What I said is that there is only one function from the empty set to $A$. But, again, a nullary operation is not a function from the empty set to $A$. The domain of a nullary operation on $A$ is "the set of all functions from the empty set to $A$". It is this set which contains one and only one element. Don't confuse the set of all nullary operations with the set of all functions from the empty set to $A$. The former is $A^{(A^0)}$; the latter is $A^0$. $\endgroup$ May 29, 2011 at 2:02
  • 2
    $\begingroup$ @Doug: This is precisely the mistake I was trying to tell you about in my original comment. You are saying that "a nullary operation is a function from the empty set to $A$". It's not. Just like a binary operation is not a function from $\{1,2\}$ to $A$, it's a function from $A^2$ to $A$. $\endgroup$ May 29, 2011 at 2:05
  • 2
    $\begingroup$ @Doug: 23 hours passed since you asked the question until you thanked Arturo for the explanation of what a nullary function is. Do you still think it is a good idea of presenting groups using a definition that involves that notion? $\endgroup$ May 29, 2011 at 2:20
  • 2
    $\begingroup$ @Doug: Have you ever actually written down a proof in "fully formal manner"? Or, say, seen the fully formal proof that $1+1=2$ in Whitehead and Russell's Principia? They are far harder to follow and understand than what is considered to be a good, solid mathematical proof. I'm just going to have to disagree vehemently with your take on this, and point simply to just how completely you managed to confuse yourself (twice!) on the subject of nullary operations. $\endgroup$ May 29, 2011 at 2:40
5
$\begingroup$

Universal algebra presentations choose the algebra operations so that the general universal algebraic notions of homomorphism and substructure agree with the classical algebraic notions. Thus, for groups, to ensure that the universal notion of substructure yields a subgroup, we must include the inverse operation in the signature, else substructures would merely be subsemigroups (or submonoids if 1 is in the signature).

There is no need to do this in classical algebra textbooks because no attempt is made to give a universal definition of homomorphism or substructure. Rather, such definitions are presented in an ad-hoc manner - given specially for each type of algebraic structure defined (groups,rings, lattices, etc). It is only when we attempt to unify these concepts for various types of algebrac structures that we are forced to pay close attention to such matters.

Also worth emphasis: in universal algebra, we prefer equational axiomatizations, i.e. those given by purely $\rm\color{#c00}{universal}$ axioms (e.g. $\rm\color{#c00}{\forall\,x,y\!:}\ f(x,y) = g(x,y)),\,$ because they allow is to apply strong theoretical results about such classes of algebras (known as varieties or equational classes). For example, we can apply Birkhoff's completeness theorem, that an equation is true in all models iff it is provable by the usual rules of equational logic. Here is a concrete example. Jacobson published a model-theoretic proof of a theorem that any ring satisfying the identity $\rm\:x^n = x\:$ is commutative. By Birkhoff's completeness theorem there exists a purely equational proof of this theorem, but such a proof took a long time to be discovered, and has yet to be published (the case $\rm\:n = 3\:$ is a common moderately difficult exercise).

$\endgroup$
2
  • $\begingroup$ But, what if you want to actually write fully formal proofs of say elementary theorems (those capturable by first-order predicate calculus with equality) in such a text? Does a definition like the first really come as easier to fully formalize than the second? I think not, since the use of existential elimination say in a natural deduction style system, in my opinion, makes for a tricky business. $\endgroup$ May 29, 2011 at 2:09
  • $\begingroup$ @Doug Indeed, universal algebra is primarily concerned with the rich theory if equational structures - see my edit above. $\endgroup$ Jun 3, 2011 at 3:07
4
$\begingroup$

That style of definition is not used because one does not gain anything from using it. I would say that, in fact, it manages to obfuscate a very simple thing. For example, as you have probably noticed by now, the concept of nullary function is not exactly the clearest thing in the universe!

When one is studying universal algebra, or what not, well, in that context something is gained, but that is never done, as far as I know, in an algebra textbook...

$\endgroup$
2
  • $\begingroup$ I think formal proofs become simpler using definition 2, since you only need to concern yourself with universal quantifiers. In say the context of natural deduction, I think it simpler to use universal-introduction and universal-elimination than to use existential-elimination, although perhaps I just feel such easier. $\endgroup$ May 29, 2011 at 2:06
  • 1
    $\begingroup$ @Doug: Have you looked into an actual textbook on group theory to see if anything would be simpler? Try rewriting, say, the proofs of Sylow's theorems, or the proof that the Frattini subgroup of a finite group isnilpotent using your definition 2... $\endgroup$ May 29, 2011 at 2:17
2
$\begingroup$

Probably some principle of economy is involved.

Also, it is reasonable to develop the theory of groups and the theory of fields using roughly similar formalism. In axiomatizing fields, a multiplicative inverse operator would create difficulties.

One might note that in Group Theory, the usefulness for your $x'$ is quickly, if only implicitly, acknowledged. Almost any group theoretic work is littered with expressions of the shape $(x)^{-1}$.

I have not undertaken a survey, but it seems to me that what in logic one would call a constant symbol for the identity element occurs fairly often in the definition of group.

$\endgroup$
2
  • $\begingroup$ Well, do fields really qualify as an algebra, since you can't express the multiplicative inverse idea in terms of a sequence of existential quantifications, nor can you quantify over the entire reference set for a field? Maybe they don't. Maybe we should give up the idea that they do qualify as an algebra, and make them quasi-algebraic at best. Maybe not though. $\endgroup$ May 29, 2011 at 2:15
  • $\begingroup$ @Doug Spoowood: I agree, they do not qualify. But I was pointing out that because classical algebra courses deal with, in particular, groups and fields, it gives reason not to treat inverse as a separate operator, since then the formal treatment of groups and fields would be different. $\endgroup$ May 29, 2011 at 2:20
1
$\begingroup$

You could couch the existence of identity in terms of a 'nullary' operation, but this is probably obfuscatory. Quickly one notices this. Suppose 1 and 1' are both identities. Then

$$1 = 1*1' = 1'.$$

The element is unique. There is no need for an operation here.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .