Show that B is monoid

Sauraj

New member
Joined
Jul 6, 2019
Messages
9
M=(B,⊙,e)
B is amount of functions: f:{1,2,..,n}→{0,1}
(f⊙g)(x)=f(x)⋅g(x)

find e
show that M is monoid

My solution:
e⊙f=f⊙e=f,
1⊙f=f⊙1=f
=>1⋅f=f⋅1=f so 1 is identity element?

f⊙(g⊙h) = (f⊙g)⊙h => M is monoid

I know it should be simple to solve and I read a lot about monoids, groups, homomorphisms but I dont understand how to solve this type of tasks, need help
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
I believe you meant to say that B is the set (not amount, or number) of all functions from {1, 2, ..., n} to {0, 1}, for some fixed number n.

The identity has to be an element of the set B. What do you mean by the function "1"?

After clarifying this, you need to prove the identity and associativity, rather than just asserting them. You can do this by considering what 1⊙f(x), f⊙1(x), f⊙(g⊙h)(x) and (f⊙g)⊙h(x) are.
 

Sauraj

New member
Joined
Jul 6, 2019
Messages
9
I believe you meant to say that B is the set (not amount, or number) of all functions from {1, 2, ..., n} to {0, 1}, for some fixed number n.

The identity has to be an element of the set B. What do you mean by the function "1"?

After clarifying this, you need to prove the identity and associativity, rather than just asserting them. You can do this by considering what 1f(x), f⊙1(x), f⊙(g⊙h)(x) and (f⊙g)⊙h(x) are.

Yes, B is the set of functions.
I thought 1 is identity. But which function is identity?
I dont understand the dot operator.
What is: 1⊙f(x)? f(x) is zero or one so 1⊙f(x) is 0 or 1?
 
Last edited:

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
Yes, B is the set of functions.
I thought 1 is identity. But which function is identity?
I don't understand the dot operator
.
What is: 1⊙f(x)? f(x) is zero or one so 1⊙f(x) is 0 or 1?
Ah! So you weren't claiming to prove anything, just stating what you have to prove? But you called it your "solution", so I assumed you had defined what function you meant by 1, and proved that it is an identity.

Please give it some thought, and tell us what you think the identity element might be! This is your task, not ours. And please ask specific questions so we can help you with your thinking.

You appear now to be asking what the operation means. You gave the definition:

(f⊙g)(x) = f(x)⋅g(x)​

This means that the "product" of any two functions f and g is the function f⊙g whose value for any input x is the product of the values of the two functions for that input, f(x) and g(x).

Take an example, with n=2. Then B is the set of all functions from {1, 2} to {0, 1}. We can describe such a function by merely listing the values of f(x) for x=1 and x=2; it can be written as an ordered pair, (f(1), f(2)). For example, we can write the function defined by g(1) = 0 and g(2) = 1 as g = (0,1).

Here is the set B: {(0,0), (0,1), (1,0), (1,1)}. Those are all the possible functions (ordered pairs). One of them will be the identity!

To multiply two functions, we just multiply corresponding elements.

The product of the functions f=(1,0) and g=(1,1) is (1⋅1, 0⋅1) = (1,0). Do you follow that? We have (f⊙g)(1)=f(1)⋅g(1)=1⋅1=1, and (f⊙g)(2)=f(2)⋅g(2)=0⋅1=0. In general, f⊙g = (a,b)⊙(c,d) = (ac,bd).

Now, what specific function g could you multiply by any function f, and the result would be the same function, f? That g will be the identity.

By the way, what I am doing is showing you how to think about a problem like this. You first have to make sure you understand what the notation means, which you can commonly do by "playing" with the concepts, often using a small example like my n=2. This makes it more manageable. Once you get an idea of what the problem is about, you can start thinking about the specific questions that are asked.
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
8,331
To: Sauraj, If you have use of a good mathematics library here is a suggestion. The text Basic Algebra I by Nathan Jacobson has chapter one on MONOIDS AND GROUPS. As with all things Jacobson, it is a bit of a hard study but well worth the effort.
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,658
I 2nd Jacobson's Basic Algebra book.
 

Sauraj

New member
Joined
Jul 6, 2019
Messages
9
Ah! So you weren't claiming to prove anything, just stating what you have to prove? But you called it your "solution", so I assumed you had defined what function you meant by 1, and proved that it is an identity.

