Abstract: Three shortcomings and two errors of Zadeh's fuzzy set theory were analyzed and proved, and a new fuzzy set theory, C^*-fuzzy set theory, was proposed. The new C^*-fuzzy set considers the relationship between fuzzy sets and represents the relationship with relativity. It overcomes all the errors and shortcomings of Zadeh's fuzzy set theory:it correctly reflects different kinds of fuzzy phenomena in the natural world; set complement exists on it; it has uniform calculating formulas for membership; it satisfies all formulas of the classical set theory and is consistent with classical and normal thinking, logic and concepts.