Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2024: Generalizations of the Notion of Primes

a
p
Generalizations of the Notion of Primes J
Exercise 0.1(part 1)
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thayaden
1135 posts
#1
This topic is linked to null - null.
Y by
let $b\in M$ by definition,
$$(1):~~e*b=b*e=b,$$$$(2):~~e'*b=b*e'=b$$this is true for all $b$ thus let $b=e'$ this might lead us to (from $(1)$),
$$e*e'=e'*e=e'$$$$e*e'=e'$$Now let $b=e$ (using $(2)$),
$$e'*e=e*e'=e$$$$e*e'=e$$By the transitive property,
$$\boxed{e'=e}$$as the first condition is true, $e,e'\in M$ we might then say that given all identity elements of $M$ denoted as $e_i$ we might have,
$$e_1=e_2$$and inductively,
$$e_k=e_{k+1}$$thus,
$$e_1=e_2=e_3=e_4=\cdots$$. Or in plain text, we might say that as one identity is equal to another then if we have some identity it is the same as the identity we already have.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thayaden
1135 posts
#2 • 1 Y
Y by felixgotti
Starting things off we have $u*v=e$ such that $e$ is the identity of $M$ and $u*v'=e$ notice that $u*e=e$ we might have,
$v'=v'*e=v'*(u*v)=(v'*u)*v = e*v = v$
thus given $u$ that is invertible there is a unique inverse $v$
Z K Y
N Quick Reply
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
Exercise 0.1(part 1)
Thayaden   1
N Sep 11, 2024 by Thayaden
let $b\in M$ by definition,
$$(1):~~e*b=b*e=b,$$$$(2):~~e'*b=b*e'=b$$this is true for all $b$ thus let $b=e'$ this might lead us to (from $(1)$),
$$e*e'=e'*e=e'$$$$e*e'=e'$$Now let $b=e$ (using $(2)$),
$$e'*e=e*e'=e$$$$e*e'=e$$By the transitive property,
$$\boxed{e'=e}$$as the first condition is true, $e,e'\in M$ we might then say that given all identity elements of $M$ denoted as $e_i$ we might have,
$$e_1=e_2$$and inductively,
$$e_k=e_{k+1}$$thus,
$$e_1=e_2=e_3=e_4=\cdots$$. Or in plain text, we might say that as one identity is equal to another then if we have some identity it is the same as the identity we already have.
1 reply
Thayaden
Sep 11, 2024
Thayaden
Sep 11, 2024
J
H
Exercise 0.1
palindrome868   0
Aug 5, 2024
What I've tried so far:

(1) If $e, e' \in M$ are two distinct identity elements of $M$, then $e * e' = e = e'$, a contradiction.

(2) Let $e$ be the identity element of $M$. If $v, v' \in M$ are two distinct inverses of $u$, then
\begin{align*}
v * u = e &\implies (v * u) * v' = (e) * v' \\
&\implies v * (u * v') = v' \\
&\implies v = v'
\end{align*}a contradiction.

(3) Claim 1: Associativity holds in $\mathcal{U}{(M)}$

$b, c, d \in \mathcal{U}{(M)} \implies b, c, d \in M \implies (b * c) * d = b * (c * d)$.

Claim 2: Identity holds in $\mathcal{U}{(M)}$

The identity element of $M$ is the inverse of itself, so it is also in $\mathcal{U}{(M)}$. Since the operations in $M$ and $\mathcal{U}{(M)}$ are the same, it is the identity of $\mathcal{U}{(M)}$ as well.

Claim 3: Closure holds in $\mathcal{U}{(M)}$

Let the identity element be $e$.
$a, b \in \mathcal{U}{(M)} \implies a, b \in M \implies a*b \in M$.
$(a*b)*(b^{-1} * a^{-1}) = a * a^{-1} = e$, so $a*b$ is invertible (namely, its inverse is $b^{-1} * a^{-1}$), which implies $a*b \in \mathcal{U}{(M)}$.

Claim 4: Every element in $\mathcal{U}{(M)}$ has an inverse

This is true by the definition of $\mathcal{U}{(M)}$.

By definition, these four claims are sufficient to determine $\mathcal{U}{(M)}$ is a group.

Where I'm stuck:

Please check :)
0 replies
palindrome868
Aug 5, 2024
0 replies
J
H
Exercise 0.1
elee310   0
Jul 27, 2024
What I've tried so far:

1) $$\forall a \in M, e*a=a*e=a$$$$\text{Similarily, } \forall a \in M, e'*a=a*e'=a$$$$e*e'=e'*e=e' \land e'*e=e*e'=e \rightarrow e'=e'*e=e$$$$\therefore e'=e$$2)
$$u*v=v*u=e \land u*v'=v'*u=e \rightarrow u*v=e=u*v'$$$$v*(u*v)=v*(u*v') \rightarrow (v*u)*v=(v*u)*v'$$$$e*v=e*v'$$$$\therefore v=v'$$
3) $$U(M): {\forall a,b \in M \text{ s.t. } a*b=b*a=e}$$$$e \text{ s.t. } e*e=e*e=e \rightarrow e \in U(M)$$$$\text {let }x,y \in U(M) \land x*y=z$$$$\text{By def. } x^{-1} \text{ s.t. } x*x^{-1}=x^{-1}*x=e \land y^{-1} \text{ s.t. } y*y^{-1}=y^{-1}*y=e \in U(M)$$$$ \rightarrow x*y*y^{-1}*x^{-1} = x*(y*y^{-1})*x^{-1}$$$$ = x*(e)*x^{-1} = x*e*x^{-1}=x*x^{-1} = e \rightarrow z^{-1}= y^{-1}*x^{-1} \rightarrow z \text{ is invertible}$$$$\therefore \forall x,y \in U(M) z=x*y \land z^{-1}=y^{-1}*x^{-1} \in U(M)$$$\text{As U(M) is closed under *, has an identity e, and every element is invertible, U(M) is a group}$
Where I'm stuck:
General: I am not quite sure how to format these kinds of questions
<Describe what's confusing you, or what your question is here!>
0 replies
elee310
Jul 27, 2024
0 replies
J
H
Exercise 0.1
hkoo   3
N Jun 16, 2024 by felixgotti
What I've tried so far:

