Redundancy in mathematical properties

  1. I've been thinking about some common properties of mathematical objects and I've been wondering if they are redundant. Like:

    Aren't all associative operations also closed under a set?

    Doesn't the existence of inverses imply the existence of an identity element?

    So that stating associativity and the existence of inverses imply closure and the existence of an identity element, respectively?

    Are there any other redundant properties like that?
     
  2. jcsd
  3. pwsnafu

    pwsnafu 903
    Science Advisor

    Addition is associative but not closed for the set [0,1].

    You need to define what the identity is before you can use it to define inverses.
     
  4. But if addition maps two tuples of elements of {0,1} to the real numbers then associativity kind of makes no sense because the operation isn't defined for all real numbers, only 0 and 1.

    In other words:

    If ## f:\{0,1\}^2\rightarrow{}\mathbb{R} ## then ## f(f(0,1),1) = f(0,f(1,1)) ## makes no sense because ## f(0,2) ## isn't even defined.


    So are you saying that I need the definition but not necessarily the existence of the inverse element to have the existence of inverses? Or does the existence of inverses actually imply the existence of an identity??
     
  5. AlephZero

    AlephZero 7,300
    Science Advisor
    Homework Helper

    I think the real problem here is using words without defining exactly what you mean by them.

    Of course we all have an intuitive idea about what "associative", "closed", "inverses", "identity element", etc, mean, but if you define carefully what you think they mean in a particular situation, your questions answer themselves.

    If you don't define carefully what the terms mean, these questions are rather like asking "what color would elephant's eggs be, if elephants laid eggs".
     
  6. arildno

    arildno 12,015
    Science Advisor
    Homework Helper
    Gold Member

    How can you invert anything into something you don't know anything about?? :confused:

    Sexual inversion was a concept once upon a time used on homosexuals, that seems not to "undo" heterosexuality into some primeval asexual human condition, but I'd rather say that was a confused concept, rather than an intelligent concept..
     
  7. You are actually making the point here. (1+0.5)+0.5=1+(0.5+0.5)=2 which is not in the set ##[0,1]\subset\mathbb{R}##. This set is not closed under ordinary addition, but it is a subset of the reals, so associativity holds. You don't need the fancy notation. This is a simple counterexample. Perhaps you misunderstood [0,1] as the singleton set {0,1} and not the closed interval?
     

  8. I've been working with the definition that an operation is a function, which is just a relation. So to me associativity for a binary operation ## \omega{}:R\times{}S\rightarrow{}T ## just means that:

    ## \forall{}a\forall{}b\forall{}x\forall{}y\exists{}z[((a,b),x)\in\omega\land{}((b,c),y)\in\omega\Rightarrow((x,c),z)\in\omega\land{}((a,y),z)\in\omega ] ##

    In that case closure is implied, right??

    What would be a definition of associativity which does not imply closure?
     
  9. micromass

    micromass 18,566
    Staff Emeritus
    Science Advisor

    If you define an operation as a function then closure is already implied by the definition of a function. No need for associativity.
     

  10. I did, but it makes no difference.. What you're saying is that addition from the set [0,1] is associative but not closed. What I'm saying is that (1+0.5)+1 is not even addition from [0,1] since (1+0.5)+1 = 1.5+1. So it doesn't make sense to talk about addition in [0,1] being associative.
     
  11. I would usually think of addition as being defined on ##\mathbb{R}## and [0,1] is considered as a subset of ##\mathbb{R}##. If you want to define the operation of addition as only applying to the set [0,1], then micromass is correct.

    Consider the odd numbers under addition. Any number that can be written as ##a=2n+1## for ##n\in\mathbb{Z}## is in this set. If we add three odds together, associativity holds

    ##(a+b)+c=(2n+1+2m+1)+2l+1=2(n+m+l+1)+1=2n+1+(2m+1+2l+1)=a+(b+c)##

    even though the set is not closed under addition. I see your point that this doesn't make sense if we consider the odds as their own algebraic structure and expect each operation to be closed. It doesn't make sense, but we have introduced closure as a separate (and probably more important) idea.
     
    Last edited: Mar 5, 2014
  12. I think we all agree about associativity of addition on the real numbers, and that an operation can be closed but not associative. I am just still not convinced that there exists a definition of associativity that allows for an operation to be associative but not closed.

    But when you say that an operation on a set is associative it has to be associative for all elements of that set. So saying that addition is associative for the odd integers would imply (3+3)+5=3+(3+5) but 6+5 isn't addition on the odd integers so you are not speaking about the binary operation "addition on the odd integers" anymore.

    In my mind what you're saying is that addition on the integers is associative and separately that addition isn't closed for the set of all odd integers. For me they are completely unrelated statements.
     
  13. micromass

    micromass 18,566
    Staff Emeritus
    Science Advisor

    The first thing you would have to do is to define what an operation is. Once you did so, you will find that operations are by definition closed.

    So sure, all associative operations are closed because all operations are closed.
     
  14. pwsnafu

    pwsnafu 903
    Science Advisor

    To explain my post about [0,1].

    There is the definition of "addition on [0,1]" via ##+ : [0,1] \times [0,1] \to [0,1]## and as micromass has pointed out if "binary operation" then "closed". But as V0ODO0CH1LD pointed out this doesn't work, it's undefined hence not binary operation. That's completely right.

    However, we rarely define algebraic structures like groups this way. We normally have a superstructure (in this case ##\mathbb{R}##) and restrict the domain and co-domain (in this case ##[0,1]##). When you do this it's not longer obvious that closure applies, so we make that test explicitly. This is why textbooks start with closure axiom, to make sure that students check.

    Remember: in theory, theory and practice are the same, in practice, they are different.
    So yes, in logic, it is redundant.
     
  15. How are all binary operations closed exactly?? The dot product isn't closed.
     
  16. Fredrik

    Fredrik 10,202
    Staff Emeritus
    Science Advisor
    Gold Member

    I've been thinking about these things too in the past few days, especially in the context of definitions of the term "group". (I've been cleaning up some notes). This is how I define "group" in my notes:

    Definition: A pair ##(G,\star)## such that ##\star## is a binary operation on ##G## is said to be a group if
    (1) ##\star## is associative.
    (2) ##\star## has an identity.
    (3) Every element of G has an inverse.

    There's no need for an explicit closure axiom here, because a binary operation on ##G## is by definition a function from ##G\times G## into ##G##. A subset ##S\subseteq G## is said to be closed under ##\star##, if ##x\star y\in S## for all ##x,y\in S##. So it follows immediately from the definitions that if ##\star## is a binary operation on ##G##, then ##G## is closed under ##\star##.

    This means that there actually is a closure axiom in the definition, because the definition is really saying this:
    A pair ##(G,\star)## is said to be a group if
    (0) ##\star## is a binary operation on ##G##.
    (1) ##\star## is associative.
    (2) ##\star## has an identity.
    (3) Every element of ##G## has an inverse.
    It's not one of the numbered axioms (in the first definition), but it still makes sense to view it as an axiom. However, when one speaks of "the axioms in definition blah-blah" (I think) one usually means only the statements on the numbered list.

    Assuming that you define "identity" and "inverse" the same way I do, the statement "Every element of ##G## has an inverse (with respect to ##\star##)" implies that ##\star## has an identity, if and only if ##G\neq\varnothing##. So my definition is NOT equivalent to this:
    A pair ##(G,\star)## such that ##\star## is a binary operation on ##G## is said to be a group if
    (1) ##\star## is associative.
    (2) Every element of G has an inverse.

    The only problem with this definition is that it makes ##(\varnothing,\varnothing)## a group. This loophole can be plugged by specifying that ##G## is non-empty. So my definition is equivalent to this:
    A pair ##(G,\star)## such that ##G## is a non-empty set and ##\star## is a binary operation on ##G## is said to be a group if
    (1) ##\star## is associative.
    (2) Every element of G has an inverse.

    The (numbered) axioms in my definition imply all of the following seven statements about a pair ##(G,\star)## such that ##\star## is a binary operation on ##G##.
    (1) ##\star## is associative.
    (2) ##\star## has a left identity.
    (3) ##\star## has a right identity.
    (4) For all ##x\in G##, there's a ##y\in G## such that ##y\star x## is a left identity of ##\star##.
    (5) For all ##x\in G##, there's a ##y\in G## such that ##x\star y## is a left identity of ##\star##.
    (6) For all ##x\in G##, there's a ##y\in G## such that ##y\star x## is a right identity of ##\star##.
    (7) For all ##x\in G##, there's a ##y\in G## such that ##x\star y## is a right identity of ##\star##.

    The redundancy in the definition can be described as follows: We only need three of these seven statements. There are four choices of triples of axioms that will work:
    (1,2,6)
    (1,2,7)
    (1,3,4)
    (1,3,5)
     
    Last edited: Mar 7, 2014
  17. Fredrik

    Fredrik 10,202
    Staff Emeritus
    Science Advisor
    Gold Member

    A binary operation on a set X is a function from ##X\times X## into ##X##, not from ##X\times X## into ##\mathbb R##.
     
  18. micromass

    micromass 18,566
    Staff Emeritus
    Science Advisor

    Fredrik (and others), you might be interested in the universal algebra definition of a group. I think that definition actually makes more sense than the others (but it's equivalent of course, and what's the use arguing about definitions).

    Definition: A group is a tuple ##(G,*,i,e)## where ##G## is a set, where ##*:G\times G\rightarrow G## is a function, where ##i:G\rightarrow G## is a function and where ##e\in G##. It satisfies the following axioms:
    1) ##g*(h*k) = (g*h)*k##
    2) ##g*e = g = e*g##
    3) ##g*i(g) = e = i(g)*g##

    The advantage of this definition is that the "inverse axiom" no longer relies on the "identity axiom", which I have never really liked.
     
  19. Fredrik

    Fredrik 10,202
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm aware of this. I think the 4-tuple definition is prettier, but probably less appropriate for an introduction. A 4-tuple group ##(G,\star,i,e)## is completely identified by the pair ##(G,\star)##, so students will wonder why we include those other two things. I understand that the main reason is that it makes our work easier when we want to view groups, fields, etc. as different types of algebraic structures, with homomorphisms defined by a single definition rather than by one definition for groups, one for fields, etc. But if we're just going to be talking about groups, it's probably better to focus on the pair definition.

    One more thing I like about the 4-tuple definition is that you can't make mistakes like this:
    A pair ##(G,\star)## such that ##\star## is a binary operation on ##G## is said to be a group if
    (1) For all ##x,y,z\in G##, we have ##x(yz)=(xy)z##.
    (2) There's an ##e\in G## such that ##ex=xe=x##.
    (3) For all ##x\in G##, there's a ##x^{-1}\in G## such that ##x^{-1}x=xx^{-1}=e##.

    The problem here is of course that e is a dummy variable in axiom 2, so axiom 2 doesn't assign a meaning to the e that appears in axiom 3. Of course, you can solve the problem by changing axiom 3 to something like this:
    (3') For all ##x\in G##, there's a ##x^{-1}\in G## such that ##x^{-1}x=xx^{-1}=e##, where ##e## denotes the identity that's guaranteed to exist and be unique by axiom 2 and theorem blah-blah.

    Definitely not as pretty as the 4-tuple definition. This complication is why I prefer the "wordy" version of the pair definition over a version that doesn't rely on previous definitions of identity and inverse.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted