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: us
  • Karma: +0/-0
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
  • Administrador
  • Mensajes: 51,248
  • País: es
  • Karma: +0/-0
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: us
  • Karma: +0/-0
hello I did not understand part b) and c) could you explain in more detail

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

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 51,248
  • País: es
  • Karma: +0/-0
Hi

hello I did not understand part b) and c) could you explain in more detail

You must explain what exactly you don't understand. Otherwise it's impossible to help you.

Best regards.