Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to show that

(a) $ \forall \alpha \; \exists \beta$ such that $\beta = \{ dom R \; | \; R \in \alpha \}$

I'm having difficulty proving this axiomatically. I'm not even certain that it can be done. I'm trying to solve this as part of the larger problem of showing that

(b) $\forall \alpha \; dom\bigcup\alpha = \bigcup\{dom R \; | \; R \in \alpha\}$

My approach to solving (a), so far, is the following (supposed to be a fitch-style proof - I couldn't figure out how to do fitch in TeX):


(1) Take $A$

(2) Take $s$

(3) Assume $s \in dom \bigcup A$
(4) [Somehow show that $\{dom R \; | \; R \in \alpha\}$ exists for any $\alpha$]
(5) Therefore, there exists $B$ = $\{dom R \; | \; R \in A\}$
(6) From (3), $\exists \psi \;(<s,\psi> \in \bigcup A)$
(7) Fix $y$ : $<s,y> \in \bigcup A$
(8) From (7), $\exists \mu \; (<s,y> \in \mu \; \wedge \; \mu \in A)$
(9) Fix $R$ : $<s,y> \in R \; \wedge \; R \in A$
(10) $dom R \in B$    [Remember (5): $B$ = ${dom R \; | \; R \in A}$]
(11) $s \in \bigcup B$    [Because $s \in dom R \; \wedge \; dom R \in B$]

[This gets me the first side of the bi-conditional]

(12) Assume $s \in \bigcup\{domR \; | \; R \in A\}$
(13) [Show that $s \in dom \bigcup A$]

[This gets me the second side of the bi-conditional]
(14) From (3-13) : $s \in dom \bigcup A \; \leftrightarrow \; s \in \bigcup \{ dom R \; | \; R \in A\}$

(15) $\forall \varphi \; ( \varphi \in dom \bigcup A \; \leftrightarrow \; \varphi \in \bigcup \{ dom R \; | \; R \in A \} )$

$\forall \alpha \forall \varphi \; ( \varphi \in dom \bigcup \alpha \; \leftrightarrow \; \varphi \in \bigcup \{ dom R \; | \; R \in \alpha \} )$

My problem is figuring out step (4).

(This is not homework - I'm teaching myself set theory from Enderton's in my spare time, and am a little stumped on this one.)


share|cite|improve this question
Just to be clear, you want to show that for every set $\alpha$ there is a collection $\beta$ which has exactly all the domains of all the relations which are elements of $\alpha$? – Asaf Karagila May 14 '11 at 17:45
Yes, that is correct. I am sorry if I did not make that very clear. By collection do you mean set? I haven't gotten very far in Enderton, so I don't know the difference between a collection and a set, if there is a difference. If what I want to show is not possible, or misguided, an explanation of why would be great. – maxenglander May 14 '11 at 18:02
Carl gave a good answer, I will just give you an answer on this comment, namely a collection is any subclass of the universe, i.e. just a bunch of elements from the universe. A set is a collection which is also an element of the universe. – Asaf Karagila May 14 '11 at 18:06
Thanks for the explanation Asaf. – maxenglander May 14 '11 at 18:30
up vote 3 down vote accepted

First let $X = \bigcup \bigcup \bigcup \alpha$. Then let $Y$ be the powerset of $X$. Now for any $R \in \alpha$, we have $\operatorname{dom} R \in Y$. This is because an ordered pair $(a,b)$ is coded in the Kuratowski style as $\{\{a\}, \{a,b\}\}$, so if you unwrap three layers of $\{ \}$ from $\alpha$ you will get to $a$. If you use a different pairing operation, you may need a different number of unions in the definition of $X$.

Now, using $Y$, we can use the axiom of separation to form $$ \{ \operatorname{dom}(R) : R \in A\} = \{ D \in Y : \exists R ( R \in A \land D = \operatorname{dom}(R))\}. $$ To turn this into a formal proof, you just need to use the axioms of whatever set theory you have to follow the three steps.

This is the general pattern you use to show that various sets exist in formal set theory: first, you move to some set like $Y$ of high enough rank that all the elements of your target set are elements of $Y$. Then you use separation to pull out just the elements of $Y$ that you want to be in your target set, assuming that the property that you want to select for can be expressed in the language of set theory.

share|cite|improve this answer
Carl - thank you for the crystal clear explanation. This general pattern for showing the existence of sets has been the biggest struggle for me as I read through Enderton. I wanted to use the axiom of separation to get what I needed, but didn't know how to get the "higher" Y. Thanks a lot! – maxenglander May 14 '11 at 18:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.