What went wrong?

The rule for even is not monotone in odd (and vice versa):

input odd	output even
{}	{0, 1, 2, 3, 4, 5}
{0, 1, 2, 3, 4, 5}	{}

In general, if each use of p in a rule is positive (i.e., not negated), the rule is monotone in p.

So if all recursive calls in a program are positive, the program is monotone.