MATH 415 Lecture 2

« previous | Thursday, August 29, 2013 | next »

Section 3: Isomorphic Binary Structures

A binary structure consits of a set $S$ and a binary operation $*$.

Tables from the book define binary structures:

• $S_{1}=\left\{a,b,c\right\}$, $*\,\!$, ${\hat {*}}$, ${\tilde {*}}$
• $S_{2}=\left\{\#,\$,\&\right\}$, $*'\,\!$
• $S_{3}=\left\{x,y,z\right\}$, $*''\,\!$

($i$^th row and $j$^th column represent $s_{i}*s_{j}$ for $s_{i},s_{j}\in S$)

Table 3.1 $*\,\!$ $a$ $b$ $c$ $a$ $c$ $a$ $b$ $b$ $a$ $b$ $c$ $c$ $b$ $c$ $a$	Table 3.2 $*'\,\!$ $\#$ $\$$ $\&$ $\#$ $\&$ $\#$ $\$$ $\$$ $\#$ $\$$ $\&$ $\&$ $\$$ $\&$ $\#$	Table 3.3 $*''\,\!$ $x$ $y$ $z$ $x$ $x$ $y$ $z$ $y$ $y$ $z$ $x$ $z$ $z$ $x$ $y$
Table 3.4 $*''\,\!$ $y$ $x$ $z$ $y$ $z$ $y$ $x$ $x$ $y$ $x$ $z$ $z$ $x$ $z$ $y$	Table 3.5 ${\tilde {*}}$ $a$ $b$ $c$ $a$ $b$ $b$ $b$ $b$ $b$ $b$ $b$ $c$ $b$ $b$ $b$	Table 3.6 ${\hat {*}}$ $a$ $b$ $c$ $a$ $c$ $a$ $b$ $b$ $b$ $c$ $a$ $c$ $a$ $b$ $c$

Tables 3.1 and 3.2 are bijections of each other with the following transformation:

• $a$ ↔ #
• $b$ ↔ $
• $c$ ↔ &

Table 3.6 is reflexive

Definition

Let $(S,*)$ and $(S',*')$ be binary algebraic structures. An isomorphism of $S$ with $S'$ is a one-to-one function $\phi$ mapping $S$ onto $S'$ such that $\phi (x*y)=\phi (x)*'\phi (y)$ for all $x,y\in S$.

Notation: $(S,*)\simeq (S',*')$

Since $\phi$ is both one-to-one and onto, we call it a bijection.

Note: A function that is not a bijection but still satisfies the property $\phi (x*y){=}\phi (x)*'\phi (y)$ is called a homomorphism. In other words, an isomorphism is a bijective homomorphism

Recall isomorphic structures from yesterday:

• $\left\langle U_{n},\cdot \right\rangle \simeq \left\langle \mathbb {Z} _{n},+_{n}\right\rangle$
• $\left\langle U,\cdot \right\rangle \simeq \left\langle \mathbb {R} _{2\pi },+_{2\pi }\right\rangle \simeq \left\langle \mathbb {R} _{c},+_{c}\right\rangle$

Showing Non-Isomorphism

Keep word invariant in mind...

Examples

Addition and Multiplication

$\left\langle \mathbb {R} ,+\right\rangle \simeq \left\langle \mathbb {R} ^{+},\cdot \right\rangle$

Transformation function is $\phi =\mathrm {e} ^{x}$: it is a bijection because

• (one-to-one) monotonically increasing
• (onto) $\forall z>0~\exists t~\mathrm {e} ^{t}=z$

It is homomorphic because $\mathrm {e} ^{x+y}=\mathrm {e} ^{x}\cdot \mathrm {e} ^{y}$

It also has an inverse mapping $\phi ^{-1}=\ln {y}$

Integers and Even Integers

$\left\langle \mathbb {Z} ,+\right\rangle \simeq \left\langle 2\mathbb {Z} ,+\right\rangle$

$\phi :m\to 2m$

Easy to see bijection homomorphism: $\phi (m+k)=2(m+k)=2m+2k=\phi (m)+\phi (k)$

$\mathbb {Z}$ and $\mathbb {Z} ^{+}$ have same cardinality (both countable), but

$\left\langle \mathbb {Z} ,\cdot \right\rangle \not \simeq \left\langle \mathbb {Z} ^{+},\cdot \right\rangle$

Assume we have a homomorphic function $\phi (m\,n)=\phi (m)\cdot \phi (n)$, then this would satisfy equation $x\cdot x=x$. There are two solutions in $\mathbb {Z}$, namely 0 and 1, but only one solution in $\mathbb {Z} ^{+}$, namely 1. This is a contradiction.

Identity

Given a binary structure $\left\langle S,*\right\rangle$, we call $e\in S$ an identity for $*$ if $e*s=s*e=s$ for all $s\in S$

• 1 is identity for multiplication
• 0 is identity for addition

Theorem 3.13

Uniqueness of Identity Element

A binary structure has at most one identity element.

Proof by contradiction. Assume we have two distinct identities $e_{1},e_{2}\in S$ for $*$. Then $e_{1}*e_{2}=e_{2}$ and $e_{1}*e_{2}=e_{1}$. By transitivity, $e_{2}=e_{1}$. Contradiction.

Groups

A group $(G,*)$ has the following axioms:

1. $*$ is associative
2. There is an identity element $e\in G$
3. Corresponding to each $a\in G$, there is an "inverse" element $a^{-1}$ such that $a*a'=a^{-1}*a=e$

Group $\left\langle G,*\right\rangle$ is abelian (or commutative) if $*$ is commutative. That is, $a*b=b*a$ for all $a,b\in G$.

Examples

$\left\langle U,\cdot \right\rangle$ is a group:

1. multiplication is associative
2. identity element is 1
3. inverse of $z=\mathrm {e} ^{i\,\theta }$ is $z^{-1}=\mathrm {e} ^{-i\,\theta }$.

• $\left\langle \mathbb {Z} ,+\right\rangle$ is an abelian group
• $\left\langle \mathbb {Q} ,+\right\rangle$ is an abelian group
• $\left\langle \mathbb {R} ,+\right\rangle$ is an abelian group
• $\left\langle \mathbb {Z} ^{+},\cdot \right\rangle$ is not a group because there is no inverse for 2
• $\left\langle M_{n}(\mathbb {R} ),\cdot \right\rangle$ is not a group since not all matrices are invertible, however
• $\left\langle M_{n}^{\cdot }(\mathbb {R} ),\cdot \right\rangle$ (where $M_{n}^{\cdot }(\mathbb {R} )$ is the set of invertible matrices of size $n$) is a group