Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By emakarov

Thread: Definable subset

  1. #1
    Oct 2007

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Oct 2009

    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)$.
    Thanks from andrei
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Mar 11th 2012, 08:08 AM
  2. [SOLVED] Proof that if A is a subset of P(A), P(A) is a subset of P(P(A))
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: May 23rd 2011, 04:26 PM
  3. Proof on Openness of a Subset and a Function of This Subset
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Oct 24th 2010, 09:04 PM
  4. subset U subset is NOT subspace of Superset?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 20th 2009, 04:17 PM
  5. subset
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 18th 2008, 06:25 AM

Search Tags

/mathhelpforum @mathhelpforum