# How do I find the type of relation on an infinite set?

Imagine I'm given a set A = {∅, {∅}, {{∅}}, {{{∅}}},…} where ∅ is empty-set. Then I also have a relation on that set (actually on its power set) defined as: $R \subseteq \wp(A) \times \wp(A)$, where $R = \{(a, B) : a ∈ B\}$.

I have to figure out whether that relation is reflexive, irreflexive, symmetric, asymmetric or transitive.

Now, more than solving this specific exercise I'm looking to understand the actual process or mental model I need to follow to show this. What I currently do is that I imagine what could the set ℘(A) look like:

℘(A) = { ∅, { ∅, {∅} }, ... {∅, {∅}, {{∅}}, {{{∅}}}}

My logic here is that a power-set always has an empty set (hence the first element), and always has the entire set itself (A for this case) as an element, hence the last element after the dots. However, what happens in the middle is just a combination and rather messy and hard for me to think about.

Now going back to the problem at hand, because (a, B) : a ∈ B, I try with the first two elements I have wrote for ℘(A) and I see that (∅, { ∅, {∅} }) would be a valid element for that relation because ∅ is an element of { ∅, {∅} } and they're both elements of ℘(A). I'm confident then that (∅, ∅) won't appear because ∅ is not an element of ∅. So I'm safe to say it's NOT reflexive. I'm also fine with symmetry and asymmetry.

However, things get complicated with transitive relation because if (∅, { ∅, {∅} }) exists and ({ ∅, {∅} }, { { ∅, {∅} } ... }) exists then also (∅, { { ∅, {∅} } ... }) has to exist. Meaning I have to find out whether ∅ is an element of { { ∅, {∅} } ... }.

Because of infinity I can't really easily prove that and am having really hard times thinking about this.

The problem is that even if I kind of am able to wrap my hand around this specific problem, there are other similar ones that I have problems proving and I almost never get right.

Any help on specific methodologies on how to prove these things would be greatly appreciated.

• For transitivity, note that the question only arises when you have pairs of the form $(a,\{a\})$ and $(\{a\},\{\{a\}\})$. For the relation to be transitive it needs to be the case that $a\in\{\{a\}\}$ for all $a$. (The general methodological note here is not to worry about the picture of a list of stuff in curly braces, but to go back to the logical conditions that defined your sets.) – Malice Vidrine Jun 29 '15 at 20:21
• (Actually I misstated things in my above comment; the second term of the second pair needn't be $\{\{a\}\}$, but it will still turn out that $a$ will need to be a member of every $x\in\mathcal{P}(A)$ such that $\{a\}\in x$, which leads to the same problem.) – Malice Vidrine Jun 29 '15 at 23:51

Look at the sets in $A$, which we can describe as $\emptyset$ or "some finite number of matching braces around the empty set", essentially. Every set in $A$ is either empty, or has one element, namely the set that has "one less pair of braces". Note that $\emptyset \in \{\emptyset\}$, $\{\emptyset\} \in \{\{\emptyset\}\}$, etc. We build this set up recursively: $A$ is the smallest set such that $\emptyset \in A$, and if $a \in A$ then also $\{a\} \in A$.

So we could denote for short elements of $A$ as $0$ (empty set) and $n+1 := \{n\}$ for every $n$. The $n$ counts the number of braces, one could say.

Note that using the relation as described: $(a,b) \in R$ iff $a \in b$, we see that $(0,1) \in R$, $(1,2) \in R$, but e.g. not $(0,2) \in R$, as $2 = \{\{\emptyset\}\}$ has only one element $1 = \{\emptyset\}$ and it's not equal to $0 = \emptyset$. No element is a member of itself. Etc. This will hopefully allow you to answer the questions about this relation.

I think trying to write out $\mathcal{P}(A)$ probably isn't going to help you too much.

Elements of (the graph of) $R$ are pairs of the form $(a,B)$ where $a \in B$. Since $B \in \mathcal{P}(A)$, this must mean that if $a \in B$ then $a \in A$. Thus the first component $a$ of $(a,B)$ must in fact be an element of $A$. Then $(a,B) \in R$ for all subsets $B$ of $A$ containing $a$ as an element.

You correctly identified that it is not reflexive, since $\varnothing \in A$ but $(\varnothing, \varnothing) \not \in R$ since $\varnothing \not \in \varnothing$. Moreover you can't have $(a,a) \in R$ for any $a$, since that would imply $a \in a$, so the relation is irreflexive.

For symmetry, antisymmetry and transitivity, consider pairs of the form $(a,B) \in R$ where $B \not \in A$. Use the fact that $a \in A$ to deduce what you want to know.