Proving something is commutative in abstract algebra

In summary, the commutativity of \ast is shown by the fact that for any two numbers, there is a one-to-one correspondence between the sets of divisors of those numbers and the sets of numbers that are divided by those numbers.
  • #1
snesnerd
26
0
If [itex]\ast : (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d})[/itex], show that [itex]\ast[/itex] is commutative. Note that [itex]d|n[/itex] says [itex]d[/itex] divides [itex]n[/itex]. Now I was not sure how to do this from an abstract algebra point of view although when I stare at it my though process was to maybe rewrite it somehow, which will then be easier to show its commutative.

Homework Statement


Homework Equations


The Attempt at a Solution

 
Last edited by a moderator:
Physics news on Phys.org
  • #2
snesnerd said:
If [itex]\ast : (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d})[/itex], show that [itex]\ast[/itex] is commutative. Note that [itex]d|n[/itex] says [itex]d[/itex] divides [itex]n[/itex]. Now I was not sure how to do this from an abstract algebra point of view although when I stare at it my though process was to maybe rewrite it somehow, which will then be easier to show its commutative.

If [itex]d|n[/itex] then there exists a unique positive integer [itex]c[/itex] such that [itex]cd = n[/itex].
 
  • #3
start by writing down g*f(n).
 
  • #4
I understand what you mean pasmith, but I don't see how that would help show it is commutative.
 
  • #5
snesnerd said:
I understand what you mean pasmith, but I don't see how that would help show it is commutative.

Put, say n=6. Write out the sum f*g(6). Then write out g*f(6). Can you see why they are equal? That's what pasmith's hint is leading to.
 
  • #6
Okay if that is the case, would the following proof show that it is commutative:

[itex](f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d}) = \sum\limits_{d|n}f(\frac{n}{c})g(c) = \sum\limits_{d|n}g(c)f(\frac{n}{c}) = (g \ast f)(n)[/itex]
 
  • #7
snesnerd said:
Okay if that is the case, would the following proof show that it is commutative:

[itex](f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d}) = \sum\limits_{d|n}f(\frac{n}{c})g(c) = \sum\limits_{d|n}g(c)f(\frac{n}{c}) = (g \ast f)(n)[/itex]

By itself, it doesn't make any sense. You have to work in the statement of how d is related to c and supply a few words of explanation.
 
  • #8
[itex] (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d})[/itex].

Note that if [itex]d|n [/itex] then their exists a [itex] c [/itex] such that [itex] n = cd [/itex]. Then [itex] d = \frac{n}{c} [/itex] and [itex] c = \frac{n}{d} [/itex]. Substituting above gives us:

[itex] \sum\limits_{d|n} f(\frac{n}{c})g(c) [/itex]

Now from here how would I word it to explain why [itex] \sum\limits_{d|n}f(\frac{n}{c})g(c) = \sum\limits_{d|n}g(c)f(\frac{n}{c}) [/itex]?
 
  • #9
snesnerd said:
[itex] (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d})[/itex].

Note that if [itex]d|n [/itex] then their exists a [itex] c [/itex] such that [itex] n = cd [/itex]. Then [itex] d = \frac{n}{c} [/itex] and [itex] c = \frac{n}{d} [/itex]. Substituting above gives us:

[itex] \sum\limits_{d|n} f(\frac{n}{c})g(c) [/itex]

Now from here how would I word it to explain why [itex] \sum\limits_{d|n}f(\frac{n}{c})g(c) = \sum\limits_{d|n}g(c)f(\frac{n}{c}) [/itex]?

You want to explain why the set of divisors of n, and the set of numbers n/d where d is a divisor of n are exactly the same set of numbers.
 
  • #10
Because if you consider the set of divisors of [itex] n [/itex] which are [itex] cd [/itex], and you substitute [itex] \frac{n}{d} [/itex] in for [itex] c [/itex] then you get that [itex] n = (\frac{n}{d})d = n [/itex].
 
  • #11
snesnerd said:
Because if you consider the set of divisors of [itex] n [/itex] which are [itex] cd [/itex], and you substitute [itex] \frac{n}{d} [/itex] in for [itex] c [/itex] then you get that [itex] n = (\frac{n}{d})d = n [/itex].

Ok, so if you sum f(d)*g(n/d) over all the divisors of n, then if you substitute the variable c=n/d (which also runs over all divisors of n) then you get the sum f(n/c)*g(c). There is a one-to-one correspondence between d and c.
 
  • #12
But since we have that [itex] n [/itex] and [itex] \frac{n}{d} [/itex] are essentially the same set of numbers then then [itex] \frac{n}{c} [/itex] and [itex] c [/itex] are the same set of numbers so we can commute them and nothing will change/
 
  • #13
snesnerd said:
But since we have that [itex] n [/itex] and [itex] \frac{n}{d} [/itex] are essentially the same set of numbers then then [itex] \frac{n}{c} [/itex] and [itex] c [/itex] are the same set of numbers so we can commute them and nothing will change/

Yes. Summing over the divisors of 6, {1,2,3,6} then f*g(6)=f(1)g(6)+f(2)g(3)+f(3)g(2)+f(6)g(1) and g*f(6)=g(1)f(6)+g(2)f(3)+g(3)f(2)+g(6)f(1). Of course, they are the same. You can match up each term in one sum with the corresponding one in the second.
 

What is the definition of commutativity in abstract algebra?

Commutativity in abstract algebra refers to the property of an operation where the order of the operands does not affect the result. In other words, if the operation is commutative, it will give the same result regardless of the order in which the operands are used.

How do you prove that an operation is commutative?

To prove that an operation is commutative in abstract algebra, you need to show that for any two elements in the set, the result of the operation is the same regardless of the order in which the elements are used. This can be done by using the definition of commutativity and showing that the operation satisfies it.

Can an operation be both commutative and non-commutative?

No, an operation cannot be both commutative and non-commutative. The property of commutativity is binary, meaning that an operation is either commutative or non-commutative. It cannot have both properties at the same time.

What are some examples of commutative operations in abstract algebra?

Some examples of commutative operations in abstract algebra include addition and multiplication of real or complex numbers, as well as the logical operations of AND and OR.

Why is proving commutativity important in abstract algebra?

Proving commutativity in abstract algebra is important because it helps to establish the properties of operations and understand their behavior. It also allows for the simplification of equations and the development of more efficient algorithms and calculations.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
470
  • Calculus and Beyond Homework Help
Replies
4
Views
299
  • Calculus and Beyond Homework Help
Replies
1
Views
248
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
4K
  • Math Proof Training and Practice
Replies
25
Views
2K
Replies
3
Views
8K
  • Advanced Physics Homework Help
Replies
1
Views
681
Replies
4
Views
1K
Back
Top