  We study the rest-frame ultra-violet sizes of massive (~0.8 x 10^11 M_Sun)
galaxies at 3.4<z<4.2, selected from the FourStar Galaxy Evolution Survey
(ZFOURGE), by fitting single Sersic profiles to HST/WFC3/F160W images from the
Cosmic Assembly Near-Infrared Deep Extragalactic Legacy Survey (CANDELS).
Massive quiescent galaxies are very compact, with a median circularized
half-light radius r_e = 0.63 +/- 0.18 kpc. Removing 5/16 (31%) sources with
signs of AGN activity does not change the result. Star-forming galaxies have
r_e = 2.0 +/- 0.60 kpc, 3.2 +/- 1.3 x larger than quiescent galaxies. Quiescent
galaxies at z~4 are on average 6.0 +\- 0.17 x smaller than at z~0 and 1.9 +/-
0.7 x smaller than at z~2. Star-forming galaxies of the same stellar mass are
2.4 +/- 0.7 x smaller than at z~0. Overall, the size evolution at 0<z<4 is well
described by a powerlaw, with r_e = 5.08 +/- 0.28 (1+z)^(-1.44+/-0.08) kpc for
quiescent and r_e = 6.02 +/- 0.28 (1+z)^(-0.72+/-0.05) kpc for star-forming
galaxies. Compact star-forming galaxies are rare in our sample: we find only
1/14 (7%) with r_e / (M / 10^11 M_Sun)^0.75 < 1.5, whereas 13/16 (81%) of the
quiescent galaxies is compact. The number density of compact quiescent galaxies
at z~4 is 1.8 +/- 0.8 x 10^-5 Mpc^-3 and increases rapidly, by >5 x, between
2<z<4. The paucity of compact star-forming galaxies at z~4 and their large
rest-frame ultra-violet median sizes suggest that the formation phase of
compact cores is very short and/or highly dust obscured.
