Register to reply

Redundancy in mathematical properties

by V0ODO0CH1LD
Tags: mathematical, properties, redundancy
Share this thread:
V0ODO0CH1LD
#1
Mar4-14, 11:27 PM
P: 259
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?
Phys.Org News Partner Mathematics news on Phys.org
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
pwsnafu
#2
Mar4-14, 11:34 PM
Sci Advisor
P: 833
Quote Quote by V0ODO0CH1LD View Post
Aren't all associative operations also closed under a set?
Addition is associative but not closed for the set [0,1].

Doesn't the existence of inverses imply the existence of an identity element?
You need to define what the identity is before you can use it to define inverses.
V0ODO0CH1LD
#3
Mar5-14, 10:47 AM
P: 259
Quote Quote by pwsnafu View Post
Addition is associative but not closed for the set [0,1].
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.

Quote Quote by pwsnafu View Post
You need to define what the identity is before you can use it to define inverses.

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??

AlephZero
#4
Mar5-14, 12:07 PM
Engineering
Sci Advisor
HW Helper
Thanks
P: 7,156
Redundancy in mathematical properties

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".
arildno
#5
Mar5-14, 01:04 PM
Sci Advisor
HW Helper
PF Gold
P: 12,016
How can you invert anything into something you don't know anything about??

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..
DrewD
#6
Mar5-14, 01:43 PM
P: 446
Quote Quote by V0ODO0CH1LD View Post
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.
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?
V0ODO0CH1LD
#7
Mar5-14, 01:44 PM
P: 259
Quote Quote by AlephZero View Post
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".

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\omeg a\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?
micromass
#8
Mar5-14, 01:56 PM
Mentor
micromass's Avatar
P: 18,278
Quote Quote by V0ODO0CH1LD View Post
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\omeg a\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?
If you define an operation as a function then closure is already implied by the definition of a function. No need for associativity.
V0ODO0CH1LD
#9
Mar5-14, 02:00 PM
P: 259
Quote Quote by DrewD View Post
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?

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.
DrewD
#10
Mar5-14, 05:11 PM
P: 446
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.
V0ODO0CH1LD
#11
Mar5-14, 07:24 PM
P: 259
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.
micromass
#12
Mar5-14, 07:26 PM
Mentor
micromass's Avatar
P: 18,278
Quote Quote by V0ODO0CH1LD View Post
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.
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.
pwsnafu
#13
Mar6-14, 12:43 AM
Sci Advisor
P: 833
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.
V0ODO0CH1LD
#14
Mar6-14, 03:04 PM
P: 259
How are all binary operations closed exactly?? The dot product isn't closed.
Fredrik
#15
Mar6-14, 04:57 PM
Emeritus
Sci Advisor
PF Gold
Fredrik's Avatar
P: 9,390
Quote Quote by V0ODO0CH1LD View Post
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?
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)
Fredrik
#16
Mar6-14, 05:01 PM
Emeritus
Sci Advisor
PF Gold
Fredrik's Avatar
P: 9,390
Quote Quote by V0ODO0CH1LD View Post
How are all binary operations closed exactly?? The dot product isn't closed.
A binary operation on a set X is a function from ##X\times X## into ##X##, not from ##X\times X## into ##\mathbb R##.
micromass
#17
Mar6-14, 05:06 PM
Mentor
micromass's Avatar
P: 18,278
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.
Fredrik
#18
Mar6-14, 05:54 PM
Emeritus
Sci Advisor
PF Gold
Fredrik's Avatar
P: 9,390
Quote Quote by micromass View Post
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.
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.


Register to reply

Related Discussions
Redundancy of Lie Group Conditions Differential Geometry 1
Definition of a group with redundancy? Calculus & Beyond Homework 1
Using SVD to determine the redundancy of a fit. Calculus & Beyond Homework 0
Redundancy Concept and ECCS in NPP Nuclear Engineering 11
Truth without redundancy? General Discussion 2