# Definable subset

• Jan 4th 2013, 02:31 AM
andrei
Definable subset
The set of all $\displaystyle n$-tuples $\displaystyle (b_1,\,b_2,\,\dots,\,b_n)\in(U_M)^n$ for which $\displaystyle M\models\varphi(b_1,\,b_2,\,\dots,\,b_n)$ is called a definable subset of $\displaystyle M.$ The set $\displaystyle U_M$ is the universe of structure $\displaystyle M.$

Sometimes I think I do not understand what a definable subset is.

Here is an exercise on definable subset:

Let $\displaystyle U_M$ be the underlying set for structure $\displaystyle M.$ Suppose that $\displaystyle A\subset(U_M)^3$ is a definable subset of $\displaystyle M.$
Suppose we rearrange the order of the $\displaystyle n$-tuples. Consider the set of all $\displaystyle (z,\,x,\,y)$ such that $\displaystyle (x,\,y,\,z)$ is in $\displaystyle A.$ Show that this set is definable.

Then I say that the the sought formula is as follows:

$\displaystyle (x=y\wedge y=z\to\varphi(x,\,y,\,z))\wedge(x\not= y\vee y\not= z\to\bigvee_{i}(x=a_{i3}\wedge y=a_{i1}\wedge z=a_{i2}))$

where $\displaystyle (a_{i1},\,a_{i2},\,a_{i3})\in A$ and $\displaystyle \varphi$ defines $\displaystyle A.$

While it may be correct, I feel that there is a simpler formula. What do you think?
• Jan 4th 2013, 03:25 PM
emakarov
Re: Definable subset
I don't understand what $\displaystyle a_{i1}$, $\displaystyle a_{i2}$ and $\displaystyle a_{i3}$ are. Suppose $\displaystyle \varphi(x,y,z)$ defines $\displaystyle A$ and let $\displaystyle B=\{(z,x,y)\mid (x,y,z)\in A\}$. The required formula must have three free variables and no constants, except possibly those that occur in $\displaystyle \varphi$.

We have $\displaystyle (x,y,z)\in A\iff(z,x,y)\in B$, i.e., $\displaystyle (y,z,x)\in A\iff(x,y,z)\in B$. Therefore, $\displaystyle B$ is defined by $\displaystyle \psi(x,y,z)$ where $\displaystyle \psi(x,y,z)\equiv\varphi(y,z,x)$.