# Proving the inverse of a relation exists

A relation is a set of ordered pairs $(x,y)$ that relates $x$ to $y$ somehow. It's a very weak relation in the sense one thing can be related to many things. A function is a special relation where each thing in the domain is related to only one thing in the image.

$xRy\iff(x,y)\in R$

Given a relation $R$ the inverse, $R^{-1}$ is "given by" $\{(y,x)|(x,y)\in R\}$

$\text{Dom}(R)=\{x|\exists y:xRy\}$ $\text{Ran}(R)=\{y|\exists x:xRy\}$

My problem is I cannot prove these three sets (inverse, domain and range) exist.

What have I tried?

If I write $\{x|P(x)\}$ where $P$ is some property of $x$ to show it exists I must find a set $A$ that exists, where $P(x)\implies x\in A$ - then this is (uniquely) the set $\{x\in A|P(x)\}$ - obviously the choice of $A$ isn't unique.

So I need to find a set $A$ such that $P((x,y),R)\implies (x,y)\in A$ where $P((x,y),R)$ is $(x,y)\in R$

Regarding domain (range will be essentially the same) I am having trouble building a set which contains the first thing in the ordered pairs that make up the relation - I don't have cardinality yet so I am not sure what "property" to formulate to extract them.

The Axioms I have so far:

• Axiom of existence: there exists a set with no elements
• Axiom of extensionality (equality basically?): if two sets have the same elements they are identical
• Lemma showing the empty set is unique
• Axiom of schema of comprehension: $\{x\in A|P(x)\}$ exists where P is a property.
• Lemma showing the set given in the comprehension axiom is unique (justifying my notation)
• Axiom of a pair: for any A, B there is a set C such that $x\in C\iff[x\in A\text{ or }x\in B]$
• Axiom of union, given a set $S$, $x\in\cup S\iff\exists A\in S:x\in A$
• Axiom of power set - I think the key is here

I am looking for a very rigorous answer

• Are you sure that you don’t have the union axiom? Mar 2, 2015 at 22:45
• @BrianM.Scott I apologise! I do, I missed it. Should I repost this as a new Q? Mar 2, 2015 at 23:05
• No reason to repost; just edit it into the question. I’d already written a hint on the assumption that you really did have it. Mar 2, 2015 at 23:07
• @BrianM.Scott hints to gaps in early chapters of a book are not that helpful. I have a book that prides itself on not being the logicians approach - when filling in holes of stuff I am not that confident I want to know I'm write - please flesh out the hint so I can have that confidence. The book just defines these things, it is my question that is "do they even exist?" I'd like it answered. Mar 2, 2015 at 23:17
• Incase you doubt this @BrianM.Scott (which I do find a little bit offensive) the module at my university isn't even running this term, nor did I take it and the book is "Elementary Set Theory" by Thomas Jech and Karel Hrbacek third edition. Mar 2, 2015 at 23:18

Mission Prove the existence of the inverse relation given only axioms of Set Theory

Axioms The axioms we will assume are the ones you posted. That is to say, the axioms we assume are

• Axiom of set existence
• Axiom of extensionality
• Axiom (schema) of specification
• Axiom of pairing
• Axiom of union
• Axiom of power

Ordered Pairs We define ordered pairs

Notation Let $X$ be a nonempty set. Let $x,y\in X$. "$\{x,y\}$" is notation for "$\{z\in X:z=x\,\vee\, z=y\}$." "$\{x\}$" is notation for "$\{ x,x \}$."

Definition Let $X$ be a nonempty set. Let $x,y\in X$. The ordered pair with first coordinate $x$ and second coordinate $y$ is $\{ \{x\},\{x,y\} \}$.

Notation Let $X$ be a nonempty set. Let $x,y\in X$. "$(x,y)$" is notation for "ordered pair with first coordinate $x$ and second coordinate $y$."

Remark Let $X$ be a nonempty set. Let $x,y,u,v\in X$. If $(x,y)=(u,v)$, then $x=u$ and $y=v$.

Cartesian Products We define Cartesian products

Proposition For all sets $A$ and $B$, there exists a unique set whose elements are exactly those elements $(a,b)$ such that $a\in A$ and $b\in B$.

Proof Let $A$ and $B$ be arbitrary sets. Define $V\overset{\mathrm{def}}{=} \left\{\mathcal{X}\in \mathcal{P}(\mathcal{P}(A\cup B)):\exists a\in A,\exists b\in B[\mathcal{X}=(a,b)] \right\}$. Therefore $V$ is a set whose elements are exactly those elements $(a,b)$ such that $a\in A$ and $b\in B$. By the axiom of extensionality, $V$ is unique.$\qquad\square$

Definition Let $A$ and $B$ be sets. The Cartesian product of $A$ and $B$ is the set whose elements are exactly those elements $(a,b)$ such that $a\in A$ and $b\in B$.

Notation Let $A$ and $B$ be sets. $A\times B$ is notation for "Cartesian product of $A$ and $B$."

Existence

