Is there a category that mathematical statements as objects and implications of statements as arrows? For example, one object would be $x^2 + 1 = 0$, and it would have an arrow to $x^2=-1$, which would have an arrow to $x = i$. What are these categories called and what all do you have to define to specify a specific one of these categories?
 A: This is captured by the Lindenbaum algebra: if we have a theory $T$ in some language, let $\approx_T$ be the relation on formulas in that language given by $\varphi(x_1, ..., x_n)\approx_T \psi(x_1, . . . , x_n)$ iff $T$ proves "For all $x_1, . . . , x_n$, $\varphi(x_1, ..., x_n)\iff\psi(x_1, ..., x_n)$."
The set of equivalence classes under this relation forms a Boolean algebra; $T$ proves that $\alpha$ implies $\beta$ if $\overline{[\alpha]}\cup[\beta]=1$ in the Boolean algebra, where "$[\alpha]$" denotes the $\approx_T$-class of $\alpha$. So implication is captured in this structure. (Incidentally, the Lindenbaum algebra can be augmented with additional structure - see also cylindrical algebras, and algebraic logic more generally.)
If you prefer categories, it can be turned into a category whose objects are the equivalence classes $[\alpha]$, and with a unique arrow from $[\alpha]$ to $[\beta]$ iff $\overline{[\alpha]}\cup[\beta]=1$.

Note that this approach doesn't distinguish between ways in which one formula implies another. A much more interesting structure would potentially have many arrows from $[\alpha]$ to $[\beta]$, corresponding to different proofs of implication. But this rapidly gets into more complicated territory, so I'll stop here for now.
A: The categorical generalization Noah Schweber alludes to is the notion of a syntactic category which in general will not be a preorder category.  The general area is categorical logic/type theory with the primary notion of an internal logic of a category (or more generally, internal language).  The syntactic category is a way of taking a logic and producing a category whose internal logic is that logic.  From this perspective, we are usually more interested in constructive logics as opposed to classical (i.e. Boolean) logics as the internal logic of most categories is not Boolean.
For the simplest case though, you can do a bit of a short-cut.  Usually we have a notion of entailment written $\Gamma \vdash P$ meaning $P$ is entailed by the context $\Gamma$ where a context is just a list of propositions.  So entailment is just a binary relation relating contexts to propositions. We can lift this to a binary relation on contexts by defining $\Gamma \vdash \Delta \iff (\Gamma \vdash \Delta') \land (\Gamma \vdash P)$ where $\Delta = \Delta', P$. That is, $\Gamma \vdash \Delta$ if each proposition in the context $\Delta$ is entailed by $\Gamma$. For most logics we have $P \vdash P$ as an admissible (if not given) rule which lifts to $\Gamma \vdash \Gamma$, and we have cut as an admissible (if not given) rule $\frac{\Gamma\ \vdash\ P\quad\Delta,P\ \vdash\ Q}{\Gamma,\Delta\ \vdash\ Q}$ from which we can derive $\frac{\Gamma\ \vdash\ \Delta\quad\Delta\ \vdash\ \Xi}{\Gamma\ \vdash\ \Xi}$. In other words, entailment lifted to contexts is a reflexive, transitive relation, and thus we can make a preorder category out of it.
