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=\{a,b,c\}$, $*$, $\widehat{*}$, $\widetilde{*}$
• $S_2=\{\mathrm{\#},\mathrm{\$},\mathrm{\&}\}$, ${*}^{\prime }$
• $S_3=\{x,y,z\}$, ${*}^{″}$

($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 ${*}^{\prime }$ $\mathrm{\#}$ $\mathrm{\$}$ $\mathrm{\&}$ $\mathrm{\#}$ $\mathrm{\&}$ $\mathrm{\#}$ $\mathrm{\$}$ $\mathrm{\$}$ $\mathrm{\#}$ $\mathrm{\$}$ $\mathrm{\&}$ $\mathrm{\&}$ $\mathrm{\$}$ $\mathrm{\&}$ $\mathrm{\#}$	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 $\widetilde{*}$ $a$ $b$ $c$ $a$ $b$ $b$ $b$ $b$ $b$ $b$ $b$ $c$ $b$ $b$ $b$	Table 3.6 $\widehat{*}$ $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^{\prime },{*}^{\prime })$ be binary algebraic structures. An isomorphism of $S$ with $S^{\prime }$ is a one-to-one function $\varphi$ mapping $S$ onto $S^{\prime }$ such that $\varphi (x*y)=\varphi (x){*}^{\prime }\varphi (y)$ for all $x,y\in S$.

Notation: $(S,*)\simeq (S^{\prime },{*}^{\prime })$

Since $\varphi$ 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 $\varphi (x*y)=\varphi (x){*}^{\prime }\varphi (y)$ is called a homomorphism. In other words, an isomorphism is a bijective homomorphism

Recall isomorphic structures from yesterday:

• $⟨U_n,\cdot ⟩\simeq ⟨{\mathbb{\mathbb{Z}}}_n,{+}_n⟩$
• $⟨U,\cdot ⟩\simeq ⟨{\mathbb{ℝ}}_{2\pi },{+}_{2\pi }⟩\simeq ⟨{\mathbb{ℝ}}_c,{+}_c⟩$

Showing Non-Isomorphism

Keep word invariant in mind...

Examples

Addition and Multiplication

$⟨\mathbb{ℝ},+⟩\simeq ⟨{\mathbb{ℝ}}^{+},\cdot ⟩$

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

• (one-to-one) monotonically increasing
• (onto) $\mathrm{\forall }z>0\mathrm{\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 ${\varphi }^{-1}=\ln y$

Integers and Even Integers

$⟨\mathbb{\mathbb{Z}},+⟩\simeq ⟨2\mathbb{\mathbb{Z}},+⟩$

$\varphi :m\to 2m$

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

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

$⟨\mathbb{\mathbb{Z}},\cdot ⟩\simeq ̸⟨{\mathbb{\mathbb{Z}}}^{+},\cdot ⟩$

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

Identity

Given a binary structure $⟨S,*⟩$, 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^{\prime }=a^{-1}*a=e$

Group $⟨G,*⟩$ is abelian (or commutative) if $*$ is commutative. That is, $a*b=b*a$ for all $a,b\in G$.

Examples

$⟨U,\cdot ⟩$ 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 }$.

• $⟨\mathbb{\mathbb{Z}},+⟩$ is an abelian group
• $⟨\mathbb{\mathbb{Q}},+⟩$ is an abelian group
• $⟨\mathbb{ℝ},+⟩$ is an abelian group
• $⟨{\mathbb{\mathbb{Z}}}^{+},\cdot ⟩$ is not a group because there is no inverse for 2
• $⟨M_n(\mathbb{ℝ}),\cdot ⟩$ is not a group since not all matrices are invertible, however
• $⟨M_n^{\cdot }(\mathbb{ℝ}),\cdot ⟩$ (where $M_n^{\cdot }(\mathbb{ℝ})$ is the set of invertible matrices of size $n$) is a group