1
$\begingroup$

I am reading Automata and Computability by Dexter C. Kozen and I am in the first chapter entitled Strings and Sets.

If we have a set $A=\{ab,b\}$ do we get to assume that the null string $\epsilon$ is also a member of that set? If we have another set $B=\{\epsilon\}$, does $A\cap B = \{\epsilon\}$ or does $A∩B=\emptyset$?

On a related note, I am having trouble understanding the meaning of a little chunk in the textbook. What does "family of set indexed by another set $I$" mean? What does the set $I$ consist of here? I am very confused by the notation as well. Anything you can do to help me understand the excerpt below is appreciated.

Set concatenation distributes over union: \begin{align} A(B\cup C) &= AB \cup AC, \\ (A \cup B)C &= AC \cup BC. \end{align} In fact, concatenation distributes over the union of any family of sets. If $\{B_i \mid i \in I \}$ is any family of sets indexed by another set $I$, finite or infinite, then \begin{align} A \bigl( \bigcup_{i \in I} B_i \bigr) &= \bigcup_{i \in I} AB_i, \\ \bigl( \bigcup_{i \in I} B_i \bigr) A &= \bigcup_{i \in I} B_iA. \end{align} Here $\bigcup_{i \in I} B_i$ denotes the union of all the sets $B_i$ for $i \in I$. An element $x$ is in this union iff it is in one of the $B_i$.

$\endgroup$
2
  • $\begingroup$ No, the empty string is a string that is not an element of $\{ab,b\}$ (if $a$ and $b$ are representing letters here). $\endgroup$
    – plop
    Feb 2 at 23:15
  • $\begingroup$ $I$ is just a set of indexes. For example, $I=\{1,2,3\}$ then $\bigcup_{i\in I}B_i$ is the same as $B_1\cup B_2\cup B_3$. But the set $I$ could be empty or it could be an infinite set, when you need to take a union of infinitely many sets. $\endgroup$
    – plop
    Feb 2 at 23:16
1
$\begingroup$

The notation $\{ x_1,x_2,x_3,\ldots,x_n \}$ means "the set of elements $x_1,x_2,x_3,\ldots,x_n$". In particular, all elements in the set are listed. If an element isn't listed, it doesn't belong to the set. For example, $\epsilon$ is not an element of $\{ab,b\}$. There is absolutely nothing special about $\epsilon$. It is a bona fide word, and undergoes no special treatment. It is not an element of $\{ab,b\}$ just as $abba$ is not an element of $\{ab,b\}$.

As for your second question, here is a family of sets indexed by $I = \{a,b,c\}$: $$ B_a = \{a,ba\}, B_b = \{b,ba\}, B_c = \{\epsilon,aa,bbb\}. $$ The union of this family is $$ \bigcup_{i \in I} B_i = B_a \cup B_b \cup B_c = \{\epsilon, a, b, aa, ba, bbb \}. $$ The set $I$ is completely arbitrary. It could be the empty set, it could be a singleton, it could be a larger finite set, it could be an infinite set. For example, we can define a family of sets indexed by the natural numbers (including zero): for every $n \in \mathbb{N}$, $S_n = \{n,-n\}$. The union of this family consists of all integers: $\bigcup_{n \in S_n} S_n = \mathbb{Z}$,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy