The first stars in the Universe are predicted to have been much more massive
than the Sun. Gravitational condensation accompanied by cooling of the
primordial gas due to molecular hydrogen, yields a minimum fragmentation scale
of a few hundred solar masses. Numerical simulations indicate that once a gas
clump acquires this mass, it undergoes a slow, quasi-hydrostatic contraction
without further fragmentation. Here we show that as soon as the primordial gas
- left over from the Big Bang - is enriched by supernovae to a carbon or oxygen
abundance as small as ~0.01-0.1% of that found in the Sun, cooling by
singly-ionized carbon or neutral oxygen can lead to the formation of low-mass
stars. This mechanism naturally accommodates the discovery of solar mass stars
with unusually low (10^{-5.3} of the solar value) iron abundance but with a
high (10^{-1.3} solar) carbon abundance. The minimum stellar mass at early
epochs is partially regulated by the temperature of the cosmic microwave
background. The derived critical abundances can be used to identify those
metal-poor stars in our Milky Way galaxy with elemental patterns imprinted by
the first supernovae.