# Superstructure with sets as atomic/base entities

This question arose while learning nonstandard analysis.

The superstructure $V(X)$ of a nonempty set $X$ is defined recursively:

\begin{align*}V_0(X) &= X \\ V_{i+1}(X) &= V_i(X) \cup P(V_i(X)) \\ V(X) &= \bigcup_{i=0}^\infty V_i(X)\;, \end{align*}

where $i \in \mathbb{N}$ and $P$ is the powerset function. So it's a way to get every relation and function on $X$ that you could possibly want, by identifying the ordered pair $(a,b)$ with the set $\{\{a\},\{a,b\}\}$ or such. I'm great with this.

BUT what happens when there are relations in $X$ (as members of $X$)? I think that I need to distinguish between the relations that are formed by the superstructure construction and any relations that I might have started with in $X$. As an example problem, I want to prove (my book says it's true) that a relation $R$ is in $V(X)$ iff the domain and range of $R$ are in $V(X)$. This is not necessarily true if $R$ is in $X$. The members of $X$ that have members themselves don't necessarily empty out.

So are we supposed to distinguish between relations in $X$ and the relations that are formed from $X$?

Cheers, Rachel

-

I've seen the answer to this in several books now. The problem is dealt with simply by treating the members of X as "atoms". Even if you know (from the outside, being all-knowing) that X contains nonempty sets, you declare that members of X don't themselves have members in the same sense that the sets constructed from X have members. You can do this by distinguishing between membership relations or just pretending that members of X aren't sets.

-

Just a note to complement Rachel's own answer: one formal way to sidestep this problem is to restrict attention to base sets -- sets $X\neq\emptyset$ such that for any $x\in X$, $x\cap V(X)=\emptyset$. One simply eliminates the problem of "extra membership" by always building superstructures over base sets.

Then the individuals relative to $V(X)$ are all elements in $X$, and those in $V(X)\setminus X$ are sets relative to $V(X)$.

This raises the question of how to replace one set by a base set of the same size. One method is to take a set $X$ of the same cardinality as our original set, but such that every element in $\bigcup X$ has the same rank $\alpha$, with $\alpha$ some fixed infinite ordinal. One can then show that for any $n$, if $x\in V_{n}(X)$, then $rank(x)\neq\alpha$. So no $V_{n}(X)$ can share any element with any $x\in X$, since each $y\in x\in X$ has rank $\alpha$. This means that $x\cap V(X)=\emptyset$ for any $x\in X$, and so $X$ is a base set.

This is how things are presented in the 2012 reprint of Chang & Keisler's Model Theory: see section 4.4.

-

It's not clear what you mean by "a relation in $X$". Do you mean a relation *on* $X$? If so, a relation on a set $X$ is usually defined as a subset of $X \times X$, and using the definition for this that you gave yourself, namely the set of all $\{\{a\},\{a,b\}\}$ for all $a, b \in X$, then any relation on $X$ is, as a set of ordered pairs, a subset of the power set of the power set of $X$, and its domain and range both are subsets of $X$ and thus both a subset and an element of $V(X)$.

If, on the other hand, you mean a relation $R \in X$, then indeed, neither domain or range need to be an element or subset of $V(X)$. A simple example would be $R = S \times S$ for some set $S$ and $X = \{R\}$. Then clearly, $dom(R) = range(R) = S \notin V(X)$ and $S \not\subset V(X)$.

Lastly, if you mean $R \subset X$, then, by definition, $R \in P(X) \subset V(X)$, and of course for all $r \in R \Longrightarrow r \in V(X)$, but in general, $dom(R) \notin V(X)$. For example, take $X = R = S \times S$ for some nontrivial set $S$. Then $dom(R) = S$ is neither an element nor a subset of $X$ and thus not in $V(X)$.

It is possible for both of those cases that domain and range are elements of or subsets of $V(X)$, which depends on if they were elements or subsets of $X$. For example, for any relation $R$ we may just define $X = R \cup dom(R) \cup range(R)$.

-
Thanks for the response. To clarify, I mean "in" to denote set membership, so $R \in X$. Also, I mean an n-ary relation to generally be a set of n-tuples. So as we've now both said, if $R \in X$, the domain and range of $R$ are not necessarily in $V(X)$. So how is this situation dealt with? Any relations in $X$ are special wrt $V(X)$ -- they don't have the same properties as the other relations in $V(X)$. So what are they called or how are they treated? – Rachel Mar 17 '12 at 5:54
I'm not really deeply familiar with nonstandard analysis, where you say this definition comes from. I merely observed the set properties here to confirm what you suspect. I would think that whenever this construction is used, X is chosen in a way that makes your question obsolete (such as discussing $V(\mathbb{R})$), but without knowing details on where you cite that from, I'm just guessing. – Desiato Mar 18 '12 at 1:15