Terminology: free algebra with binary op, constant.

[Skolem]

In the sense of 'universal algebra':

The natural numbers N can be presented as an free algebra with one constant (0) and one -unary- operation s(x) (i.e. x --> x+1). We have (of course) elements 0, s(0), s(s(0)), etc...

Is there a good name for a set A with one constant (*) and one -binary- operation b? Here one term is b(b(*,*),b(b(*,*),*)), which can be visualized as some sort of unlabeled binary tree.

Unfortunately, there are multiple concepts related to the term binary tree (see Wikipedia, for example). Here for example, every node must have 0 or 2 children, not 0, 1 or 2 as is commonly allowed. Plus there is the distinction between combinatorial objects and their algebraic forms.

Hopefully there is something more common than "Free (2,0)-algebra [over the empty set]".


Skolem

 

[adriank]

Well, your characterization of N is precisely that (N, [0, s]) is the initial F-algebra, where F: Set -> Set is the functor defined by F(S) = 1 + S, where 1 is a one-element set (a terminal object in Set) and + is the disjoint union (coproduct in Set). Here [0, s] denotes the function 1 + N -> N uniquely determined by the coproduct from the functions 0: 1 -> N and s: N -> N. This definition captures the recursion properties of N: For any set S, x in S, and f: S -> S, we have that (S, [x, f]) is a F-algebra, so there is a unique function k = k_{[x, f]}: N -> S (called a catamorphism) such that k(0) = x and k(s(n)) = f(k(n)) for all n in N. (You should draw a commutative diagram at this point.)

So in the case of the binary operation, let F be the functor Set -> Set defined by F(S) = 1 + (S × S); then (A, [*, b]) is the initial F-algebra. This means that for any set S with x in S and binary operation f: S × S -> S (so that (S, [x, f]) is a F-algebra), there is a unique function k = k_{[x, f]}: A -> S (the catamorphism) satisfying k(*) = x and k(b(m, n)) = f(k(m), k(n)).

 

[Skolem]

Well, your characterization of N is precisely that (N, [0, s]) is the initial F-algebra, where F: Set -> Set is the functor defined by F(S) = 1 + S, where 1 is a one-element set (a terminal object in Set) and + is the disjoint union (coproduct in Set). Here [0, s] denotes the function 1 + N -> N uniquely determined by the coproduct from the functions 0: 1 -> N and s: N -> N. This definition captures the recursion properties of N: For any set S, x in S, and f: S -> S, we have that (S, [x, f]) is a F-algebra, so there is a unique function k = k_{[x, f]}: N -> S (called a catamorphism) such that k(0) = x and k(s(n)) = f(k(n)) for all n in N. (You should draw a commutative diagram at this point.)

So in the case of the binary operation, let F be the functor Set -> Set defined by F(S) = 1 + (S × S); then (A, [*, b]) is the initial F-algebra. This means that for any set S with x in S and binary operation f: S × S -> S (so that (S, [x, f]) is a F-algebra), there is a unique function k = k_{[x, f]}: A -> S (the catamorphism) satisfying k(*) = x and k(b(m, n)) = f(k(m), k(n)).

Yes, but this still leaves my question open: the first 'F-algebra' is called the 'natural numbers', but what is the second 'F-algebra' called? Perhaps the second example has no colloquial name like the first.


Skolem