Operation 'Referencing' In Abstract Algebra

Question

I recently started an Abstract Algebra course so I may not know all of the 'necessary' vocabulary to fully express my question, but here is my attempt. First I need to provide some background thinking.

When beginning my course, a binary operation was defined as a function $F: S \times S \to S$. When dealing with finite sets, we can just list the binary operation pairings $(x,y)$ with $x,y \in S$ each mapped to some $z \in S$ with no problem, but when dealing with infinite sets we need some sort of rule to calculate all of these pairings in $S \times S \to S$ since while the 'list' of pairings may exist we have no way to understand the properties of some infinitely long list without some tools to analyze that list. As an example, something like $a*b = b \cdot a $ on the set $\mathbb{Z}$ (not commenting on whether this is a group or not etc). What I noticed though is that this just 'references' the multiplication operation, which itself has to be defined. Various definitions exist but the simplest is the grade school repeated addition definition and the one I will be going with for this example.

We can then define $a*b = \sum_{i=1}^{b} a$. But this itself references the 'addition' operation. So now we need to define an addition operation. Again various definitions exist, but for simplicity I will go with the Successor Function since we are working exclusively with $\mathbb{Z}^+$ I am not an expert on peano arithmetic so there may be some errors but the general point should be communicated at least, assuming there are errors. We can define addition a + a as $S^{a}(a) = a + a = 2a = c$. We can define multiplication of $3x $ as $S^{a}(S^{a}(a)) = S^{a}(c) = a + a + a = 3a$ and so on. However, unsurprisingly we notice that we first need a definition for function composition since we 'reference' it with $S^{a}(a)$.

Based on what I am seeing here, it looks like each time we try and define a binary operation we just reference some other binary operation. I am assuming this stops eventually, but where does it stop does 'where it stops' true for all binary operations?

If anything needs to be clarified or corrected, I will do so.

Answer 1

This isn't really a question about abstract algebra per se.

The hierarchy is as follows. We begin by asserting the existence of a set $\mathbb{N}$, together with a distinguished element $0 \in \mathbb{N}$ and function $successor : \mathbb{N} \to \mathbb{N}$, which satisfy the (second-order) Peano Axioms or, equivalently, form a "natural numbers object" (a notion from category theory). This requires an axiom. In structural set theory, the axiom would simply be that there is some $\mathbb{N}, 0, successor$ which is a natural numbers object. If you formulate set theory using ZFC, the axiom in question asserts the existence of a specific set $\omega$; one can then define $successor$ and $0$ and prove that they satisfy the axioms.

Just in case you haven't seen it, when we say that $(\mathbb{N}, 0 \in \mathbb{N}, successor : \mathbb{N} \to \mathbb{N})$ is a natural numbers object, we mean that for all sets $A$, $a \in A$, and $next : A \to A$, there is a unique function $f : \mathbb{N} \to A$ such that $f(0) = a$ and $f \circ successor = next \circ f$ (if you don't like the use of function composition, you could instead say $\forall n \in \mathbb{N} (f(successor(n)) = next(f(n)))$). From this basic property, we can prove more general recursion principles, which we will use to define $+$ and $\cdot$.

Once we have a natural numbers object $(\mathbb{N}, 0, successor)$, we can explicitly define $+ : \mathbb{N}^2 \to \mathbb{N}$ as the unique function satisfying a particular recurrence. We can define $\cdot : \mathbb{N}^2 \to \mathbb{N}$ as the unique function satisfying another recurrence, making reference to the already defined $+$. And of course, $1 = successor(0)$.

Once we have these in hand, we can construct $\mathbb{Z}$ using several different methods and define $0, 1 \in \mathbb{Z}$ in terms of $0, 1 \in \mathbb{N}$. We can also define $+, \cdot : \mathbb{Z}^2 \to \mathbb{Z}$ in terms of $+, \cdot : \mathbb{N}^2 \to \mathbb{N}$. And we can define the unary minus sign $- : \mathbb{Z} \to \mathbb{Z}$. One way of doing this is the so-called “Grothendieck completion” construction.

Once we have this in hand, we can construct $\mathbb{Q}$ using a number of different methods. We then have new constants and functions $0, 1 \in \mathbb{Q}$, $+, \cdot : \mathbb{Q}^2 \to \mathbb{Q}$, and $- : \mathbb{Q} \to \mathbb{Q}$, all defined in terms of the operators of the "same name" on $\mathbb{Z}$. Finally, we have a new operator $-^{-1} : \mathbb{Q} \setminus \{0\} \to \mathbb{Q}$, which we define using the construction of $\mathbb{Q}$. One way of doing this is the “field of fractions” construction.

Finally, from there, we repeat the above step with the reals, using one of a number of explicit constructions to generate a new set $\mathbb{R}$ from the pre-existing set $\mathbb{Q}$. We then define the relevant operators on $\mathbb{R}$ in terms of the existing ones for $\mathbb{Q}$.

Finally, an important thing to note. You write

