Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Terminology: free algebra with binary op, constant.

  1. Sep 11, 2010 #1
    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]".

  2. jcsd
  3. Sep 12, 2010 #2
    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)).
  4. Sep 12, 2010 #3
    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.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook