A word for a relationship in which one thing (or state) must exist in order for another thing (or state) to exist

A prerequisite is something that must exist for another to exist.

Perhaps, contingency/contingent? Maybe this definition for contingency:

a future event or circumstance that is possible but cannot be predicted with certainty

and this one for contingent:

occurring or existing only if (certain other circumstances) are the case; dependent on

EDIT: I just thought of this one after I had posted, but it could also be conditional.

subject to one or more conditions or requirements being met; made or granted on certain terms

Given the statement "Logically, A can't exist or occur without B", then to describe A 's relationship to B, you'd say "A is a prerequisite of B" (as @JasperLoy answered).

By contrast, if you wanted to describe B 's relationship to A, you'd say "B is predicated on A" (which sounds a lot like your "predecession" to me).