### Autor Tema: Prove that they are monoids

0 Usuarios y 1 Visitante están viendo este tema.

09 Abril, 2022, 04:58 am
Leído 141 veces

#### Kandor

• $$\Large \color{#6a84c0}\pi$$
• Mensajes: 4
• País:
• Karma: +0/-0
##### Prove that they are monoids
a)Let $$S, T, U$$, and $$V$$ be sets and let $$X \subseteq S \times T, Y \subseteq T \times U$$, and $$Z \subseteq U \times V$$ be subsets. Define
$$X * Y:=\{(s, u) \in S \times U \mid \exists t \in T:(s, t) \in X \text { and }(t, u) \in Y\} \subseteq S \times U .$$
Show that
$$(X * Y) * Z=X *(Y * Z) .$$
(b) Let $$S$$ be a set. Show that $$(\mathcal{P}(S \times S), *)$$ is a monoid. Is it commutative?
(c) What are the invertible elements in the monoid of Part (b)?

09 Abril, 2022, 09:15 am
Respuesta #1

#### Luis Fuentes

• el_manco
• Mensajes: 51,248
• País:
• Karma: +0/-0
##### Re: Prove that they are monoids
Hola

a)Let $$S, T, U$$, and $$V$$ be sets and let $$X \subseteq S \times T, Y \subseteq T \times U$$, and $$Z \subseteq U \times V$$ be subsets. Define
$$X * Y:=\{(s, u) \in S \times U \mid \exists t \in T:(s, t) \in X \text { and }(t, u) \in Y\} \subseteq S \times U .$$
Show that
$$(X * Y) * Z=X *(Y * Z) .$$
(b) Let $$S$$ be a set. Show that $$(\mathcal{P}(S \times S), *)$$ is a monoid. Is it commutative?

To be a mononoid the operation must be associative and indentity element must exist.

First check that $I=\{(s,s)|S\in S\}$ is the indentity element:

$I*X=\{(s,u)\in S\times S|\exists t\in S,\,(s,t)\in I\textsf{ and }(t,u)\in X\}$

Note that $(s,t)\in I$ means $t=s$, so:

$I*X=\{(s,u)\in S\times S|(s,u)\in X\}=X$

In a smiliar way prove that $X*I=X$.

Secondly, prove the associative property:

$(s,u)\in (X*Y)*Z\quad \Rightarrow\quad \exists t\in S$ such that $(s,t)\in (X*Y)$ and $(t,u)\in Z$.
$(s,t)\in (X*Y)\quad \Rightarrow\quad \exists t'\in S$ such that $(s,t')\in X$ and $(t',t)\in Y$

Since $(t',t)\in Y$ and $(t,u)\in Z,$ then $(t',u)\in (Y*Z)$

But, $(s,t')\in X$ and  $(t',u)\in (Y*Z)$ means that $(s,u)\in X*(Y*Z)$.

This prove that $(X*Y)*Z\subset X*(Y*Z).$

With a similar argument prove that $X*(Y*Z)\subset (X*Y)*Z$

For not-conmutativity (when $S$ has more than one element) take $X=\{(x,x)\}$ and $Y=\{(x,y)\}$ and compare $X*Y$ and $Y*X$.

Citar
(c) What are the invertible elements in the monoid of Part (b)?

Check that invertible elements correspond to bijective correspondences $X$, that is, verifying:

$\forall s\in S$ exists an unique $t\in S$ such that $(t,s)\in X$

Best regards.

10 Abril, 2022, 05:17 pm
Respuesta #2

#### Kandor

• $$\Large \color{#6a84c0}\pi$$
• Mensajes: 4
• País:
• Karma: +0/-0
##### Re: Prove that they are monoids
hello I did not understand part b) and c) could you explain in more detail

11 Abril, 2022, 08:40 am
Respuesta #3

• el_manco