\begin{align}(x,y)\in (A\setminus B)\times(C\setminus D)&\iff x\in (A\setminus B)\wedge y\in(C\setminus D)\\&\iff x\in A\wedge x\notin B \wedge y\in C\wedge y\notin D\\&\iff(x,y)\in(A\times C)\wedge (x,y)\notin(B\times C)\wedge (x,y)\notin (A\times D)\\&\iff (x,y)\in (A\times C) \setminus [(A\times D)\cup (B\times C)] \end{align}
Let me preface this by saying that I am an analyst, and not an expert in set theory or mathematical foundations. The answer that I am about to give is based on an undergraduate class that I took maybe a decade ago, so if anyone with an actual background in foundational set theory wants to correct my errors, I am more than happy to defer to them.
That being said, my feeling about the construction is as follows: the axioms of $\mathsf{ZFC}$ (or any other axiom system) tell us how objects should behave, but it is not obvious that those axioms actually provide enough structure to model the objects that we are interested in. In particular, it is not immediately obvious that $\textsf{ZFC}$ is sufficient to model our intuition about counting. Hence the set theoretic construction of the natural numbers is meant to give a model within the axiom system. Once we know that such a model exists, we can largely get on with our lives.
Depending on precisely how the axioms are stating, $\textsf{ZFC}$ doesn't give us many sets to work with. Indeed, the only set that is required in order to start building things up is the empty set–existence of the empty set can either be taken as an axiom, or follows from the Axiom of Schema Specification. From the empty set, we want to be able to build up the natural numbers.
To do this, we need a starting place (zero), and a way of getting from one set to another (a successor operation). The usual way to do this is as you described, i.e. we define
$$ 0 := \varnothing \qquad\text{and}\qquad s(n) := n \cup \{n\}.$$
The definition of zero is, I think, relatively easily understood. The successor operation is a little more opaque. The essential idea is that, given a natural number $n$, we want some kind of set theoretic construction which gives the "next" natural number $s(n)$. To do this, we have to construct a new set out of whole cloth which is distinct from all of the other sets thus far constructed. The way we choose to do this is to consider a set which contains two elements: the set $n$ itself, and the set $\{n\}$, which is a set containing only one element.
The two sets
$$ 0 = \varnothing \qquad\text{and}\qquad
1 = \{\varnothing\} $$
look like a whole lot of nothing, but they are actually quite distinct. The set containing the empty set–$\{\varnothing\}$–is an element of 1, but not an element of 0. Perhaps part of the problem here is the distinction between the ideas of "subset" and "is an element of." The empty set is a subset of any set. Hence
$$ \varnothing \subseteq 0. $$
On the other hand, the empty set is not an element of 0. That is,
$$ \varnothing \not\in \varnothing,
\qquad\text{though}\qquad
\varnothing \in \{\varnothing\} = 1. $$
The construction of the natural numbers depends on understanding how this nesting works, and noting that a set with no elements is distinct from the set which contains a set which has no elements. Think of $\varnothing$ as an empty grocery bag, and $\{\varnothing\}$ as a grocery bag containing an empty grocery bag. These are two different objects: the bag with a bag in it isn't empty!
In general two sets $n$ and $n \cup \{n\}$ are distinct: we will always have $n \in s(n)$, but $n\notin n$. This also has the advantage of giving us an ordering that matches our intuition:
$$ m \le n \iff m \subseteq n \iff m \in n. $$
For example (abbreviating notation so that we don't have to write a whole bunch of empty sets over and over again),
$$ 3 = 2 \cup \{ 2 \} = (1 \cup \{ 1 \} ) \cup \{2\} = ((0 \cup \{0\}) \cup \{1\}) \cup \{2\} = \{ 0, 1, 2 \}. $$
Note that $2 \in 3$, and also that $2 = \{0,1\} \subseteq 3$. The advantage of this scheme is that the cardinality of the set $n$ is equal to the number of elements contained in $n$, where "cardinality" has a rigorous mathematical definition, and "the number of elements contained in" matches our intuitive notion.
Best Answer
If $A = \{apples, oranges, bananas\}$ and $B= \{3,7,9\}$ then $A\cup B = \{apples, oranges, bananas,3,7,9\}$.
There is no restriction that if $A$ is a set of fruit that the only things you can do with it is in the realm of fruit nor that if $B$ is in the realm of numbers that the only things we can do with it are in the realms of numbers.
$A = \{4,5,6,7\}$ in the realm of single numbers.
And $B\times C =\{(6,4),(6,7),(6,9),(8,4),(8,7),(8,9)\}$ in the real of ordered pairs
And so $A \cup (B\times C) =\{4,5,6,7,(6,4),(6,7),(6,9),(8,4),(8,7),(8,9)\}$ which is not restricted to either the ream of number nor the realm of ordered pairs.
.....
As for relations. Note: one relation is subset of $A\times B$. A relation is not an element of $A\times B$.
Example if $A = \mathbb N$ and $B=\mathbb N$ and the relation is "the first number divides the second" then "the first number divides the second" $\ne (a,b)$ for any one pair $(a,b)$.
Instead "the first number divides the second" $= \{(1,2),(5,15), (7,35),,.......\}$ which is a whole subset of ordered pairs.
So if $C= \{1,5\}$ and $D=\{2,3,5\}$
Then what are the possible relations.
First is: $\emptyset$. That is no number is related to any other.
The second is $\{(1,2)\}$. That is $1$ is related to $2$ but nothing else are.
Another is $\{(1,2),(1,5), (5,3),(5,2)\}$. Which is a arbitrary $1$ is relateed to $2$ and $5$ and $5$ is related to $3$ and $2$. Why? Who cares?
The last is $\{(1,2),(1,3),(1,5),(5,2),(5,3),(5,5)\} = C\times D$. Everything is related to everything!
So how many total relations are there?
Well every subset of $C\times D$ can be a relation. so if $\mathscr P(C\times D)=\{$ the subsets of $C\times D\}$ then the number of relations is $|\mathscr P(C\times D)|$.
Which is a different concept then $|C\times D|$.
....
So you figure that if $|A| = k$ and $|B| =3$ then $|A\times B| = 3k$. That's fine.
But $4096 = |\mathscr P(A\times B)|$.
So you need to figure out if $|A\times B| = 3k$ then what does $|\mathscr P(A\times B)| = f(3k)$ is.
Can you?
Hint: If I eyeball factor $4096$ I get that $4|4096$ so $4096 = 4*1024$ and if I eyeball factor $1024$ I see it is divisible by $2$ so $4096 = 8*512$ and if I eyeball factor I get .... hey, wait a minute!