ZK-Bootcamp - Homework 2 - Groups and Fields

Problem 1

Let our set be real numbers. Show a binary operator that is not closed

Set is closed under an operation if applying that operation to elements within the set always results in an element that’s still within the set.

On a set of real numbers, the binary operator of “root” $\sqrt[a]{b}$ is not closed.

e.g Two real numbers, 2 and -1, $\sqrt[2]{-1}$ does not result in a real number as $\sqrt[2]{-1} = i$ which is not a real number

Problem 2

Find a binary operator that is closed but not associative for real numbers

A group is considered associative if grouping of operations doesn’t affect the result e.g (a∗b)∗c=a∗(b∗c)

On a set of real numbers, the binary operator of “power” is closed but not associative.

e.g Three real numbers, 2, 3 and 4,

$(2^3)^4=2^(3^4)$

    p23 = pow(2, 3);
    p23_4 = pow(p23, 4);
    
    p34 = pow(3, 4);
    p2_34 = pow(2, p34);
    
    assert p23_4 != p2_34

Problem 3

What algebraic structure (group, monoid, semigroup, etc) is all even integers under addition

1. Closed - Yes. When even numbers are added, they result in even numbers. 2m + 2n = 2(m+n)
2. Associative - Yes. Integers under addition are always associative.
3. Identity - Yes. Since 0 is an even integer, adding anything with 0 results in the same value.
4. Inverse - Yes. Since even integers, include negative integers, every element has a negative or postive version of itself as the inverse.

Even integers under addition is a Group.

Problem 4

What algebraic structure is all odd integers under multiplication?

1. Closed - Yes. When odd integers are multiplied, they result in odd numbers. (2m+1)*(2n+1) = 2mn+2m+2n+1 = 2(mn+m+n) + 1
2. Associative - Yes. Integers under multiplication are always assocaitive.
3. Identity - Yes. Since 1 is an odd integers, multiplying anything with 1 results in same value.
4. Inverse - No. integers do not have multiplicative inverses which are integers.

Odd integers under multiplication is a Monoid.

Problem 5

Let our set be 3 x 2 matrices of integers under addition. What algebraic structure is this?

e.g 3x2 Matrix \(\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ a_{31} & a_{32} \end{bmatrix}\)

1. Closed - Yes. Addition is done pairwise. So a 3x2 matrix under addition results in a 3x2 matrix. \(\begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{bmatrix} + \begin{bmatrix} 6 & 5 \\ 4 & 3 \\ 2 & 1 \end{bmatrix} = \begin{bmatrix} 7 & 7 \\ 7 & 7 \\ 7 & 7 \end{bmatrix}\)
2. Associative - Yes. Pairwise addition is associative. $$ \left( \begin{bmatrix} 1 & 2
   3 & 4
   5 & 6 \end{bmatrix} + \begin{bmatrix} 6 & 5
   4 & 3
   2 & 1 \end{bmatrix} \right) + \begin{bmatrix} 1 & 1
   1 & 1
   1 & 1 \end{bmatrix}

=

\begin{bmatrix} 1 & 2
3 & 4
5 & 6 \end{bmatrix} + \left( \begin{bmatrix} 6 & 5
4 & 3
2 & 1 \end{bmatrix}

+ \begin{bmatrix} 1 & 1
1 & 1
1 & 1 \end{bmatrix} \right) $$

1. Identity - Yes. Any 3x2 matrix when added with the Zero matrix results in itself. \(\begin{bmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 0 \end{bmatrix}\)

2. Inverse - Yes. Since 3x2 matrix of integers, include negative integers, every element has a negative or postive version of itself as the inverse.

3 x 2 matrices of integers under addition is a Group.

Problem 6

Suppose our set is all rational numbers $\mathbb{Q}$ except $0$ and our binary operator is division. What algebraic structure is this?

1. Closed - Yes. When any rational number p1/q1 is divided by p2/q2, the result is another rational number. \(\frac{\frac{p1}{q1}}{\frac{p2}{q2}} = \frac{p1*q2}{q1*q1}\)

2. Associative - No. Division under rational numbers is not associative. $$ p1 = 1, q1 = 2
   p2 = 3, q2 = 4
   p3 = 5, q3 = 6\

\frac{\left( \frac{\frac{p1}{q1}}{\frac{p2}{q2}} \right)}{\frac{p3}{q3}} = \frac{\frac{p1}{q1}}{\left(\frac{\frac{p2}{q2}}{\frac{p3}{q3}}\right)}
\frac{\left( \frac{\frac{1}{2}}{\frac{3}{4}} \right)}{\frac{5}{6}} = \frac{\frac{1}{2}}{\left(\frac{\frac{3}{4}}{\frac{5}{6}}\right)}
\frac{\frac{14}{23}}{\frac{5}{6}} = \frac{\frac{1}{2}}{\frac{36}{45}}
\frac{\frac{4}{6}}{\frac{5}{6}} = \frac{\frac{1}{2}}{\frac{18}{20}}
\frac{46}{65} = \frac{120}{218}
\frac{24}{30} = \frac{20}{36}
\frac{4}{6} = \frac{5}{9}
$$

Rational numbers under division is a Magma.

Problem 7

Suppose our set is 𓅔 𓆓 𓆟

Define a binary operator that makes it a group. You can define the binary operator’s property by constructing a table where the left two columns are the inputs and the right column is the result. Remember you need to allow that the inputs can be the same, for example (𓅔,𓅔) —> ?

1. Closed - Yes. Output of all the operation are within the group.
2. Associative - Yes. \((𓅔 \cdot 𓆓) \cdot 𓆟 = 𓅔 \cdot (𓆓 \cdot 𓆟)\\ 𓆓 \cdot 𓆟 = 𓅔 \cdot 𓅔\\ 𓅔 = 𓅔\)
3. Identity - Yes. $a \cdot 𓅔 = a $. 𓅔 is the identity element.
4. Inverse - Yes. $a \cdot a^{-1} = 𓅔$. Inverse of 𓅔 is 𓅔, 𓆓 is 𓆟, 𓆟 is 𓆓.

Define a binary operator that makes it not a group (but it should be closed). Hint: if there is no identity element, then it is not a group

1. Closed - Yes. Output of all the operation are within the group.
2. Associative - Yes. \((𓅔 \cdot 𓆓) \cdot 𓆟 = 𓅔 \cdot (𓆓 \cdot 𓆟)\\ 𓅔 \cdot 𓆟 = 𓅔 \cdot 𓆓\\ 𓅔 = 𓅔\)
3. Identity - Yes. $a \cdot 𓆓 = a $. 𓆓 is the identity element.
4. Inverse - No. $a \cdot a^{-1} = 𓆓$ does not exist for all elements.

$𓅔 \cdot 𓅔 = 𓆓$. Inverse of 𓅔 is 𓅔.

$𓆓 \cdot anything = 𓆓$

$𓆟 \cdot nothing = 𓆓$

The above set under the specifiend operation is a Monoid, and not a group.

Problem 8

What is the size of the smallest possible group? (Remember, a group is a set, so this is asking how large the set is)

Smallest group is {1} under multiplication.

1. Closed - Yes. 1*1 = 1
2. Associative - Yes. (1* 1)* 1 = 1(11)
3. Identity - Yes. 1* i = 1*1 = 1
4. Inverse - Yes. 1*1 = i = 1.