Problem 5 - Applied Discrete Structures

Question

Which of the following sets are subgroups of \(\mathbb{Z} \times \mathbb{Z} ?\) Give a reason for any negative answers. (a) \\{0\\} (b) \(\\{(2 j, 2 k) \mid j, k \in \mathbb{Z}\\}\) (c) \(\\{(2 j+1,2 k) \mid j, k \in \mathbb{Z}\\}\) (d) \(\left\\{\left(n, n^{2}\right) \mid n \in \mathbb{Z}\right\\}\) (e) \(\\{(j, k) \mid j+k\) is even \(\\}\)

Step-by-Step Solution

Answer

Sets (a), (b), and (e) are subgroups; sets (c) and (d) are not.

Step 1: Check Subgroup Criteria for Set (a)

To determine if \( \{0\} \) is a subgroup of \( \mathbb{Z} \times \mathbb{Z} \), we must verify the subgroup criteria: closure under addition, existence of the identity element, and existence of inverses.\ - **Identity**: The zero vector \((0,0)\) is present in the set.- **Closure**: Adding any two elements of this set, which is always \((0,0) + (0,0) = (0,0)\), results in \((0,0)\), which is in the set.- **Inverses**: The inverse of \((0,0)\) is \((0,0)\), also in the set.Thus, \( \{0\} \) is a subgroup.

Step 2: Evaluate Set (b)

Set \( \{(2j, 2k) \mid j, k \in \mathbb{Z}\} \) forms a subgroup if it is closed under addition, contains the identity, and has inverses.\- **Identity**: The identity \((0,0)\) is present as \((2 \times 0, 2 \times 0)\).- **Closure**: If \((2j_1, 2k_1) + (2j_2, 2k_2) = (2(j_1+j_2), 2(k_1+k_2))\), the result remains in the set because sums of integers are integers.- **Inverses**: The inverse of \((2j, 2k)\) is \((-2j, -2k)\), which is also in the form \((2j, 2k)\).Therefore, \( \{(2j, 2k) \mid j, k \in \mathbb{Z}\} \) is a subgroup.

Step 3: Investigate Set (c)

Set \( \{(2j+1, 2k) \mid j, k \in \mathbb{Z}\} \) must satisfy the subgroup property.\- **Identity**: The identity \((0,0)\) is not in the set because \(2j+1\) can never be zero.Since the identity is not part of the set, \( \{(2j+1, 2k) \mid j, k \in \mathbb{Z}\} \) is not a subgroup.

Step 4: Assess Set (d)

Examine the criteria for \( \left\{\left(n, n^{2}\right) \mid n \in \mathbb{Z}\right\} \) to determine subgroup status.\- **Identity**: The identity element \((0,0)\) belongs to the set as \((0, 0^2)\).- **Closure**: Consider \((n_1, n_1^2) + (n_2, n_2^2) = (n_1+n_2, n_1^2+n_2^2)\). The result is not of the form \((n, n^2)\), failing closure.Because the set is not closed under addition, it is not a subgroup.

Step 5: Examine Set (e)

Consider if \( \{(j, k) \mid j+k \text{ is even}\} \) forms a subgroup by subgroup criteria.\- **Identity**: The identity \((0,0)\) is in the set since \(0+0 = 0\), which is even.- **Closure**: If \((j_1, k_1)\) and \((j_2, k_2)\) are in the set, then \((j_1+j_2) + (k_1+k_2) = (j_1 + k_1) + (j_2 + k_2)\) which is even if both sums are even, ensuring closure.- **Inverses**: The inverse of \((j, k)\) is \((-j, -k)\), and since \(j+k\) is even, \(-j - k\) is also even.Hence, \( \{(j, k) \mid j+k \text{ is even}\} \) is a subgroup.

Key Concepts

Integer Groups

Integer groups play a fundamental role in understanding abstract algebra. A group is a mathematical structure consisting of a set equipped with an operation that combines any two elements to form a third. When we specifically talk about integer groups, we're referring to groups whose elements are integers. The typical operation in this context is addition. For example, the set of all integers, denoted by \( \mathbb{Z} \), with the operation of addition, forms a group. This is because it satisfies the group axioms: closure, associativity, identity, and inverses.

In dealing with subgroups, we often consider different sets of integer pairs, such as those in \( \mathbb{Z} \times \mathbb{Z} \). This notation stands for all ordered pairs of integers \((m, n)\), where both \(m\) and \(n\) belong to \( \mathbb{Z} \). To find subsets of \( \mathbb{Z} \times \mathbb{Z} \) that are themselves groups (i.e., subgroups), we investigate each candidate set by verifying key group properties.

Closure Property

The closure property is essential in determining if a subset qualifies as a subgroup in the context of integer groups. Closure under an operation means that when you perform the operation on any two elements in the set, the result is still an element within the same set. For example, in the group of integers \( \mathbb{Z} \) under addition, the sum of any two integers is still an integer, exemplifying the closure property.

When assessing subsets such as those in \( \mathbb{Z} \times \mathbb{Z} \), we perform operations like addition on the pairs. Take the set \( \{(2j, 2k) \mid j, k \in \mathbb{Z}\} \): adding two such elements \((2j_1, 2k_1) + (2j_2, 2k_2)\) results in \((2(j_1+j_2), 2(k_1+k_2))\), which is also in the set, showing closure. If the result of the operation can ever lie outside the set, the set does not have closure, thereby failing to be a subgroup.

Identity Element

The identity element in a group is a unique element that, when combined with any other element of the group using the group operation, leaves that element unchanged. For groups under addition, like the integers \( \mathbb{Z} \), the identity element is 0 because adding 0 to any integer leaves it unchanged.

Subgroups of \( \mathbb{Z} \times \mathbb{Z} \) must include the identity element \((0, 0)\). In subsets such as \( \{(2j+1, 2k) \mid j, k \in \mathbb{Z}\} \), the identity element \((0,0)\) is absent since the first component \(2j+1\) does not satisfy 0. Therefore, one crucial step in subgroup evaluation is verifying the presence of the identity element, as absence disqualifies any set from being a subgroup.

Inverses in Groups

In group theory, for any element in a group, there should exist an inverse such that when combined with the element using the group operation, yields the identity element. In the case of the group operations involving addition, each integer \(n\) has an inverse \(-n\), since \(n + (-n) = 0\).

For subgroups like \( \{(j, k) \mid j+k \text{ is even}\} \), each element \((j, k)\) must have an inverse \((-j, -k)\) that also satisfies the condition for inclusion in the set. Since the condition \(j+k\) being even implies that \(-j-k\) is also even, every element effectively has an inverse within the set, satisfying one of the fundamental requirements for a set to be a subgroup. If such inverses did not exist for at least one element, the set wouldn't qualify as a subgroup.