Results 1 to 11 of 11

Math Help - cardinality formulae

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    8

    cardinality formulae

    I need help in the following problem:

    Let \mathcal{L}=\mathcal{L}() be a (first order) language. Find \mathcal{L}-fomulae \phi_{\leq n}, \phi_{= n}, \phi_{\geq n} that for any \mathcal{L}-structure \mathcal{A} with support A=|\mathcal{A}|:

    \mathcal{A}\models \phi_{\leq n} \Leftrightarrow |A|\leq n
    \mathcal{A}\models \phi_{= n} \Leftrightarrow |A|= n
    \mathcal{A}\models \phi_{\geq n} \Leftrightarrow |A|\geq n.

    Some ideas: Because the signature is empty, there are no relations, no functions and no constants. The only possible formulae consist of terms like x_i=x_j with variables and the logical signs (,), \neg,\vee, \exists (others excluded by demand).

    For \phi_{= n} I guess something like:

    \exists x_i\left[\neg \left(\bigvee_{j=1}^{n}(x_i=x_j)\right)\vee\left(\  bigvee_{l=1}^{n-1}\bigvee_{m=l+1}^{n}(x_l=x_m) \right)\right]

    but this seems quite complex. Is there a shorter form? Or is it even correct? And the others?
    Last edited by kumpel; March 9th 2010 at 05:40 AM. Reason: typing error
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2010
    Posts
    8
    Quote Originally Posted by kumpel View Post
    \exists x_i\left[\neg \left(\bigvee_{j=1}^{n}(x_i=x_j)\right)\vee\left(\  bigvee_{l=1}^{n-1}\bigvee_{m=l+1}^{n}(x_l=x_m) \right)\right]
    Throw it away.

    Somewhere I found a better solution. Given \phi_{\geq n} the others can easily be expressed in terms of this expression:

    \phi_{\leq n}=\neg\phi_{\geq (n+1)} and
    \phi_{= n}=\neg \phi_{\geq n}\vee \neg \phi_{\geq n}

    Trying to prove \mathcal{A}\models \phi_{\geq n} \Leftrightarrow |A|\geq n for
    \phi_{\geq n}=\exists x_1...\exists x_n \left(\bigwedge_{1\leq i\le j \leq n} (x_i\neq x_j)\right)
    via induction over n I get into trouble in the step from n-1 to n
    \phi_{\geq n}=\exists x_n\left(\phi_{\geq (n-1)}\wedge\left(\bigwedge_{j=1}^{n-1}x_j\neq x_n\right)\right)
    ...don't know how to proceed...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765
    A couple of quick remarks:

    Shouldn't it be \phi_{=n}=\phi_{\ge n}\land\phi_{\le n}?

    In this formula, the variables x_1,\dots,x_{n-1} are not bound.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765
    Maybe you can put \phi_{\ge n}=\exists x_1\dots x_n\psi_{\ge n} and prove by induction that \mathcal{A}\models(\psi_{\ge n}(x_1,\dots,x_n))\theta iff \theta(x_1),\dots,\theta(x_n) are different. Here \theta is an environment, i.e., a mapping from \{x_1,\dots,x_n\} to the domain of \mathcal{A}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2010
    Posts
    8

    bound

    Quote Originally Posted by emakarov View Post
    Shouldn't it be \phi_{=n}=\phi_{\ge n}\land\phi_{\le n}?
    yes, of course. I used copy-paste instead of brain.
    In this formula, the variables x_1,\dots,x_{n-1} are not bound.
    yes, thanks. what I wrote is not consequent with the above. If you put \exists-quantor for x_1,...,x_{n-1} in front of the second conjunction part, then the proof is easy.
    But, I hope, it works with the unbound variables as well! Because then, the modelling requires \forall-quantor for x_1,...,x_{n-1} and after using the induction assumption for \phi_{\geq(n-1)}, it can be shown that:

    <br />
