Table in a mathematical paper

I suggest you simplify the table structure as follows:

• Provide only four columns: The left-most one should be headed by $\mathcal{P}\backslash e$, and columns 2 to 4 should be headed by $\mathcal{P}/e$.
• Don't use a tabular but, instead, a tabularx environment, and make use of the X column type provided by this package. The X column type allows text to wrap. Put differently, don't use c as the column alignment specifier.
• Don't use full (left and right) justification; use left-justification instead.
• You're probably going to do this anyway, but I'll still suggest you provide a \caption for the table environment.

\documentclass[12pt,oneside]{amsart}
\usepackage{tabularx,ragged2e}
\newcolumntype{Y}{>{\RaggedRight}X} % left-justified version of X column type
\begin{document}
\section{Test code}

Together with the inductive result of Lemma \ref{induction} this implies in all cases that $\mathcal{P}$ is one of optimal, unbounded, or feasible:
\begin{table}[htbp]
\begin{tabularx}{\textwidth}{|X|*{3}{Y|}}
\hline
$\mathcal{P}\backslash e$ 
&\multicolumn{3}{c|}{$\mathcal{P}/e$}\\
\cline{2-4}
& optimal  &unbounded & infeasible \\ 
\hline
optimal 
& optimal Lemma \ref{induction} i) 
& (not possible)
& optimal or infeasible Lemma \ref{induction} ii)   \\ 
\hline
unbounded
& unbounded or optimal Lemma \ref{induction} iii) 
& unbounded
& unbounded or infeasible Lemma \ref{induction} iv) \\ 
\hline
infeasible 
& (not possible)                                  
& (not possible)
& infeasible \\ 
\hline
\end{tabularx}
\end{table}
\end{document}

---

Addendum: I'll make one more suggestion related to the overall design of the table: Don't use any vertical lines at all, and use the booktabs package and its commands for drawing well-spaced horizontal lines ("rules"):

\documentclass[12pt,oneside]{amsart}
\usepackage{tabularx,ragged2e,booktabs}
\newcolumntype{Y}{>{\RaggedRight}X} % left-justified version of X column type
\begin{document}
\section{Test code}

Together with the inductive result of Lemma \ref{induction} this implies in all cases that $\mathcal{P}$ is one of optimal, unbounded, or feasible:
\begin{table}[htbp]
\begin{tabularx}{\textwidth}{@{}X*{3}{Y}@{}}
\toprule
$\mathcal{P}\backslash e$ 
&\multicolumn{3}{c}{$\mathcal{P}/e$}\\
\cmidrule(l){2-4}
& optimal  &unbounded & infeasible \\
\midrule
optimal 
& optimal Lemma \ref{induction} i) 
& (not possible)
& optimal or infeasible Lemma \ref{induction} ii)   \\[1ex]
unbounded
& unbounded or optimal Lemma \ref{induction} iii) 
& unbounded
& unbounded or infeasible Lemma \ref{induction} iv) \\[1ex]
infeasible 
& (not possible)                                  
& (not possible)
& infeasible \\ 
\bottomrule
\end{tabularx}
\end{table}
\end{document}

---

Second addendum: The OP has asked for a version of the table that features $\mathcal{P}\backslash e$ by itself in a new column at the far-left. Here's an attempt to make this work.

\documentclass[12pt,oneside]{amsart}
\usepackage{tabularx,ragged2e}
\newcolumntype{Y}{>{\RaggedRight}X} % left-justified version of X column type
\begin{document}
\section{Test code}

Together with the inductive result of Lemma \ref{induction} this implies in all cases that $\mathcal{P}$ is one of optimal, unbounded, or feasible:
\begin{table}[htbp]
\begin{tabularx}{\textwidth}{|l|l|*{3}{Y|}}
\hline 
& &\multicolumn{3}{c|}{$\mathcal{P}/e$}\\
\cline{3-5}
& & optimal  &unbounded & infeasible \\ 
\hline
& optimal 
& optimal Lemma \ref{induction} i) 
& (not possible)
& optimal or infeasible Lemma \ref{induction} ii)   \\ 
\cline{2-5}
$\mathcal{P}\backslash e$
& unbounded
& unbounded or optimal Lemma \ref{induction} iii) 
& unbounded
& unbounded or infeasible Lemma \ref{induction} iv) \\ 
\cline{2-5}
& infeasible 
& (not possible)                                  
& (not possible)
& infeasible \\ 
\hline
\end{tabularx}
\end{table}
\end{document}

\documentclass{article}
\usepackage{tabularx}
\usepackage{array}
\usepackage[showframe]{geometry}

\begin{document}
\noindent
\begin{tabularx}{\textwidth}{|cc|XcccX|}
\hline
A & B & CCC CCC CCC CCC CCC CCC & D & E & F & HHH HHH \\
A & B & CCC CCC CCC CCC CCC CCC & D & E & F & HHH HHH \\
\hline
\end{tabularx}
\end{document}