• Answer: False
• Justification: A set with zero members is called the empty set and is written as $\emptyset$. The power set of any set $A$ is defined as the set of all subsets of $A$. Since the empty set $\emptyset$ is a subset of itself, the power set of $\emptyset$ is $2^\emptyset = \{\emptyset\}$. Thus, the power set is not empty; it contains exactly one element (the empty set itself), meaning $|2^\emptyset| = 1 = 2^0$.

• Answer: True
• Justification: A sequence of objects is a list in a specified order. In a sequence, order and repetition matter; for example, the sequence $(7, 21, 57)$ is not the same as $(57, 7, 21)$, and $(7, 7, 21, 57)$ is a distinct sequence. Conversely, in a set, order and repetition do not matter; the set $\{7, 21, 57\}$ is identical to $\{7, 7, 21, 57\}$.

• Answer: False
• Justification: By definition, if the domain of a function $f$ is all of $S_1$, it is called a total function on $S_1$. If the domain is only a subset of $S_1$, $f$ is instead referred to as a partial function.

• Answer: True
• Justification: If we have a defined equivalence relation on a set $S$, we can use it to partition the set into equivalence classes. By definition of a partition, the subsets are disjoint and their union equals the original set $S$.

• Correct Options: B, C, D
• Justification:
  • A is incorrect because although the alphabet $\Sigma$ is finite, $\Sigma^*$ and $\Sigma^+$ are always infinite sets since there is no limit on the length of the strings we can construct.
  • B is correct because $\Sigma^*$ is defined as the set of strings obtained by concatenating zero or more symbols from $\Sigma$, which always contains the empty string.
  • C is correct because $\Sigma^+$ is defined specifically to exclude the empty string from $\Sigma^*$.
  • D is correct because the length of a string is the number of symbols it contains (with the empty string having a length of zero), meaning a string’s length is always a non-negative integer.

• Correct Options: B, C, D
• Justification: The Cartesian product $S_1 \times S_2$ is the set of all ordered pairs where the first element is a member of $S_1$ and the second element is a member of $S_2$.
  • A is incorrect because while $2 \in S_1$, $4$ is not an element of $S_2$. Therefore, $(2, 4) \notin S_1 \times S_2$.
  • B is correct because $4 \in S_1$ and $2 \in S_2$.
  • C is correct because $2 \in S_1$ and $3 \in S_2$.
  • D is correct because $2 \in S_1$ and $2 \in S_2$.

