Motivation
Much mathematics begins with the instruction “let the set of all objects having a certain property be ”. That instruction hides an existence claim. The property might describe a subset of an already available set, or it might range over everything in the universe. Those are different operations. Axiomatic set theory makes the distinction explicit so that ordinary constructions can be justified without admitting contradictory collections.
Suppose every formula determined a set . Taking to mean would give a set with if and only if . No consistent theory can permit that construction. The repair is not to forbid descriptions containing negation: the complement of a subset inside a fixed set is perfectly legitimate. The repair is to control the domain on which a description forms a set.
We work in the classical first-order language of membership, with equality and the relation . Every variable denotes a set. Expressions such as “the class of all ordinals” are useful descriptions, but classes are not additional objects of ZF. A definable class means the collection described by a formula, with parameters allowed. It can be discussed without assuming it is a set.
Definitions
The axiom of extensionality says that sets with exactly the same members are equal:
The empty-set, pairing, union, power-set and infinity axioms supply an empty set, a set for any two sets, a union , a power set , and an inductive set. An inductive set contains and contains whenever it contains . Extensionality gives uniqueness where the displayed specification determines all members.
Definition 1.1.1
(Separation schema)
Separation is an axiom schema: for each formula , and each set , there is a set
The new set variable must not occur freely in the defining formula. Parameters are allowed. A schema is a family of first-order axioms, one for every formula, rather than one axiom quantifying over formulas inside the language.
Definition 1.1.2
(Replacement schema)
Replacement is another schema. If a formula specifies exactly one for every , then the values form a set:
The formula need not be represented by a previously existing function set. This matters when the possible values have no available common set bound. Separation selects members from a known set; replacement collects uniquely specified values indexed by a known set.
Foundation says that every nonempty set contains a member disjoint from . Together these axioms form ZF in a customary formulation. ZFC adds the axiom of choice; none of the elementary constructions below needs choice. We do not claim that listing the axioms proves their consistency.
Definition 1.1.3
(The construction axioms in symbols)
Write for . Written out in the language of , the five construction axioms named above and Foundation are the following sentences.
In Infinity, , and are abbreviations. Each can be eliminated in favor of a formula using only and , because the next proposition shows that the sets they name exist and are unique. Many books state Pairing, Union and Power set in a weaker form that asks only for a set containing the required members. Separation then cuts such a set down to the exact set displayed here, so the two versions give the same theory.
Proposition 1.1.4
(Elementary consequences of the construction axioms)
- There is exactly one set with no members. Its existence already follows from Separation, because first-order logic proves that at least one set exists.
- For all sets , the sets , , , and exist and are unique. For each fixed finite list , the set exists.
- The union exists for every set , and the intersection exists for every nonempty set .
Proof
(Each set is pinned down by its membership condition)
Uniqueness in every case is extensionality: two sets satisfying the same membership condition have the same members. For existence of an empty set, logic gives some set , and Separation gives , which has no members. Thus the Empty set axiom is convenient but redundant.
Pairing with gives . Union applied to the pair gives , whose members are exactly the members of together with the members of ; this is . In particular . Separation in gives and . For a fixed , the set is obtained from singletons by binary unions. This is a separate proof for each concrete . A single theorem about a variable would instead need and recursion.
Part 3 is the Union axiom, together with the worked example on intersections below, which applies Separation inside one member of .
Definition 1.1.5
(Ordered pair, relation and function)
Define the ordered pair by Kuratowski's construction
A relation from to is a subset of . A function is such a relation for which each is paired with exactly one . Its graph is a set. Its codomain is part of the declared map, and can be larger than its range.
Theorem/proposition
Proposition 1.1.6
(Bounded comprehension does not produce a universal set)
For every set , the set is not a member of . Consequently there is no set containing every set as a member.
Proof
(The Russell set escapes every set)
Separation gives and the equivalence . If , substitute to obtain , a contradiction. Hence . If were universal, would nevertheless have to belong to it. Notice that the argument proves ; it does not assert that the definition of was illegitimate.
Proposition 1.1.7
(Ordered pairs and products exist)
The ordered-pair definition satisfies exactly when and . For any sets , the Cartesian product is a set.
Proof
(Recovering coordinates and bounding the product)
The intersection of the members of is , including the case . Thus equality of ordered pairs first gives . Their unions then give . If , the latter set is a singleton and forces ; otherwise its unique member different from is both and . This proves the forward implication, and the reverse implication follows by substitution.
Let . Pairing and union construct . Each ordered pair with is a subset of , so belongs to . Separation inside that twice-iterated power set selects exactly the required ordered pairs. This establishes existence of , rather than merely writing a suggestive brace expression.
Proposition 1.1.8
(Coordinates lie two unions down)
If , then and . Consequently, if and are sets whose members are ordered pairs and is any set, the domain, range, inverse, restriction to and composite below are all sets:
Proof
(Two unions recover a bound for the coordinates)
The hypothesis says . Hence , and so . Let . Separation in defines and with the displayed conditions. The inverse is separated from , the restriction from itself, and the composite from . Each bounding set exists by the product proposition.
The point is that a relation need not come with a declared product containing it. The bound is recovered from the relation alone. The same lemma justifies the remark in the descent section below that every value of a function lies in .
Proposition 1.1.9
(Images and inverse images exist)
For a function and a subset , its image is a set. For , its inverse image is a set. A composition of set functions is a set function.
Proof sketch or proof idea
Each proposition is proved by naming the set that bounds the candidates; the first two proofs appear directly after their statements.
Proof
(Images, inverse images and composites by separation)
Separation inside defines . Separation inside defines . For , separate from all pairs such that some has and . Existence and uniqueness in the two function definitions prove that this relation is the graph of . Replacement also constructs , but is unnecessary once the codomain bounds the values.
Worked examples
Worked example 1.1.10
(An intersection needs a domain)
If is a nonempty set of sets, choose a member and define
The result is independent of the chosen member, because its membership condition is “belongs to every member of ”. No axiom of choice is needed to take one member of one nonempty set in a proof. If , the unbounded condition “belongs to every member” is true of every set and does not define a set. An empty intersection relative to a specified ambient set is instead .
Worked example 1.1.11
(Replacement can collect iterated constructions)
Let and . Finite recursion gives a uniquely determined for every natural number . Replacement collects , and union then produces . Saying “there is a set at each finite stage” does not alone justify the collection of all stages. Recursion and replacement are the bridges. Transfinite recursion will be developed in the next chapter; this example uses its elementary finite form.
Worked example 1.1.12
(Functions need not come from formulas)
For a set , every subset of satisfying uniqueness is a function to . Characteristic functions correspond bijectively to subsets of by . Their existence as sets comes from separation inside , not from a defining formula for each one. The tempting argument “there are only countably many formulas but is uncountable, so some subset is undefinable” is not a theorem of ZF: definability by a formula is a metatheoretic notion, and if ZF is consistent it has models in which every set is definable without parameters. Set existence and definability are distinct questions.
Worked example 1.1.13
(Foundation excludes membership cycles)
If , then is a nonempty set whose only member intersects , contrary to foundation. If , apply foundation to : each of its members intersects it. Foundation therefore excludes these cycles. Russell's contradiction did not use foundation and remains a separate obstruction to a universal set.
From Minimal Elements to Descending Sequences
The Axiom of Foundation is stated for sets. It says that every nonempty set has an element with . Arguments about "infinite descent" are often phrased in terms of sequences, so this section connects the two. In each argument below, we first name a specific nonempty set and then apply Foundation to that set.
No given function can descend forever
We write for the universe of all sets. is a proper class, not a set, so "" is shorthand. Formally, is a set of ordered pairs. It is a function, its domain is , and each value is some set. Nothing restricts which sets the values are.
Proposition 1.1.14
(No given function descends forever)
No such function satisfies for every .
Proof
(Apply Foundation to the range)
Suppose is such a function and let
is a set. Replacement applied to gives this directly. Alternatively, every value of lies in , so Separation applied to that set gives .
is nonempty because . By Foundation there is some with . Since , we have for some .
By hypothesis . Also , because it is a value of . So , which contradicts .
The proof is short, but two of its moves deserve to be isolated.
Proof X-ray
Where the descent argument gets its set
- Foundation does the work. It supplies as a consequence of an axiom. Moving from "" to " for some " is ordinary existential reasoning about one fact. No choice principle is involved.
- The function is given in advance. We never built . The hypothesis hands it to us complete, and its range is then a single set to which Foundation applies.
The set version needs no sequence
Proposition 1.1.15
(No nonempty set is closed under stepping down)
There is no nonempty set such that every has some with .
Proof
(One application of Foundation)
The hypothesis says for every . Foundation says some has . These statements contradict each other.
It is tempting to argue from such a set to a sequence. Start at some , pick , then pick , and so on.
That construction makes infinitely many dependent choices. Each choice depends on the previous one, and no rule says which predecessor to take. Collecting the choices into a single function generally requires a principle such as Dependent Choice.
So we should not claim that, in bare ZF without Foundation, any counterexample to Foundation yields a descending -sequence. The argument that uses minimality inside a set needs no such principle.
Finite membership cycles
Let . Suppose
That is, for , and . Repeated values are allowed.
Treat the finite indexed list as a given set function on ; its range is a set. Every element of equals some , so it is enough to check each :
- If , then .
- If , then .
So every element of meets . This contradicts Foundation.
The cases and are the self-membership and two-cycle results of the worked example on membership cycles.
An honest finite chain
The chain
is a legitimate descent. Let and check each element against :
- , which is nonempty.
- , which is nonempty.
- .
So is the Foundation witness in , and it is the only one. The descent stops at because has no element to step down to.
Foundation does not forbid descent. It forbids descent that never reaches a stopping point inside a given set.
Common mistake
(Invoking infinite descent without naming a set)
A common error is to write “otherwise there would be an infinite descending chain, contradicting Foundation” without naming the set to which Foundation is applied. Foundation concerns sets, not imagined processes.
For this particular minimal-element contradiction, specify a nonempty set and show that every element of that set meets it. Examples are the range of a given function, or the finite set of entries in a cycle.
Exercises
Quick check
(Show that no set satisfies , using .)
Ask whether the only element of can be disjoint from .
Solution · Answer
is nonempty, and its only element is . If , then , so . Then no element of is disjoint from , which contradicts Foundation.
Quick check
(Show that there are no sets with , , and , even if some of them are equal.)
Collect the three sets into one set and check each element against it.
Solution · Answer
Let . Each element meets :
- .
- .
- .
If some of the sets coincide, has fewer elements, but each of its elements is still one of , so each still meets . Foundation fails either way. For instance, if , this is the previous check.
Quick check
(Why does the range argument differ from “choose a member, then choose a member of that, and so on” when no function is supplied?)
Compare what is given by hypothesis with what would have to be constructed.
Solution · Answer
In the range argument, is a hypothesis, so its range is immediately a set, and Foundation applies once to that set.
Without a supplied function, we must create one from infinitely many unspecified choices, each depending on the previous one. For an arbitrary serial relation, Dependent Choice justifies constructing such a function; a particular relation may already have a definable selection rule and need no extra choice principle.
The set-level statement avoids this entirely. Applying Foundation once to gives the contradiction, with no sequence constructed.
Worked example 1.1.16
(Quotient sets exist without a choice of representatives)
Let be an equivalence relation on a set . For each , separation gives its equivalence class . Each class is an element of . Thus the quotient set can be constructed directly by separation:
No representative has been chosen in this construction. The projection is a set function, and it is surjective by the defining condition on the quotient. A right inverse for would choose one representative from each class; that is an additional selection problem, rather than a requirement for constructing the quotient itself. For example, integer congruence classes modulo a positive integer have canonical least nonnegative representatives, but a general equivalence relation comes with no such convention.
This distinction is useful whenever a construction identifies different descriptions of the same object. Rational numbers may be constructed from integer pairs with a nonzero denominator modulo cross-multiplication equivalence. The quotient exists before any proof that each rational admits a unique reduced fraction with positive denominator. A preferred normal form, when available, is extra mathematical structure.
Worked example 1.1.17
(All structures on a fixed underlying set)
A topology on is a collection of subsets of , so it lies in . Separation in this containing set produces the set of all topologies on by imposing the open-set axioms. Similarly, all binary operations on form a subset of after the function condition is imposed. Group structures are then selected by formulas expressing associativity, an identity and inverses.
The phrase “all groups” is more delicate because it has no fixed underlying-set bound. The preceding construction proves only the existence of all group structures on a given . It does not turn the entire universe of groups into a set. When one later forms a collection of algebraic structures, the first check should be whether the underlying sets are bounded or indexed by an already existing set. This is the same discipline that separated safe comprehension from the Russell construction at the beginning. Quantifiers in the formal language may range over the entire universe, but such a quantifier does not by itself gather all of its satisfying objects into one object.
Concept lens
Two kinds of existence
The distinction between a formula and a set can be read as the distinction between a specification and an available domain of objects. The condition defining an equivalence class is meaningful for every input, but the class is a set because its members lie in the known set . The collection of those classes is then bounded by . Each construction has a separate existence warrant.
When reading a new definition, identify three things: the variables allowed as parameters, the set in which candidates are sought, and the condition selecting the result. If the definition instead assigns an output to each input, identify the input set and prove uniqueness of the output before invoking replacement. This procedure is especially useful for nested constructions, where one valid inner definition can disguise an unjustified outer collection. The quotient examples show that representative selection and quotient existence are different mathematical tasks. Likewise, constructing all structures on a fixed underlying set is not the same as constructing all structures; the range of the containing set always needs separate justification. Such checks are not a formal ritual: they ensure that later maps, orders and algebraic operations have actual objects to work with.
Indexed families and maps: following an element
A formula for an indexed union can look like a formal manipulation, but it records a particular order of quantifiers. Let and be sets, and let be a set function on with each . The union consists of those for which some has ; the intersection relative to consists of those for which every has . Both are sets by separation from . In particular, if , the union is and the relative intersection is . These values follow from the quantifiers, not from a choice of a first index.
Let be a function and let be a set function on with . Taking an inverse image commutes with either operation, even for the empty family, provided the intersection on the left is relative to and that on the right is relative to :
Proof. For any , membership in the first left-hand side says that belongs to some . This is equivalent to saying that belongs to some . Replacing “some” by “every” gives the second equality. Extensionality turns these elementwise equivalences into set equalities. When is empty, they read and .
For a set-indexed family with , direct images always preserve unions. Indeed belongs to exactly when there are an index and an with ; exchanging the two existential quantifiers gives . For intersections one always has
where intersections are relative to and respectively. If is nonempty and is injective, equality holds: for a point on the right, choose one index and a preimage of . Each other contains some preimage of , which must equal by injectivity. Thus the same lies in every . No simultaneous selection of preimages is needed. For empty , equality instead requires , that is, surjectivity.
Counterexample mode
Images can lose intersections
It is tempting to expect direct images to commute with intersections for every map, as inverse images do. Take , , and . For and , the intersection of the domains is empty, so its image is empty. Yet . The two witnesses for need not be the same input. For the empty-family case, instead take the injective map with . The two sides are and , showing that injectivity alone does not settle the empty case. The correct statement is the one above: inclusion always, equality for nonempty families when is injective, and equality for the empty family exactly when is surjective.
Two round trips
For and , element chasing gives
The first preimage includes every point sharing an image with a point of ; it equals for every exactly when is injective. For the converse, if distinct have the same image, take . The second round trip discards the elements of outside the range; it equals for every exactly when is surjective. Taking proves the converse. These are statements about all subsets; equality may happen for an individual subset without injectivity or surjectivity.
Practice with solutions
Quick check
(Let be , and let be the multiples of and the multiples of . Find .)
Either intersect first, or take the two preimages first.
Solution · Answer
The intersection consists of multiples of ; is such a multiple exactly when is a multiple of . Equivalently the two preimages are the multiples of and , whose intersection gives the same answer.
Quick check
(For the constant map above, compute and . Explain each result.)
Use the two round-trip formulas.
Solution · Answer
The first set is because both points map to . The second is empty because is outside the range.
Quick check
(If is injective but not surjective, does it preserve intersections of all nonempty families of subsets of ? What about the empty family?)
Treat the nonempty and empty index sets separately.
Solution · Answer
Yes for every nonempty family, by the injectivity proof above. The empty-family equality fails: its sides are and , which differ because is not surjective.
Common mistakes
Common mistake
(A brace expression is not an existence proof)
Writing is not an existence proof. Supply an ambient set and separation, or a uniquely specified set-indexed image and replacement. Conversely, replacement does not collect the values of a rule over a proper class of inputs. The input must be a set.
Common mistake
(Confusing membership with inclusion)
Do not confuse with , or membership with inclusion. We have for every set , but is an additional assertion.
Summary
The axioms license particular constructions. Separation controls selection, replacement controls set-indexed images, and power set controls collections of subsets. Relations and functions become ordinary sets once their graphs are constructed. This accounting makes later arguments about orders, cardinality and computation mathematically meaningful.
Exercises
Quick check
(Construct and the set of all functions using explicitly named containing sets.)
Solution · Answer
Separation in gives . Every function graph lies in . Separate those for which . This also handles : its unique function graph is empty, for every .
Quick check
(Prove that if , then . Give an example showing that does not imply .)
Solution · Answer
If and , transitivity of inclusion gives . For a counterexample take and . Then , but and , so .
Quick check
(Let and . Prove that inverse images preserve unions, intersections and relative complements. Give a direct-image counterexample for intersections.)
Solution · Answer
For any , means or , exactly membership in the union of the two inverse images. Replace “or” by “and” for intersections, and use “not in ” for . For direct images, the constant map sends the disjoint singletons to the same nonempty set, so but .
Quick check
(Suppose a definable rule assigns a unique set to every set . Explain why replacement does not imply that is a set, even when .)
Solution · Answer
Replacement requires a set of inputs ; quantification over all sets is not such an input. For the identity rule the asserted image would be a universal set, already proved impossible. A rule can be meaningful on the entire universe without having a set of all its values.
Quick check
(Using only Empty set, Power set and Replacement, prove that exists for all sets . Thus Pairing follows from the other axioms.)
Solution · Answer
Power set applied twice to gives , a set with exactly two members. Apply Replacement to it with parameters and the formula
Each of the two inputs has exactly one output: goes to and goes to . The set of values is . The argument also covers , where the set of values is .
Quick check
(Prove that every instance of Separation follows from Replacement together with the Empty set axiom.)
Solution · Answer
Fix a set and a formula , and argue by cases, which classical logic allows. If no satisfies , the empty set has exactly the required members. Otherwise fix one with ; this is one existential instantiation, not a choice principle. Apply Replacement to with parameters and the formula
Every has exactly one output. The set of values contains each satisfying , and also , which satisfies ; it contains nothing else. So it equals .
Quick check
(Prove that and for every set . Find a set with .)
Solution · Answer
If , then , so . Conversely, if for some , then . Extensionality gives the first equality. If , every member of lies in , so , that is, . For we get and , which has a member not in .
Quick check
(Prove that no set contains every singleton . Then explain why defining as would not give an ordered pair.)
Solution · Answer
If contained every singleton, then every set would satisfy , so would be a set containing every set. The bounded Russell proposition rules this out. For the second part, by extensionality. With this would give , so the first coordinate could not be recovered. Kuratowski's definition breaks this symmetry, because is the intersection of its members.