Problem: 
Along with $\in, \notin$; logical connectives like $ \land , \lor, \lnot$; and quantifiers $\forall , \exists$ we can also use $x = y$ and $x \subseteq y$, where
\begin{align*}
x = y &::= \forall z(z\in x \leftrightarrow z\in y), \\
x \neq y&::= \neg(x = y) ,\\
x \subseteq y &::= \forall z( z\in x \to z\in y), \\
x \nsubseteq y &::= \neg(x \subseteq y).
\end{align*}
This problem is from the Discrete Mathematics course notes of MIT OCW. Link
I have come up with a solution for the first part:
- $\mathrm{Subset}_n(x, y_1,…,y_n) ::=\exists y_1,y_2,…,y_n\left(
\begin{array}{l}
\forall i,j(i \neq j \to y_i \neq y_j)~\wedge \\
\forall z(z\in x \to z \in \{y_1,…,y_n\})
\end{array}
\right).
$
I am having trouble with deriving formulas for the rest of the parts.
Best Answer
The problem with your attempt at $\mathrm{Subset}_n$ is that the first-order language of set theory doesn't allow you to quantify over variables indices, so when you write $$ \forall i,j(\cdots y_i \cdots y_j \cdots) $$ you don't end up with a well-formed formula. Each of the variables $y_1$, $y_2$ and so forth is a completely different variable, and first-order logic doesn't know they have anything to do with each other. You know their numbering while you're putting the formula together, but your goal is to construct a formula whose meaning does not depend on knowing it.
You also can't write $z\in\{y_1,\ldots,y_n\}$, because set brackets are not actually among the symbols of the formal language of set theory! They're abbreviations for more complex formulas (though in a more complex way that $x\subseteq y$ is an abbreviation). But the exercise states which such abbreviations you're allowed to use, and $\{\ldots\}$ is not one of them.
A better solution would be one that produces, say, $$ \mathrm{Subset}_4(x,a,b,c,d) ::= \forall z(z\in x \to z=a \lor z=b \lor z=c \lor z=d) $$ Note that there are no indices on the variables here. I can do that because I'm only writing the formula for $n=4$. When you describe how to construct a formula for a general $n$ you will need some indices and dots or other repetition constructs at the metalevel, but these are only for describing how to make a formula like the above. The number $n$ does not exist at the set-theory level; you will end up with a different formula for each $n$ -- even though these different formulas are constructed according to a common recipe).
The exercise is a bit confusingly worded because in parts 1, 2, 3 it only says "Write a formula $A_n$", whereas in part 4 it becomes "Describe how to write a formula $D_n$". Actually each part is a "describe how to write a formula", because in every part each value of $n$ needs its own formula, and your task requires you to describe all of those formulas in a generic way.
A different problem with your $\mathrm{Subset}_n$ is that it looks like you've made a specific effort to make the formula require the $y_i$s to be distinct. This is not what the exercise asks for, though. For example, if $x$ is the set $\{1,2\}$, then $$ \mathrm{Subset}_4(x,1,2,3,3) $$ must be true because it is the case that $\{1,2\}\subseteq\{1,2,3,3\}$.
Perhaps you've gotten the impression that $\{1,2,3,3\}$ is "forbidden", such that it's your task to enforce that rule? That's not true -- it's perfectly allowed in set theory to write $\{1,2,3,3\}$, it's just another way to notate the set that's usually called $\{1,2,3\}$.
It's a bit silly to write $\{1,2,3,3\}$ explicitly, of course -- and for this reason you may have found yourself marked down by teachers if you've done it. But that's just because doing so suggests you've misunderstood how set works and that it's actually the same set as $\{1,2,3\}$.
However if you have a good reason to mention a value twice between the curly brackets -- for example because you have two variables and don't yet know if their values will be the same -- then it's perfectly okay to do so.
(Formally, $\{1,2,3,3\}$ means the (unique) set $x$ such that $$ \forall z(z\in x \leftrightarrow z=1 \lor z=2 \lor z=3 \lor z=3) $$ Such a set of course does exist, and it's the same set as $\{1,2,3\}$).
As for your lack of ideas for the other parts, here are some attempts at hints that don't give everything away:
Do you agree that $x$ has at most 17 elements if there is some set of 17 elements that $x$ is a subset of?
A set that has exactly 17 elements has at most 17 elements -- but it doesn't have at most 16 elements.
If $a, b, c, d$ are not all distinct, there is a set that contains all of them yet has at most 3 elements. (This is probably not the hint envisaged in the exercise, though, since it wouldn't even use $\mathrm{Exactly}$).