Implications of Theorem 3

This theorem is very important. Let L and $\bar{L}$ be complementary languages. Then one of three cases is true:

1.

both L and $\bar{L}$ are recursive,

2.

neither L nor $\bar{L}$ is r.e, or

3.

at most one of L and $\bar{L}$ is r.e, the other is not r.e.

.