Please give it some thought, and tell us what you think the identity element might be! This is your task, not ours. And please ask specific questions so we can help you with your thinking.

You appear now to be asking what the operation means. You gave the definition:

(f⊙g)(x) = f(x)⋅g(x)​

This means that the "product" of any two functions f and g is the function f⊙g whose value for any input x is the product of the values of the two functions for that input, f(x) and g(x).

Take an example, with n=2. Then B is the set of all functions from {1, 2} to {0, 1}. We can describe such a function by merely listing the values of f(x) for x=1 and x=2; it can be written as an ordered pair, (f(1), f(2)). For example, we can write the function defined by g(1) = 0 and g(2) = 1 as g = (0,1).

Here is the set B: {(0,0), (0,1), (1,0), (1,1)}. Those are all the possible functions (ordered pairs). One of them will be the identity!

To multiply two functions, we just multiply corresponding elements.

The product of the functions f=(1,0) and g=(1,1) is (1⋅1, 0⋅1) = (1,0). Do you follow that? We have (f⊙g)(1)=f(1)⋅g(1)=1⋅1=1, and (f⊙g)(2)=f(2)⋅g(2)=0⋅1=0. In general, f⊙g = (a,b)⊙(c,d) = (ac,bd).

Now, what specific function g could you multiply by any function f, and the result would be the same function, f? That g will be the identity.

By the way, what I am doing is showing you how to think about a problem like this. You first have to make sure you understand what the notation means, which you can commonly do by "playing" with the concepts, often using a small example like my n=2. This makes it more manageable. Once you get an idea of what the problem is about, you can start thinking about the specific questions that are asked.
Thank you, now I understand what the operator do.

I think the identity is the function that have n one's:
g(1,1,1,1,..,1) because for any function f and some n: f⊙g=g⊙f=f. f(a,b,c,...)⋅g(1,1,1,...) = f(a,b,c,...) = g(1,1,1,...)⋅f(a,b,c,...)
and it is associative because:
f⊙(g⊙h)=(f⊙g)⊙h = f(x)⋅( g(x)⋅h(x) ) = ( f(x)⋅g(x) )⋅h(x)
so M is monoid.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
I think the identity is the function that have n one's:
g(1,1,1,1,..,1) because for any function f and some n: f⊙g=g⊙f=f. f(a,b,c,...)⋅g(1,1,1,...) = f(a,b,c,...) = g(1,1,1,...)⋅f(a,b,c,...)
and it is associative because:
f⊙(g⊙h)=(f⊙g)⊙h = f(x)⋅( g(x)⋅h(x) ) = ( f(x)⋅g(x) )⋅h(x)
so M is monoid.
Good!

Often the way to solve a problem like this is to make a reasonable guess and see what happens!

Since the order n-tuple notation is my own (though not unique to me), not from the problem, a better way to show your work would be to define the function by e(x) = 1 for all x in {1,...,n}, and show that (f⊙e)(x) = f(x)*e(x) = f(x)*1 = f(x) for all x, so that f⊙e = f, and so on.

Similarly, a clearer way to show associativity is to change the order so that you have a single chain of equalities: [f⊙(g⊙h)](x) = f(x)⋅( g(x)⋅h(x) ) = ( f(x)⋅g(x) )⋅h(x) = [(f⊙g)⊙h](x) for all x, so that f⊙(g⊙h) = (f⊙g)⊙h. What you wrote doesn't really make sense, though it shows me that you understand the idea.
 

Sauraj

New member
Joined
Jul 6, 2019
Messages
9
Thx for helping.

(f⊙e)(x) = f(x)*e(x) = f(x)*1 = f(x) for all x, so that f⊙e = f
(e⊙f)(x) = e(x)*f(x) = 1*f(x) = f(x) for all x, so that e⊙f = f
e(x) = 1 is identity.

Now I have 2 monoids
A = (P(A) , ∪, {})
B = (B, ⊙, e(x)=1)

show bijective homomorphism from A → B

My solution:
identity of A is {}

conditions for monoid-hom.:
  • (M, ∗) and (N, •) is a function f : MN such that
    • f(xy) = f(x) • f(y) for all x, y in M
    • f(eM) = eN,
