  We develop a toolbox for forcing over arbitrary models of set theory without
the axiom of choice. In particular, we introduce a variant of the countable
chain condition and prove an iteration theorem that applies to many classical
forcings such as Cohen forcing and random algebras. Our approach sidesteps the
problem that forcing with the countable chain condition can collapse $\omega_1$
by a recent result of Karagila and Schweber. Using this, we show that adding
many Cohen reals and random reals leads to different theories. This result is
due to Woodin. Thus one can always change the theory of the universe by
forcing, just like the continuum hypothesis and its negation can be obtained by
forcing over arbitrary models with choice. We further study principles
stipulating that the first-order theory of the universe remains the same in all
generic extension by a fixed class of forcings. Extending a result of Woodin,
we show that even for very restricted classes such as the class of all finite
support products of Cohen forcing or the class of all random algebras, this
principle implies that all infinite cardinals have countable cofinality.
