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

algorithm, c++, equation-solving, linear-algebra, math

Solution

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;
}

Problem

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 `long`s?

Original source