\mathcal{A}\models \forall x_1...\forall x_{n-1}\exists x_n\left(\bigwedge_{j=1}^{n-1}x_j\neq x_n\right) \Leftrightarrow |A|\geq n<br />

    What do you think? I just started learning logic, so I try to become familiar with all this.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by kumpel View Post
    I need help in the following problem:

    Let \mathcal{L}=\mathcal{L}() be a (first order) language. Find \mathcal{L}-fomulae \phi_{\leq n}, \phi_{= n}, \phi_{\geq n} that for any \mathcal{L}-structure \mathcal{A} with support A=|\mathcal{A}|:

    \mathcal{A}\models \phi_{\leq n} \Leftrightarrow |A|\leq n
    \mathcal{A}\models \phi_{= n} \Leftrightarrow |A|= n
    \mathcal{A}\models \phi_{\geq n} \Leftrightarrow |A|\geq n.

    Some ideas: Because the signature is empty, there are no relations, no functions and no constants. The only possible formulae consist of terms like x_i=x_j with variables and the logical signs (,), \neg,\vee, \exists (others excluded by demand).

    For \phi_{= n} I guess something like:

    \exists x_i\left[\neg \left(\bigvee_{j=1}^{n}(x_i=x_j)\right)\vee\left(\  bigvee_{l=1}^{n-1}\bigvee_{m=l+1}^{n}(x_l=x_m) \right)\right]

    but this seems quite complex. Is there a shorter form? Or is it even correct? And the others?
    Can you provide a pointer to the source of this material?
    I'd like to see a fuller development.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765
    This seems correct.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2010
    Posts
    8
    Quote Originally Posted by PiperAlpha167 View Post
    Can you provide a pointer to the source of this material?
    I'd like to see a fuller development.
    Yes, but the text is in German. The exercise is here http://www.math.uni-heidelberg.de/lo...thlogik_05.pdf and the solution on page 6 here http://www.math.uni-heidelberg.de/lo...k/handout4.pdf . I hope it helps.
    Last edited by kumpel; March 10th 2010 at 07:59 AM. Reason: wrong link
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by kumpel View Post
    Yes, but the text is in German. The exercise is here http://www.math.uni-heidelberg.de/lo...thlogik_05.pdf and the solution on page 6 here http://www.math.uni-heidelberg.de/lo...k/handout4.pdf . I hope it helps.
    Thanks. Sadly, I don't read German. So I could be staring at the title of the textbook at either one of the links you provided and
    not even realize it. Can you just provide the title of the textbook and the author(s)? Presumably, it's a book on mathematical logic.
    Perhaps it's been translated into English.

    By the way, is Klaus Ambos-Spies your professor?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Mar 2010
    Posts
    8

    notes

    Quote Originally Posted by PiperAlpha167 View Post
    Thanks. Sadly, I don't read German. So I could be staring at the title of the textbook at either one of the links you provided and
    not even realize it. Can you just provide the title of the textbook and the author(s)? Presumably, it's a book on mathematical logic.
    Perhaps it's been translated into English.

    By the way, is Klaus Ambos-Spies your professor?
    I'm sorry. I'm working with the lecture notes from Prof Gloede (also on the site) from Heidelberg and they are not available in English, so I guess it won't help you.
    No, Prof. Spies is not my professor. Is he famous? Or are you only amused by his name?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by kumpel View Post
    I'm sorry. I'm working with the lecture notes from Prof Gloede (also on the site) from Heidelberg and they are not available in English, so I guess it won't help you.
    No, Prof. Spies is not my professor. Is he famous? Or are you only amused by his name?
    I asked about him becauce his name is on the front page of the first link that you kindly provided. You didn't see it?
    Naturally, I connected his name with the document and thus the problem.

    Is he famous? I don't know. You tell me.
    Am I amused by his name? No. Maybe your question was meant to be amusing.

    Adios.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: July 5th 2010, 06:20 AM
  2. formulae
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 7th 2009, 05:01 AM
  3. t formulae
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: November 4th 2009, 03:38 AM
  4. Using Formulae
    Posted in the Algebra Forum
    Replies: 16
    Last Post: December 14th 2008, 06:47 AM
  5. R formulae (double angle formulae) URGENT
    Posted in the Algebra Forum
    Replies: 8
    Last Post: April 10th 2008, 11:30 AM

Search Tags


/mathhelpforum @mathhelpforum