Matrosov's relaxation of Lyapunov conditions for uniform global asymptotic stability in time-varying systems is extended to stochastic, set-valued discrete-time systems. Nested Matrosov functions are used to give conditions for stability that complement invariance principles for time-invariant systems. Unlike invariance principles, Matrosov functions also can be applied to general time-varying systems.