Mathematics for Computer Science

Chapter 5 Infinite Sets100

5.4.2 The ZFC Axioms for Sets

It’s generally agreed that, using some simple logical deduction rules, essentially all
of mathematics can be derived from some axioms about sets called the Axioms of
Zermelo-Frankel Set Theory with Choice (ZFC).
We’renotgoing to be studying these axioms in this text, but we thought you
might like to see them –and while you’re at it, get some practice reading quantified
formulas:

Extensionality.Two sets are equal if they have the same members. In a logic
formula of set theory, this would be stated as:

. 8 z: z 2 xIFFz 2 y/IMPLIESxDy:

Pairing.For any two setsxandy, there is a set,fx;yg, withxandyas its only
elements:
8 x;y: 9 u: 8 z: Œz 2 uIFF.zDxORzDy/ç

Union. The union,u, of a collection,z, of sets is also a set:

8 z: 9 u; 8 x:. 9 y: x 2 yANDy 2 z/IFFx 2 u:

Infinity.There is an infinite set. Specifically, there is a nonempty set,x, such that
for any sety 2 x, the setfygis also a member ofx.

Subset.Given any set,x, and any definable propery of sets, there is a set containing
precisely those elementsy 2 xthat have the property.

8 x: 9 z: 8 y:y 2 zIFFŒy 2 xAND.y/ç

where.y/is any assertion aboutydefinable in the notation of set theory.

Power Set. All the subsets of a set form another set:

8 x: 9 p: 8 u: uxIFFu 2 p:

Replacement. Suppose a formula,, of set theory defines the graph of a function,
that is,
8 x;y;z:Œ.x;y/AND.x;z/çIMPLIESyDz:
Then the image of any set,s, under that function is also a set,t. Namely,

8 s 9 t 8 y:Œ 9 x:.x;y/IFFy 2 tç: