A few questions about checking whether a set in C++ is an algebraic group

Question

I've started making a library for doing things with abstract algebra. Right now I'm trying to make a function that checks whether a set is a group. It should be self-explanatory:

In mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element satisfying four conditions called the group axioms, namely closure, associativity, identity and invertibility. One of the most familiar examples of a group is the set of integers together with the addition operation; the addition of any two integers forms another integer. (http://en.wikipedia.org/wiki/Group_(mathematics))

#include <set>
#include <iostream>

template <typename ObType, typename BinaryFunction>
bool isGroup(const std::set<ObType> & S, BinaryFunction & op)
{
    /*
       isGroup returns true or false depending on whether the set S
       along with the operator op is a group in the Algebraic sense.
       That is, S is a group if and only if all the 4 following
       conditions are true: 
            (1) If a, b in S, then a op b in S
            (2) If a, b, c in S, then (a + b) + c = a + (b + c)
            (3) There is an element 0 in S such that a + 0 = 0 + a for all a in S
            (4) If a in S, then there is a b in S such that a + b = b + a = 0
    */
    typename std::set<ObType>::const_iterator beg(S.cbegin()), offend(S.cend());
    bool noProblems = true;
    for (std::set<ObType>::const_iterator ia = beg; ia != offend && noProblems; ++ia)
    {
        for (std::set<ObType>::const_iterator ia = beg; ib != offend && noProblems; ++ib)
        {
            // ---------- (1) --------------
            if (S.count(op(*ia, *ib)) == 0) 
                noProblems = false;
            // -----------------------------
            for (std::set<ObType>::const_iterator ic = beg; ic != offend && noProblems; ++ic)
            {
                // ---------- (2) -------------
                if (((*ia + *ib) + *ic) != (*ia + (*ib + *ic)))
                    noProblems = false;
                // ----------------------------
            }
        }
    }

    return noProblems;
}

template <typename T>
class Plus
{
    public:
        T operator() (const T & x, const T & y) { return x + y; };  
};

int main()
{
    std::set<int> S1 = { 0, 1, -1 };
    std::set<int> S2 = { 0 };
    class Plus<int> p;
    std::cout << isGroup(S1, p);
    return 0;

}

No compiler errors, but I have a few questions:

• How can I check for (3) and (4) inside my nest of loops? I
• Later, I'd like to check whether entire sets of native objects like int and long are groups. How can I set S1 equal to an std::set of all longs?

Answer 1

You should create a class to express notion of a set with an operation op (+) (note: this "+" is not ordinary arithmetic + so

// ---------- (2) -------------
if (((*ia + *ib) + *ic) != (*ia + (*ib + *ic)))
    noProblems = false;

is wrong, this should be

// ---------- (2) -------------
if ( op( op(*ia,*ib), *ic) != op( *ia, op( *ib, *ic)))
    noProblems = false;

), values (or rather elements) of this set (a container), and a special element called 1 (or e) element (it is 0 for integers R with (operation called) addition +, but 1 for integers R\0 with multiplication "x"). You need to add a 1 to your class. It is absolutely necessary to check (3) and (4). Further, identity 1 is not an integer 0 in general but a description of some special identity element that will yield same element x if x itself is subject to operation + with 1 ,(e), and 1 + x = x. (you can skip one expression if the operation "+" is commutative, what is true if S is abelian group).

Now what you will do depends on the thing if you would like to introduce hint parameter or not. To find identity element in a given set with hint you can write

template <typename ObType, typename BinaryFunction>
bool isGroup( const std::set<ObType> & S, BinaryFunction & op, ObType e)
{
 //... important define BinaryFunction as taking const args !
typename std::set<ObType>::const_iterator beg(S.cbegin()), offend(S.cend());
bool isGroup = true;
for (std::set<ObType>::const_iterator ia = beg; ia != offend && noProblems; ++ia)
{

        // ---------- (3) --------------
        if( op( *ia, e)) != *ia  || op( e, *ia)) != *ia) 
            isGroup = false;
        // -----------------------------

This is not straightforward to indicate identity element in general. Simple example of integers or other arithmetic types with our well known + is just one of the simplest and not extensible, i.e. in the field of fractions of ring Z, the Q(Z), e for + is given by a pair [0,1] and for "x" by [1,1]. So to make this more general you have to iterate over elements, choose e and call op to check if (3) holds for all elements.

template <typename ObType, typename BinaryFunction>
bool isGroup( const std::set<ObType> & S, BinaryFunction & op)
{
     //... important define BinaryFunction as taking const args !
    typename std::set<ObType>::const_iterator beg(S.cbegin()), offend(S.cend());

    for (std::set<ObType>::const_iterator ia = beg; ia != offend; ++ia)
    {

        // ---------- (3) -------------
        /* let e be an *ia */
        ObType e = *ia; 
        bool isGroup = true;
        for ( auto ia2 : S) {

            if( op( ia2, e)) != ia2  || op( e, ia2)) != ia2) {
                isGroup = false;
                break;
            }

            // identity found, set e_ in class to e and return
            if( isGroup) {
                e_ = e;
               return true;
            }
        }
    }

    /* identity not found, this is not a group */
    return false;
}