Starting from the Bonn potential, relativistic Brueckner-Hartree-Fock (RBHF) equations are solved for nuclear matter in the full Dirac space, which provides a unique way to determine the single-particle potentials and avoids the approximations applied in the RBHF calculations in the Dirac space with positive-energy states (PESs) only. The uncertainties of the RBHF calculations in the Dirac space with PESs only are investigated, and the importance of the RBHF calculations in the full Dirac space is demonstrated. In the RBHF calculations in the full Dirac space, the empirical saturation properties of symmetric nuclear matter are reproduced, and the obtained equation of state agrees with the results based on the relativistic Greens function approach up to the saturation density.