• Formulating the Proof: Let $P(n)$ be the statement: “If a finite set $S$ has size $|S| = n$, then the size of its power set $2^S$ is $|2^S| = 2^n$.”

  • Basis Step: Let $n = 0$. The only set of size $0$ is the empty set $\emptyset$. As established in Question 1, $2^\emptyset = \{\emptyset\}$, which has a size of $1$. Since $2^0 = 1$, the basis step holds.

  • Inductive Hypothesis: Assume that for any set $S$ of size $|S| = k \geq 0$, the power set size is $|2^S| = 2^k$.

  • Inductive Step: We must show that a set $S'$ of size $k + 1$ has a power set of size $2^{k+1}$. Let $S' = S \cup \{x\}$, where $|S| = k$ and $x \notin S$ (meaning $S'$ has $k+1$ elements). We can divide the subsets of $S'$ into two disjoint collections:

    1. Subsets of $S'$ that do not contain $x$. These are precisely the subsets of $S$. By our inductive hypothesis, there are exactly $2^k$ such subsets.
    2. Subsets of $S'$ that do contain $x$. Each of these subsets can be formed by taking a subset of $S$ and adding the element $x$ to it. Since there are $2^k$ subsets of $S$, there are exactly $2^k$ such subsets in this collection as well.

    The total number of subsets of $S'$ is the sum of these two disjoint groups:

    $$|2^{S'}| = 2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$$

    This completes the inductive step, showing that $P(k) \implies P(k+1)$. Thus, the statement holds for all finite sets. $\blacksquare$

• Answer: $\{ab, aa, b, \lambda\}$
• Derivation: Union combines all elements of both sets into a single set.

• Answer: $\{abb, ab, aab, aa\}$
• Derivation: Concatenation attaches every string from $L_1$ to every string from $L_2$.
  • $ab \cdot b = abb$
  • $ab \cdot \lambda = ab$
  • $aa \cdot b = aab$
  • $aa \cdot \lambda = aa$

• Answer: $\{abab, abaa, aaab, aaaa\}$
• Derivation: We concatenate every element in $L_1$ with every element in $L_1$:
  • $ab \cdot ab = abab$
  • $ab \cdot aa = abaa$
  • $aa \cdot ab = aaab$
  • $aa \cdot aa = aaaa$

• Answer: $\{ba, aa\}$
• Derivation: The reverse of a language is the set of all string reversals. Reversing the string $ab$ gives $ba$. Reversing the string $aa$ gives $aa$.

To be an equivalence relation, $\equiv_7$ must satisfy reflexivity, symmetry, and transitivity.

• Reflexivity: For any $i \in \mathbb{N}$, $i - i = 0$. Since $0 = 7 \times 0$, $0$ is a multiple of 7. Thus, $i \equiv_7 i$ holds.

• Symmetry: Suppose $i \equiv_7 j$. This means $i - j$ is a multiple of 7 (i.e., $i - j = 7k$ for some integer $k$). We can rewrite this as $j - i = 7(-k)$. Since $-k$ is also an integer, $j - i$ is a multiple of 7, meaning $j \equiv_7 i$.

• Transitivity: Suppose $i \equiv_7 j$ and $j \equiv_7 k$. This implies $i - j = 7x$ and $j - k = 7y$ for some integers $x, y$. Summing these two equations yields:

  $$(i - j) + (j - k) = 7x + 7y \implies i - k = 7(x + y)$$

  Since $x + y$ is an integer, $i - k$ is a multiple of 7. Thus, $i \equiv_7 k$.

  Since all three properties are satisfied, $\equiv_7$ is an equivalence relation.

The relation $\equiv_7$ partitions $\mathbb{N}$ into 7 distinct equivalence classes based on the remainder when divided by 7:

• $ = \{0, 7, 14, 21, \dots\}$
• $ = \{1, 8, 15, 22, \dots\}$
• $ = \{2, 9, 16, 23, \dots\}$
• $ = \{3, 10, 17, 24, \dots\}$
• $ = \{4, 11, 18, 25, \dots\}$
• $ = \{5, 12, 19, 26, \dots\}$
• $ = \{6, 13, 20, 27, \dots\}$

• Step 1: Write down the start variable $S$.
• Step 2: Apply production rule $S \rightarrow aSb$ to yield the sentential form: $aSb$.
• Step 3: Apply production rule $S \rightarrow aSb$ to the inner $S$ to yield: $aaSb\mathit{b}$.
• Step 4: Apply production rule $S \rightarrow \lambda$ to yield the terminal string: $aabb$.

The derivation is:

• Claim: Every sentential form generated by $G$ must be of the form $a^i S b^i$ for some $i \geq 0$.

• Basis Step: Before any production rules are applied, we have the starting sentential form $S$. This corresponds to $i = 0$ ($a^0 S b^0 = S$), which establishes our basis.

• Inductive Hypothesis: Assume that any sentential form derived in $k$ steps is of the form $a^k S b^k$.

• Inductive Step: To get a new sentential form in step $k+1$, we must apply the recursive production rule $S \rightarrow aSb$ to the variable $S$ in $a^k S b^k$. This yields:

  $$a^k (aSb) b^k = a^{k+1} S b^{k+1}$$

  This matches the required form for $i = k+1$.

  By mathematical induction, every sentential form containing the variable $S$ is of the form $a^n S b^n$ for some $n \geq 0$. To complete the derivation and obtain a terminal sentence, we must apply the production rule $S \rightarrow \lambda$. Substituting $\lambda$ for $S$ in $a^n S b^n$ yields the sentence $a^n b^n$. Thus, $L(G) = \{a^n b^n \mid n \geq 0\}$. $\blacksquare$