Understanding lemma found in proof of quotient construction for DFAs

Question

Lemma 13.6    $p \in F \Longleftrightarrow [p] \in F'$

Proof. The direction $\Rightarrow$ is immediate from the definition of $F'$. For the direction $\Leftarrow$, we need to show that if $p \approx q$ and $p \in F$, then $q \in F$. In other words, every $\approx$-equivalence class is either a subset of $F$ or disjoint from $F$. This follows immediately by taking $x = \epsilon$ in the definition of $p \approx q$. $\quad\square$

The excerpt above found in Dexter C. Kozen's Automata and Computability. This lemma is found in a proof of the Quotient Construction for DFA.

I do not understand how the author concludes that if one wants to show $[p] \in F' \implies p \in F$ (1), then it is equivalent to showing that $p≈q$ and $p \in F \implies q \in F$ (2). Can someone please provide as detailed as possible an explanation of why if we want to show (1) it is equivalent to show (2)? Any idea on why the author does not feel the need to justify this?

Answer 1

Let us start with explaining the notation:

• $F$ is the set of accepting states of some DFA.
• We define an equivalence relation $\approx$ on the states of the DFA as follows: $p \approx q$ if for all words $x$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x)$, where $\hat\delta$ is the transition function of the DFA (extended from symbols to words).
• We denote the equivalence class of a state $p$ by $[p]$.
• $F' = \{ [p] : p \in F \}$.

Now suppose that $[p] \in F'$. According to the definition of $F'$, $[p] = [q]$ for some $q \in F$. Standard properties of equivalence relations imply that $[p] = [q]$ iff $p \approx q$. By definition of $\approx$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x) \in F$ for all words $x$. Taking $x = \epsilon$, we see that $p = \hat\delta(p,\epsilon) \in F$ iff $q = \hat\delta(q,\epsilon) \in F$. Since $q \in F$, this shows that indeed $p \in F$.