I am trying to solve the following question:
Decide if a relation can be proven between $\text{NSPACE}(n\log n)$ and $\text{DSPACE}(n)$. That is, whether $A \subseteq B$, $B \supseteq A$, $A \setminus B = \emptyset$; and $B \setminus A = \emptyset$. Some relations may not be known.
Firstly, I don't understand the difference between the two sets of relations, as in aren't $A \subseteq B$ and $A\setminus B = \emptyset$ the same thing? And same for the other two?
Secondly, I know that $\text{DSPACE}(n) \subseteq \text{NSPACE}(n)$, however given that we have $\text{NSPACE}(n \log n)$, can someone show me how to go about it?
If $L \in \text{DSPACE}(n)$, then there exists a deterministic Turing machine $M$ that decides $L$ using at most $O(n)$ tape cells on any input of length $n$. If $L \in \text{NSPACE}(n \log n)$, then there exists a nondeterministic Turing machine $M$ that decides $L$ using at most $O(n \log n)$ tape cells in any nondeterministic computation on any input of length $n$.
We know for any function $f : \mathbb{N} \rightarrow \mathbb{N}$ that if $f = O(n)$, then also $f = O(n \log n)$. Moreover, a deterministic Turing machine is also a very boring nondeterministic Turing machine. So we have $L \in \text{NSPACE}(n \log n)$.
To see that the inclusion is strict, apply the space hierarchy theorem to $\text{DSPACE}(n)$ and $\text{DSPACE}(n \log n)$.