Consider the decision problem where three decisions are valid: $0, 1$ and a third option $reject$. An optimal rule has the lowest probability of error at a fixed "reject" probability. More formally, given a context $X \in \mathcal{X}$ and a target $Y \in \{0, 1\}$, a decision rule $g: \mathcal{X} \rightarrow \{0, 1, reject\}$ is optimal if for any decision rule $g'$ with $\mathbb{P}(g'(X) = reject) \leq \mathbb{P}(g(X) = reject)$ we have that the error probability of $g'$ is at least as large as that of $g$:
$$\mathbb{P}(g'(X) \neq Y | g'(X) \neq reject) \geq \mathbb{P}(g(X) \neq Y | g(X) \neq reject)$$
Show that the following decision function is optimal for $c \in (0, 1/2)$:
$$ g_c(X) = \begin{cases} 1, & \eta(X) > 1/2 + c \\ 0, & \eta(X) \leq 1/2 - c \\ reject, & \text{otherwise} \end{cases} $$
where $\eta(x) = \mathbb{P}(Y = 1 | X=x)$.
What I've tried
I've tried showing this in the same way as showing that $\eta(x)$ is the Bayes optimal predictor in the case without the rejection option:
Using the identity: $$ \mathbb{P}(g(X) \neq Y | X = x) = 1- (\mathbb{I}(g(X) = 1)\eta(x) + \mathbb{I}(g(X) = 0)(1-\eta(x))) $$
We then have:
$$ \begin{align} &\mathbb{P}(g(X) \neq Y | X = x) - \mathbb{P}(g_c(X) \neq Y | X = x)\\ & = (\mathbb{I}[g_c(X) = 1]\eta(x) + \mathbb{I}[g_c(X) = 0](1-\eta(x))) -(\mathbb{I}[g(X) = 1]\eta(x) + \mathbb{I}[g(X) = 0](1-\eta(x))) \\ &= (\eta(x)(\mathbb{I}[g_c(X) = 1] - \mathbb{I}[g(X) = 1)] + (1-\eta(x))(\mathbb{I}[g_c(X) = 0] - \mathbb{I}[g(X) = 0])) \\ &= (2\eta(x) -1)(\mathbb{I}[g_c(X) = 1] - \mathbb{I}[g(X) = 1]) + (1-\eta(x))(\mathbb{I}[g_c(X) = reject] - \mathbb{I}[g(X) = reject]) \end{align} $$ The last equality follows from considering the complement of the events in the indicators in the second term.
In the case of the Bayes optimal rule, the first term is always nonnegative. In our case this isn't clear to me since the decision boundary is no longer $1/2$. We also have an extra term involving the rejection probability.
I have tried a few other manipulations but I think there is a simpler way that I am missing.
Without the rejection option, for any given $X \in \mathcal{X}$ we want to choose $g(X)$ to minimize your identity:
$$\mathbb{P}(g(X) \neq Y | X ) = 1- (\mathbb{I}(g(X) = 1)\eta(X) + \mathbb{I}(g(X) = 0)(1-\eta(X)))$$
Well, there are two options:
Thus, the probability of rejection:
$$\mathbb{P}(g(X) \neq Y) = \sum_{X \in \mathcal{X}} \mathbb{P}(g(X) \neq Y | X)\mathbb{P}(X)$$
is minimized by letting $g(X) = \mathbb{I}(\eta(X) > 1/2)$, and evaluates to:
$$\mathbb{P}(g(X) \neq Y) = \sum_{X \in \mathcal{X}} \big(1/2 -|1/2 - \eta(X)|\big) \, \mathbb{P}(X)$$
Thus, when $c=0$, the optimal decision rule is your $g_0$.
With the rejection option, any optimal $g$ still has the property that $g(X) = \mathbb{I}(\eta(X) > 1/2)$ if $g(X) \neq reject$.
Deciding when to reject then becomes identical to the discrete case of the Neyman Pearson Lemma. There are two options for each $X \in \mathcal{X}$, either reject and add $\mathbb{P}(X)$ the probability of rejecting, or do not reject and add $\big(1/2 -|1/2 - \eta(X)|\big) \, \mathbb{P}(X)$ to the error probability. (We can interpret their ratio as the likelihood ratio.) This lemma implies that any cutoff rule rejecting $X$ for sufficiently large values of $\big(1/2 -|1/2 - \eta(X)|\big)$ is optimal, which is what $g_{c}$ is.
This is very intuitive and why you chose $g_c$ correctly: we want to reject $X$ when it is close to $1/2$.