cardinality formulae

**kumpel** · March 9th 2010, 05:23 AM

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?

**kumpel** · March 9th 2010, 07:42 AM

Originally Posted by kumpel

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

**emakarov** · March 9th 2010, 09:48 AM

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.

**emakarov** · March 9th 2010, 10:10 AM

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

**kumpel** · March 9th 2010, 12:06 PM

Originally Posted by emakarov

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.

**PiperAlpha167** · March 9th 2010, 10:08 PM

Originally Posted by kumpel

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.

**emakarov** · March 10th 2010, 03:34 AM

This seems correct.

**kumpel** · March 10th 2010, 07:57 AM

Originally Posted by PiperAlpha167

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.

**PiperAlpha167** · March 11th 2010, 05:08 AM

Originally Posted by kumpel

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?

**kumpel** · March 11th 2010, 06:57 AM

Originally Posted by PiperAlpha167

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?

**PiperAlpha167** · March 11th 2010, 08:26 AM

Originally Posted by kumpel

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.

Thread: cardinality formulae

LinkBack

Thread Tools

Display

cardinality formulae

bound

notes

Similar Math Help Forum Discussions

problem in addition formulae and double angle formulae

formulae

t formulae

Using Formulae

R formulae (double angle formulae) URGENT

Search Tags