(1) Suppose that monoid has two different identity e,e'. Since identity is commutative, $e*e'=e'*e$.
and $e*e'=e, e'*e=e'$. therefore $e=e'$.

(2) Suppose that for $u \in M$, there exist two different inverse $v,v' \in M$. we know that $u*v=v*u=e$.

$v'=v'*e=v'*(u*v)=(v'*u)*v = e*v = v$. so inverse of u is unique

(3) Group is a set with binary operation satisfying following 4 properties.

1. associativity, 2. identity, 3. closure, 4. inverse.

since $\mathcal{U}(M)$ is subset of monoid and e(=identity) has inverse, it satisfies (1)&(2)

for $u_1,u_2  \in \mathcal{U}(M)$, there exists $(v_2*v_1) \in \mathcal{U}(M)$ s.t $v_1,v_2$ are inverse of $u_1,u_2$
and $(u_1*u_2)*(v_2*v_1) = (u_1)*(u_2*v_2)*(v_1) = (u_1)*(e)*(v_1) = e$. it implies $\mathcal(M)$ satisfies (3)

Last, $\mathcal{U}(M)$ satifies (4) by definition.

$\mathcal{U}(M)$ is a set which holds all 4 propeties. so it is a group

<Describe what you have tried so far here. That way, we can do a better job helping you!>


Where I'm stuck:
<Describe what's confusing you, or what your question is here!>
I wonder that inverse of u is always commutative like $u*v=v*u=e$.
Can we prove commutativity with only conditions such that $u*v=e, u*e=e*u=u $
3 replies
hkoo
May 20, 2024
felixgotti
Jun 16, 2024
J
No more topics!
H
J
H
Exercise 0.1(part 1)
Thayaden   1
N Sep 11, 2024 by Thayaden
let $b\in M$ by definition,
$$(1):~~e*b=b*e=b,$$$$(2):~~e'*b=b*e'=b$$this is true for all $b$ thus let $b=e'$ this might lead us to (from $(1)$),
$$e*e'=e'*e=e'$$$$e*e'=e'$$Now let $b=e$ (using $(2)$),
$$e'*e=e*e'=e$$$$e*e'=e$$By the transitive property,
$$\boxed{e'=e}$$as the first condition is true, $e,e'\in M$ we might then say that given all identity elements of $M$ denoted as $e_i$ we might have,
$$e_1=e_2$$and inductively,
$$e_k=e_{k+1}$$thus,
$$e_1=e_2=e_3=e_4=\cdots$$. Or in plain text, we might say that as one identity is equal to another then if we have some identity it is the same as the identity we already have.
1 reply
Thayaden
Sep 11, 2024
Thayaden
Sep 11, 2024
J