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

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

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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) $.

share|cite|improve this answer
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

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.