Why $\mathbb Z/2\mathbb Z$ is not definable in $(\mathbb Z, +, 0)$? Marker states in his textbook:

It is possible that $G/H$ does not
  correspond to a definable group in our structure.

Our instructor gave $\mathbb Z/2\mathbb Z$ as an example. But definability, again by Marker, is 

We say that $X \subseteq M^n$ is definable if and only if there is an L-formula $\phi(v_1,... , v_n, w_1, ..., w_m)$ and $b\in M^m$ such that $X = \{a ∈ M^n : M |= φ(a, b)\}$.

So, why can't we choose arbitrary elements $u,v\in\mathbb  Z$ to represent $0,1 \in\mathbb Z/2\mathbb Z$ and use them as $b$ in the definition above?
Addition in $\mathbb Z/2\mathbb Z$, viewed as a relation, is defined for the following triples: $(0,0,0), (0,1,1), (1,0,1), (1,1,0)$. Let's build a formula $\phi(x,y,s, u,v): (x=u \land y=u \land s=u) \lor (...)\lor (...)\lor (...)$. Resulting relation will be a subset of $\mathbb Z^3$ and will define addition from $\mathbb Z/2\mathbb Z$.
Where am i wrong?
 A: You're right. More precisely, a definable group in a structure $M$ is given by:


*

*A definable set $X\subseteq M^n$ for some $n$.

*A definable function $\cdot\colon X^2\to X$.

*A definable element $e\in X$.

*A definable function $^{-1}\colon X\to X$.

*Such that the group axioms are satisfied.


Of course, specifying $e$ and $^{-1}$ are optional, since if $X$ is actually a definable group, then they can be defined from $\cdot$. In all of the above, definable usually means definable with parameters. 
A consequence of this definition is that any finite group is definable in any infinite structure $M$. Just pick elements $a_1,\dots,a_n\in M$, let $X$ be defined by $\bigvee_{i=1}^n (x = a_n)$, and define $\cdot$ by explicitly writing out the multiplication table of the group, as you did in your example. 
It's possible that your instructor was thinking about the concept of definable subgroup. When your structure $(M,\cdot)$ is itself a group (possibly with additional extra structure), then a definable subgroup is a definable set $X\subseteq M$ such that $(X,\cdot)$ is a subgroup of $(M,\cdot)$. Note that the group operation here is the same, you don't get to define it in some other way. Then indeed $\mathbb{Z}/2\mathbb{Z}$ is not (isomorphic to) a definable subgroup of $\mathbb{Z}$. But this is somewhat trivial, because definability isn't relevant here: $\mathbb{Z}$ has no subgroup, definable or otherwise, isomorphic to $\mathbb{Z}/2\mathbb{Z}$.  