in my case:
  • A=(P(A), ∪, {}) and B=(B, ⊙, e(x)=1) is a function f: A → B such that
    • f(g ∪ h) = f(g) ⊙ f(h) for all g, h in A
    • f( {} ) = 1,
proof:
f(g ∪ h) = f(g) ∪ f(h) = f(g) ⊙ f(h) ?
f( {} ) = f( g({})={} ) = (f⊙ g)( {} ) = f( {} ) ⊙ g( {} ) now I think this is wrong
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
Before I look closely (as I am busy at the moment), I have to point out a couple things.

First, when you say, "A = (P(A) , ∪, {}) ", you are using A to mean two different things, a set and its power set. Is this how the problem was stated? Also, how are A and B related? I think something is missing.

Second, I don't think you defined your function f. What is it?
 

Sauraj

New member
Joined
Jul 6, 2019
Messages
9
Before I look closely (as I am busy at the moment), I have to point out a couple things.

First, when you say, "A = (P(A) , ∪, {}) ", you are using A to mean two different things, a set and its power set. Is this how the problem was stated? Also, how are A and B related? I think something is missing.

Second, I don't think you defined your function f. What is it?
the f is definition from wikipedia (monoid-hom)

I think it should be:

M_A=(P(A), ∪, {})
M_B=(B, ⊙, e(x)=1) is monoid of subsets of A with disjunction. B is a set of functions f:{1..n} -> {0,1}
A is a set.
n = |A|

monoid-hom. is a function φ : M_A → M_B such that
  • φ(g ∪ h) = φ(g) ⊙ φ(h) for all g, h in A
  • φ( {} ) = 1,
 
Last edited:

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
Good; one thing is resolved, in that you have distinguished MA from A, and we now know that MA and MB are related via n: MA is the monoid consisting of all subsets of a set A with cardinality n, and MB is the monoid consisting of all functions from a set with cardinality n to the set {0,1}.

But your goal is to show that there is a bijective homomorphism from MA to MB, so you can't just declare or assume its existence. It is not already defined; the definition of a homomorphism states what must be true of it, if it exists. You have to either define this homomorphism (and show that it meets the requirements), or else indirectly show that such a homomorphism must exist. In a simple case like this, you will be doing the former.

So you need to decide what elements of MA and MB will be paired up.

Suppose you have a subset of A, say X. What function from {1, 2, ..., n} should your φ map it to?

As before, you may find it helpful initially to think about a specific case, such as my n=2. Suppose that A = {1, 2}; list the power set, and decide on a mapping that makes sense. This may make the concept obvious; then you'll just have to make a clear statement of the general case, and prove it.
 

Sauraj

New member
Joined
Jul 6, 2019
Messages
9
finally I have the function =)

ϕ : P(A) → B

how to proof injection and surjection?

injection: P(x) = P(y) => x = y
surjection: ∀y ∈B ∃x ∈P(A) : f(x) = y
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
I don't see that you have defined ϕ yet. You have only said that it is a function from P(A) to B! Given an element of P(A), that is, a subset of A, what function in B will it map to? Given a subset X of A, its image ϕ(X) will be some function f from {1,2,...,n} to {0,1}. State how you will determine (ϕ(X))(x), that is, f(x), for each x.

I think you may be confusing P(A), the set of all subsets of A, with its elements (particular subsets of A). What does P(x) even mean?

Here is what you really need to prove, stated in terms of what P(A) and B are:
  • Injection: show that for any X and Y (two subsets of A), if ϕ(X) = ϕ(Y) [that is, (ϕ(X))(x) = (ϕ(Y))(x) for all x in {1,2,...,n}], then X = Y.
  • Surjection: show that for any function f in B, there is a subset X in P(A) such that ϕ(X) = f.
Again, I think it will help if you think first about the example with n=2, and make things very specific, so that you can see exactly what everything means. That is the only thing about this sort of problem that is really difficult, as you are juggling several different sets and many different functions, which are easy to mix up.
 

Sauraj

New member
Joined
Jul 6, 2019
Messages
9
I don't see that you have defined ϕ yet. You have only said that it is a function from P(A) to B! Given an element of P(A), that is, a subset of A, what function in B will it map to? Given a subset X of A, its image ϕ(X) will be some function f from {1,2,...,n} to {0,1}. State how you will determine (ϕ(X))(x), that is, f(x), for each x.

