What does it mean to define an operation?

[SithsNGiggles]

I'm currently enrolled in a course covering semigroups (as an undergrad), and it's the first "abstract" math class I've taken so far. The assignment is to "Define a binary operation on $\mathbb{N}$ which is associative but not commutative," as well as other variations of the associativity/commutativity.

My question is, what does it mean to define an operation? What's the procedure here? My prof didn't give any examples, so I don't know what to do here.

The definition for binary operation (which I think I have a grasp on) given by our textbook is:
"Given a set $S$, a binary operation $\bullet$ on $S$ is a function from $S\times S$ into $S$. The image under $\bullet$ of an element $(s_1,s_2) \in S\times S$ is denoted by $s_1 \bullet s_2$; that is, $s_1 \bullet s_2 \in S$."

 

[LCKurtz]

Informally, you can think up anything you want to do with two positive integers that results in a positive integer for your operation. You obviously don't want to use the usual operations. Here are some random things you could try for your operation, which I will call @:

n@m = max(n,m)
n@m = |m-n|+1
n@m = least common multiple of m and n
n@m = n@m = n^m

on and on. Surely you can think of some that aren't "nice" in the way you need.

 

[SithsNGiggles]

Ah, I see. Thanks for the breakdown!

 

[SithsNGiggles]

Ok, so I came up with a possible operation that I think is commutative but not associative.

Define $\# : \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ to be a binary operation on $\mathbb{N}$ such that $\forall a,b \in \mathbb{N}, a \# b = |a-b|$.

I hope the structure's right and that it's easy to understand.

How do I check for (non-)associativity in this particular case?
I know that I have to show $\forall a,b,c \in\mathbb{N}, a \# (b \# c) \not= (a \# b) \# c$, but I'm a bit confused as to how the left hand side, for example, would translate.

I'm thinking it's something like
$a \# (b \# c) = |a - (b \# c)| = |a - |b - c||$. Is this right?

 

[SammyS]

Ok, so I came up with a possible operation that I think is commutative but not associative.

Define $\# : \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ to be a binary operation on $\mathbb{N}$ such that $\forall a,b \in \mathbb{N}, a \# b = |a-b|$.

I hope the structure's right and that it's easy to understand.

How do I check for (non-)associativity in this particular case?
I know that I have to show $\forall a,b,c \in\mathbb{N}, a \# (b \# c) \not= (a \# b) \# c$, but I'm a bit confused as to how the left hand side, for example, would translate.

I'm thinking it's something like
$a \# (b \# c) = |a - (b \# c)| = |a - |b - c||$. Is this right?

Your Original Post said the operation should be "associative but not commutative".

The operation here is the other way around.

 

[SithsNGiggles]

Your Original Post said the operation should be "associative but not commutative".

The operation here is the other way around.

Yes, I know. I have a set of exercises like this one with minor variations (which I also mentioned in the same post), like "associative but not commutative," "commutative but not associative," both, and neither. Here I'm addressing the second exercise.

Does the operation work, though? And is the syntax okay, especially the translation from a#(b#c) to |a-|b-c||?

 

[VantagePoint72]

Associativity means $\forall a,b,c \in\mathbb{N}, a \# (b \# c) = (a \# b) \# c$. That means that the criterion for non-associativity is actually $\exists a,b,c \in\mathbb{N}, a \# (b \# c) \not= (a \# b) \# c$. That is, you only need a single example in which your operation isn't associative to demonstrate its non-associativity. Indeed, your operation is associative for certain cases like a,b, and c are equal, so you won't be able to prove what you're trying—but it doesn't associate for all numbers which is enough to be "non-associative".

 

[SithsNGiggles]

Associativity means $\forall a,b,c \in\mathbb{N}, a \# (b \# c) = (a \# b) \# c$. That means that the criterion for non-associativity is actually $\exists a,b,c \in\mathbb{N}, a \# (b \# c) \not= (a \# b) \# c$. That is, you only need a single example in which your operation isn't associative to demonstrate its non-associativity. Indeed, your operation is associative for certain cases like a,b, and c are equal, so you won't be able to prove what you're trying—but it doesn't associate for all numbers which is enough to be "non-associative".

Ok, so I came up with a possible operation that I think is commutative but not associative.

Define $\# : \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ to be a binary operation on $\mathbb{N}$ such that $\forall a,b \in \mathbb{N}, a \# b = |a-b|$.

I get the feeling there's been a slight misunderstanding here. I'm showing that this operation is "commutative but not associative", and not "associative but not commutative." Sorry for the mix-up from the first post to the one I'm quoting here.

I've already shown commutativity and non-associativity on paper (tinkering with the definition of |a-b| for commutativity and using a = 1, b = 2, and c = 3 to show non-associativity), but I'm not sure if I translated the operation properly from a#(b#c) to |a-|b-c||, and that's my concern.

 

[VantagePoint72]

You haven't been misunderstood, I understand you are doing a different example. You are misunderstanding (at least in one part of your earlier comment) what it means to be non-associative. Read what I said very carefully. To be called "non-associative", there must exist a set of numbers it's not associative for. It doesn't need to be non-associative for all numbers. Indeed, non-associative operators usually are associative for certain examples (such as the one I gave).

You said that to show non-associativity, you thought you had to prove $\forall a,b,c \in\mathbb{N}, a \# (b \# c) \not= (a \# b) \# c$. That is wrong (and impossible). You just have to show there exists such an a,b,c.

Your counterexample by itself is fine—I just want to make sure you're clear on what it is you have to show to demonstrate something does not have a particular property.

 

[VantagePoint72]

And yes, you translated the operation correctly.

 

[SithsNGiggles]

Oh, I see. I was already aware of the fact that the negation of a "for all ..." is "there exists...", it just didn't quite register for whatever reason. Thanks for pointing out the mistake, though!