[Sorry for posting pictures; I prefer to typeset in my LaTeX editor \newcommands + autocompletion. If you're up to the challenge, please update my post by replacing the pictures with genuine code]

• I am pretty sure you can copy and paste the \newcommands with dollar signs around them and it will work in your post.
– user29123
Mar 3, 2015 at 21:53
• This comment is copy and paste - but you did it too! I did get it, however I'm not entirely sure what your $\exists y\in\cup\cup R[(x,y)\in R]$ means, I wrote $\exists y\in\cup\cup R\text{ such that }(x,y)\in R$ (I use $|$ to mean such that when specifying a set and $:$ to mean "such that" in expression, so I actually wrote $\{x\in\cup\cup R|\exists y\in\cup\cup R:(x,y)\in R\}$ - I'm not sure why you used brackets and rather than speculating I'd rather ask.) Mar 4, 2015 at 21:49
• link.springer.com/chapter/10.1007%2F978-3-7643-9977-1_1 This is the best I could find online. A quick answer is that my bracket notation is a slight modification of the standard parenthesis. I prefer the bracket and reserve it only to signify "such that." The book I linked you teaches the standard notation which may be more helpful. Mar 5, 2015 at 2:27
• Hello again, if I may bother you again, I'd like a hint. I am trying to prove that $\forall A\ \mathcal{P}(\cup A)\notin A$ - I've been trying to do this by contradiction (and thinking about it for several days now) but getting nowhere. Any hints you can offer? Mar 9, 2015 at 16:12
• General Fact: For each set $X$, $X\subseteq \mathcal{P}(\bigcup X)$. So (by contradiction) $A\subseteq\mathcal{P}(\bigcup A)\in A$ implies $\mathcal{P}(\bigcup A)\in\mathcal{P}(\bigcup A)$. (this contradicts axiom of regularity) Mar 9, 2015 at 20:40

Each ordered pair $\langle x,y\rangle\in R$ is actually a set of the form $\{\{x\},\{x,y\}\}$. Recall that $x\in\bigcup y$ if and only if there is a $z\in y$ such that $x\in z$. Thus, the elements of $\bigcup R$ are sets of the form $\{x\}$ and $\{x,y\}$ for the ordered pairs $\langle x,y\rangle\in R$, and the elements of $\bigcup\bigcup R$ are elements of the underlying set for the relation. Specifically:

\begin{align*} \operatorname{dom}R&=\left\{x\in\bigcup\bigcup R:\exists y\in\bigcup\bigcup R\big(\langle x,y\rangle\in R\big)\right\}\\ \operatorname{ran}R&=\left\{y\in\bigcup\bigcup R:\exists x\in\bigcup\bigcup R\big(\langle x,y\rangle\in R\big)\right\}\;,\text{ and}\\ R^{-1}&=\left\{\langle y,x\rangle\in\left(\bigcup\bigcup R\right)\times\left(\bigcup\bigcup R\right):\langle x,y\rangle\in R\right\}\;. \end{align*}\tag{1}

In each case it’s clear that the sets that I’ve defined exist, via the union axiom and comprehension schema. (I am assuming that if you have ordered pairs, you have Cartesian products.) It’s also clear that they are at least subsets of what they purport to be, e.g., that everything in my definition of the domain of $R$ actually is in what we think of as the domain of $R$. The only thing that might still be open to question is whether these definitions actually pick up everything that they ought to pick up, but the introductory comments cover that. If, for example, $\langle x,y\rangle\in R$, then $\{x,y\}\in\bigcup R$, so $x,y\in\bigcup\bigcup R$, and the definitions in $(1)$ really do pick up $x$ in $\operatorname{dom}R$, $y\in\operatorname{ran}R$, and $\langle y,x\rangle$ in $R^{-1}$.

• Thanks for fleshing it out, I've still got the screenshot of the hint and haven't read this, I appreciate it! Mar 3, 2015 at 0:12
• @Alec: You’re welcome! Mar 3, 2015 at 0:15
• Okay I have one quick question, one I started doing the union of things (I only have R so it was quickly obvious) I did get it, however I'm not entirely sure what your $\exists y\in\cup\cup R((x,y)\in R)$ means, I wrote $\exists y\in\cup\cup R\text{ such that }(x,y)\in R$ (I use $|$ to mean such that when specifying a set and $:$ to mean "such that" in expression, so I actually wrote $\{x\in\cup\cup R|\exists y\in\cup\cup R:(x,y)\in R\}$ - I'm not sure why you used brackets and rather than speculating I'd rather ask.) Mar 4, 2015 at 21:48
• @Alec: We mean the same thing. I don’t think that I’ve seen your notation before; mine is a very standard one that’s been around for a long time: $\exists x\big(\varphi(x)\big)$ is ‘there is an $x$ such that $\varphi(x)$’. Some people also parenthesize the quantifiers: $(\exists x)\big(\varphi(x)\big)$. Mar 4, 2015 at 21:53
• Okay, may I pester you for hint with what I actually think is surprisingly interesting. The question is: Show $\mathcal{P}(\cup A)\notin A$ $\forall A$. I've been stuck on this for a while, the furthest I've gotten is: "Assume $\exists A(\mathcal{P}(\cup A)\in A$ and reach a contradiction, so $\mathcal{P}(\cup A)\in A\iff[x\in\mathcal{P}(\cup A)\implies x\in \cup A]$ we know this because $\mathcal{P}(\cup A)\in A$ so anything in the power set will also be in the union of $A$ - $\implies[\mathcal{P}(\cup A)\subseteq \cup A]$ - this is where I've gotten stuck. Mar 10, 2015 at 17:50