I agree, this seems like a reasonable way of defining dependencies between constant symbols. In case of logical uncertainty, I think you'd want to look into how relative lengths of proofs depend on adding more theorems as axioms (so that they don't cost any proof length to use). This way, different agents or an agent in different situations would have different ideas about which dependencies are natural.

This goes all the way back to trying to define dependencies by analogy with AIXI/K-complexity, I think we were talking about this on the list in spring 2011.