I think you may be confusing P(A), the set of all subsets of A, with its elements (particular subsets of A). What does P(x) even mean?

Here is what you really need to prove, stated in terms of what P(A) and B are:
  • Injection: show that for any X and Y (two subsets of A), if ϕ(X) = ϕ(Y) [that is, (ϕ(X))(x) = (ϕ(Y))(x) for all x in {1,2,...,n}], then X = Y.
  • Surjection: show that for any function f in B, there is a subset X in P(A) such that ϕ(X) = f.
Again, I think it will help if you think first about the example with n=2, and make things very specific, so that you can see exactly what everything means. That is the only thing about this sort of problem that is really difficult, as you are juggling several different sets and many different functions, which are easy to mix up.
every element of P(A) maps to a fuction with 2 values in B.
ϕ : P(A) -> B
P(x) means, to which function the subset x will be mapped in B.

Is this the function?
\(\displaystyle (ϕ(X))(x) = f_x, \quad \forall x \in \{1,..,n\}, \forall X \subset A
\)

with n = 2, A = {1,2}

P(A) = { {}, {1}, {2}, {1,2} }
B = { (0,0), (0,1), (1,0), (1,1)}

\(\displaystyle
f_1(1) = 0, f_1(2) = 0\\
f_2(1) = 0, f_2(2) = 1\\
f_3(1) = 1, f_3(2) = 0\\
f_4(1) = 1, f_4(2) = 1\\
\)
\(\displaystyle
B = \{ f_1 = (0,0), f_2 = (0,1), f_3 = (1,0), f_4 = (1,1) \}
\\
P\{ \{\} \} = f_1 = (0,0),\\
P\{ \{1\} \} = f_2 = (0,1),\\
P\{ \{2\} \} = f_3 = (1,0), \\
P\{ \{1,2\} \} = f_4 = (1,1)\\
\)