when dealing with infinite sets we need some sort of rule to define [a function $S^2 \to S$

This is sort of true - if you wish to construct a particular function, you will need to write a rule to specify it. But not all functions have a rule that can be written down. In particular, if I tell you $f : S^2 \to S$, you are not allowed to assume there is some rule that can be written down governing the behaviour of $f$.

Answer 2

The actual definition is as given, it's just a function from $S\times S \to S$. What is that? Technically, it is a set of ordered pairs, the first element of which is itself an ordered pair of elements of $S$, the second is an element of $S$, such that Every possible combination ordered pair in $S\times S$ shows up exactly one time.

Example: I can define an operation on the set $\{1,2\}$ as $\{((1,1),1),((1,2),1),((2,1),2),((2,2),1)\}$

This is a set which is my operation, I can give that set a name, such as $\cdot$

Once we have the operation defined such, we can write the information in the form $$1\cdot 1=1$$$$1\cdot 2=1$$ $$2\cdot 1=2$$ $$2\cdot 2=1$$

Note that the actual definition is just the set of ordered pairs above, but writing in that notation is very tedious so we use the convention that $a\cdot b=c$ means $((a,b),c)\in \cdot$

We can define every operation in such a fashion rigorously, so it's not "binary operations all the way down", it's just sets of sets of sets. (We can define ordered pairs themselves as sets: $(a,b)=\{\{a\},\{a,b\}\}$)

However, when everything is obviously understood that the rigorous details CAN be done but is trivially understood, we skip them.

---

Edit: This is the "usual" way of building everything out of axiomatic set theory, the usual axioms being what are the so called ZF axioms (Zermelo-Frankel), or ZFC if we through in the Axiom of Choice. There are alternative ways of doing things not based on sets, but you have to study weirder ways of doing things to go that route!

---

Edit to answer question in comment:

We can use pure set theory to develop addition on the natural numbers recursively, then multiplication, then expand to integers/rationals/reals/etc, so all of those can be built.

For your question, one of the axioms of ZF set theory allows you to describe a set as the elements of an existing set that fit certain logical criteria. So, the existing set would be $(S\times S) \times S$ and your operation could be defined as a set as

$$\cdot =\{((a,b),c)|a,b,c\in S, (b=a+1\rightarrow c=5)\land (b\neq a+1\rightarrow c=a+b)\}$$

This completely describes your infinite set of ordered triples with the desired rules. Note we are using previously defined operations and the shortcut notations, for instance $b=a+1$ is just a shorthand notation for $((a,1),b)\in +$ where $+$ is our previously built addition operation

---

Next edit: How to define an infinite binary operation like addition without referencing another binary operation. We start with the identification of $0=\emptyset$ and $s(n)=n\cup \{n\}$ for previously defined $n$s, this lets us define the natural numbers as sets of previously defined sets recursively, so $1=\{0\},2=\{0,1\}$, etc.

So now we have a function defined on the natural numbers, $s$, this function inputs a number and outputs that number + 1 by definition. We then get $s^{-1}$ as a function that has as the domain all natural numbers but 0 and gives the predecessor to any natural number.

Now we build our general definition of addition in layers: Call $$+_{0}=\{((n,0),n)|n\in \mathbb{N}\}$$

This is the "addition by 0" set. Now, for $m>0$ define $$\{((n,m),r)|n\in \mathbb{N}, ((s(n),s^{-1}(m)),r)\in +_{s^{-1}(m)}\}$$ What this does is define addition by 1 (n+1) as the same thing you get in the previous step as adding (n+1) to 0.
Similarly, it then says adding 2 to a number is the same thing as adding 1 to the next higher number.

Finally, we define our true binary operation + on $\mathbb{N\times N}$ as $$\bigcup _{i=0}^n+_i$$

There is a recursion to "earlier" functions, but those functions aren't full binary relations, they are sets of the form $\mathbb N\times \{m\}\to \mathbb{N}$. It's only when we take the union of all of them that we get a binary operation on an infinite set pop out, without any reference to other binary relations.

Answer 3

I think it is best to think of the definitions bottoming out with the order-theoretic properties of the natural numbers. To explain this, I find it technically more convenient to take $\Bbb{N} = \Bbb{Z}_{\ge0}$, i.e., to include $0$ as a natural number (an approach which sadly seems to have gone out of fashion in recent years). The successor operation is the function $n \mapsto S(n)$ that sends a natural number $n$ to the least natural number $n'$ such that $n < n'$. The order-theoretic properties of $\Bbb{N}$ guarantee that $S(n)$ is well-defined for all $n$.

We then define addition by the clauses: \begin{align*} a + 0 &= a \\ a + S(b) &= S(a + b) \end{align*} That this is a valid definition of a (unique) binary operator $+$ follows from the principle of definition by primitive recursion, which again can be justified by the order-theoretic properties of $\Bbb{N}$. Similarly, we define multiplication by: \begin{align*} a \times 0 &= 0 \\ a \times S(b) &= (a \times b) + b \end{align*}

In more detail, the relevant order-theoretic properties of $\Bbb{N}$, say that the ordering (1) is total (for every $a, b$, either $a \le b$ or $b \le a$), (2) is bounded below (there is least element which we call $0$), (3) is unbounded above (there is no greatest element), (4) is a well-ordering (there are no infinite descending chains $a_0 > a_1 > a_2 > \ldots$), and finally (5) for every $a$, there are only finitely many $b$ such that $b < a$ (this amounts to the principle of mathematical induction and is a bit more tricky to state formally: one way is to say that if $A \subseteq \Bbb{N}$ is non-empty, unbounded and downwards-closed (if $a \in A$ and $b < a$, then $b \in A$), then $A = \Bbb{N}$). From these properties and some not too difficult set theory, one can justify the existence of the successor function and the validity of of the principle of definition by primitive recursion. Axiomatic set theories, such as ZF, come with an axiom of infinity that can be used to construct a set $\Bbb{N}$ with these properties.

As a final remark, I recommend Landau's beautiful book Foundations of Analysis for a very clear exposition of the constructions of $\Bbb{N}$, $\Bbb{Z}$, $\Bbb{Q}$, $\Bbb{R}$ and $\Bbb{C}$.