# Definable subset

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

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

Here is an exercise on definable subset:

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

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

$(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 $(a_{i1},\,a_{i2},\,a_{i3})\in A$ and $\varphi$ defines $A.$

While it may be correct, I feel that there is a simpler formula. What do you think?
• Jan 4th 2013, 04:25 PM
emakarov
Re: Definable subset
I don't understand what $a_{i1}$, $a_{i2}$ and $a_{i3}$ are. Suppose $\varphi(x,y,z)$ defines $A$ and let $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 $\varphi$.

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