or better:\(\displaystyle
(ϕ( \{\} )(1) = f_1 = (0,0),\\
(ϕ( \{1\})(2) = f_2 = (0,1),\\
(ϕ( \{2\} )(3) = f_3 = (1,0), \\
(ϕ( \{1,2\})(4) = f_4 = (1,1)\\
\)
I hope this is correct.

Now I want to show:
  • Injection: show that for any X and Y (two subsets of A), if ϕ(X) = ϕ(Y) [that is, (ϕ(X))(x) = (ϕ(Y))(x) for all x in {1,2,...,n}], then X = Y.
  • Surjection: show that for any function f in B, there is a subset X in P(A) such that ϕ(X) = f.
Injection:
I know how to show inj. for easy functions like f(x) = 2x. f(x)=f(y) => 2x=2y => x=y. But for this I have no idea.
 
Last edited:

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
every element of P(A) maps to a fuction with 2 values in B.
ϕ : P(A) -> B
P(x) means, to which function the subset x will be mapped in B.

Is this the function?
\(\displaystyle (ϕ(X))(x) = f_x, \quad \forall x \in \{1,..,n\}, \forall X \subset A
\)

with n = 2, A = {1,2}

P(A) = { {}, {1}, {2}, {1,2} }
B = { (0,0), (0,1), (1,0), (1,1)}

\(\displaystyle
f_1(1) = 0, f_1(2) = 0\\
f_2(1) = 0, f_2(2) = 1\\
f_3(1) = 1, f_3(2) = 0\\
f_4(1) = 1, f_4(2) = 1\\
\)
\(\displaystyle
\)
or better: <-- I removed backslashes this so that what follows is visible!\(\displaystyle
(ϕ( \{\} )(1) = f_1 = (0,0),\\
(ϕ( \{1\})(2) = f_2 = (0,1),\\
(ϕ( \{2\} )(3) = f_3 = (1,0), \\
(ϕ( \{1,2\})(4) = f_4 = (1,1)\\
\)
Note that I edited one line above to make something visible that was not originally, and removed the version that is not "better"!

Ultimately, the hard part of writing the actual proof will be to figure out how to clearly say what you mean. That's why I suggested first seeing what you want it to mean in a specific case. I don't think you've quite got the latter.

In particular, you still haven't really defined ϕ, because in "\(\displaystyle (ϕ(X))(x) = f_x, \quad \forall x \in \{1,..,n\}, \forall X \subset A\)", you didn't state what you mean by \(\displaystyle f_x\); and in fact, I think you just meant f(x), since (ϕ(X))(x) is not a function but a value in {0,1}. Or if you did mean what you wrote, then you aren't thinking about what x is, because in the example, x would not be a number from 1 to 4.

Even in the "better" version, your notation is incorrect. What you should have said, for example, is not that \(\displaystyle (\phi( \{1,2\})(4) = f_4 = (1,1)\), but that \(\displaystyle (\phi( \{2\})(1) = f_3(1) = 0\) and \(\displaystyle (\phi( \{2\})(2) = f_3(2) = 1\). In terms of ordered n-tuple notation, which ends up not being so useful in the actual proof, it would be \(\displaystyle (\phi( \{2\}) = f_3 = (0,1)\).

But what you haven't shown at all is how it is determined which function is which. Why does the subset {2} map to the function/ordered pair (0,1)? There is a very nice answer, at least under our temporary supposition that A = {1,2,...,n}, or specifically {1,2}. Until you can clearly explain this in the small example, you will not be able to state it in the proof.

Keep working!
 

Sauraj

New member
Joined
Jul 6, 2019
Messages
9
Sorry, in this task I have only to give bijective homomorphism from \(\displaystyle M_A → M_B\) without any prove. So I don't have to prove injection and surjection as I tought before.

But what you haven't shown at all is how it is determined which function is which. Why does the subset {2} map to the function/ordered pair (0,1)? There is a very nice answer, at least under our temporary supposition that A = {1,2,...,n}, or specifically {1,2}.
If we have A = {1,2}, subset {2} map to the function/ordered pair (0,1) because the element {1} is not in the subset {2}, the value of the first element is zero and the second element is present so its value is 1. Or this example A = {1,2,3} with n=3 then {1,3} map to the function (1,0,1).

\(\displaystyle ϕ(X) = f(x_1,...,x_n), ∀x_i∈\{1,0\},∀ X⊂A, 1 <= i <= n \)

\(\displaystyle
(ϕ(X))(x) =
\left\{
\begin{array}{ll}
1 & \mbox {if } x \in X \\
0 & \mbox {if } x \notin X
\end{array}
\right.
\)
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
Good. You do have the idea.

Even in the absence of a formal proof, you do need a clear statement of what the mapping is, and technically you haven't quite done that yet, in my opinion.

If A were stated in the problem to be the set {1, 2, ..., n}, then what you've said here would be good (though the first version, using an n-tuple, would be a little wrong, because it doesn't explicitly say how the \(\displaystyle x_i\) are related to X). I wouldn't use the n-tuple form in my answer.

In the general case, some mention would have to be made of an enumeration of the elements of A, that is, a one-to-one correspondence between A and {1, 2, ..., n}. As you have it, your x has to be in {1, 2, ..., n}, but is indicated as being in X, and subset of A. (Maybe you never exactly stated the problem as given, and this is acceptable.)
 

Sauraj

New member
Joined
Jul 6, 2019
Messages
9
Good. You do have the idea.

Even in the absence of a formal proof, you do need a clear statement of what the mapping is, and technically you haven't quite done that yet, in my opinion.

If A were stated in the problem to be the set {1, 2, ..., n}, then what you've said here would be good (though the first version, using an n-tuple, would be a little wrong, because it doesn't explicitly say how the \(\displaystyle x_i\) are related to X). I wouldn't use the n-tuple form in my answer.

In the general case, some mention would have to be made of an enumeration of the elements of A, that is, a one-to-one correspondence between A and {1, 2, ..., n}. As you have it, your x has to be in {1, 2, ..., n}, but is indicated as being in X, and subset of A. (Maybe you never exactly stated the problem as given, and this is acceptable.)
Sort \(\displaystyle A =\{x_1, x_2,...,x_n\}\)

ϕ : P(A) -> B

\(\displaystyle \forall i \in\{1,...,n\} \quad \forall X ⊂ A\)

\(\displaystyle (ϕ(X))(i) =

\left\{

\begin{array}{ll}

1 & \mbox {if } x_i \in X \\

0 & \mbox {if } else

\end{array}

\right.\)
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
Looks good.
 
Top