1. ## Propositional Logic Problem

Hi...
I have an excercise that is keeping me up all day and night..
The problem is:
"There is an infinite set of formulae $\displaystyle T=<a_0,a_1,a_2,....>$ and those formulae involve atoms from a finite set $\displaystyle M=<p_1,p_2,p_3,.....,p_n>$.
Show that if $\displaystyle a_i \models a_i _+_1 , i=0,1,2,..$, then there is a natural number $\displaystyle m\leq2^n$ which $\displaystyle a_m \equiv a_m_+_1$

2. Here are some hints. Consider only the formulas $\displaystyle a_0,\dots, a_{2^n+1}$.

There are $\displaystyle 2^n$ valuations on n variables. For each valuation, how does the sequence $\displaystyle a_0,\dots, a_{2^n+1}$ of truth values look like? Can we have $\displaystyle a_i=a_{i+2}\ne a_{i+1}$?

Use pigeonhole principle where pigeons are pairs of formulas $\displaystyle (a_0,a_1), (a_1,a_2),\dots,(a_{2^n},a_{2^n+1})$ that can have different truth values for some valuation and holes are valuations.

3. by $\displaystyle a_i=a_{i+2}\ne a_{i+1}$ you mean $\displaystyle a_i \models a_{i+2} \nvDash a_{i+1}$????

4. Thank you very much...
I Hope to solve this since i m new to maths....
and finally sleep before 6AM(everyday)...
many many thnx

5. how about some sets theory?
proving that, If $\displaystyle S(a_i)$ the set of interpretations that satisfy $\displaystyle a_i$, $\displaystyle S(a_{i+1})$ the set of interpretations that satisfy $\displaystyle a_{i+1}$, then $\displaystyle a_i \models a_{i+1}$ Iff $\displaystyle S(a_i) \subseteq S(a_{i+1})$

also from the above
$\displaystyle a_i \equiv a_{i+1}$ Iff $\displaystyle S(a_i) = S(a_{i+1})$

Then i say the max compinations of interpetation for n atoms is $\displaystyle 2^n$
this as far as i got, and i don't know if i m right..

then since $\displaystyle a_i \models a_{i+1}$ then $\displaystyle S(a_0) \subseteq S(a_1) \subseteq S(a_2)\subseteq........\subseteq S_{max}(a)=2^n$)

6. Originally Posted by emakarov
Here are some hints. Consider only the formulas $\displaystyle a_0,\dots, a_{2^n+1}$.

There are $\displaystyle 2^n$ valuations on n variables. For each valuation, how does the sequence $\displaystyle a_0,\dots, a_{2^n+1}$ of truth values look like? Can we have $\displaystyle a_i=a_{i+2}\ne a_{i+1}$?

Use pigeonhole principle where pigeons are pairs of formulas $\displaystyle (a_0,a_1), (a_1,a_2),\dots,(a_{2^n},a_{2^n+1})$ that can have different truth values for some valuation and holes are valuations.
By $\displaystyle a_i=a_{i+2}\ne a_{i+1}$ you mean $\displaystyle a_i \models a_{i+2} \nvDash a_{i+1}$????

7. Originally Posted by nick1978
If $\displaystyle S(a_i)$ the set of interpretations that satisfy $\displaystyle a_i$, $\displaystyle S(a_{i+1})$ the set of interpretations that satisfy $\displaystyle a_{i+1}$, then $\displaystyle a_i \models a_{i+1}$ Iff $\displaystyle S(a_i) \subseteq S(a_{i+1})$

also from the above
$\displaystyle a_i \equiv a_{i+1}$ Iff $\displaystyle S(a_i) = S(a_{i+1})$

then since $\displaystyle a_i \models a_{i+1}$ then $\displaystyle S(a_0) \subseteq S(a_1) \subseteq S(a_2)\subseteq........\subseteq S_{max}(a)=2^n$
I agree, and I like this idea. We have a sequence of $\displaystyle 2^n+1$ set inclusions $\displaystyle S(a_0) \subseteq S(a_1) \subseteq S(a_2)\subseteq\dots\subseteq S(a_{2^n+1})$, and the number of elements in the last set is at most $\displaystyle 2^n$. This means that at least one of the inclusions must be non-strict.

by $\displaystyle a_i \models a_{i+2} \nvDash a_{i+1}$ you mean $\displaystyle a_i \models a_{i+2} \nvDash a_{i+1}$????
No, I was referring to the truth values of $\displaystyle a_i$, $\displaystyle a_{i+1}$ and $\displaystyle a_{i+2}$ under some fixed interpretation. Fix an interpretation $\displaystyle I$, and let $\displaystyle I(a_k)$ denote the truth value, say 0 or 1, of $\displaystyle a_k$ at $\displaystyle I$. Then the sequence $\displaystyle I(a_0),\dots,I(a_{2^n+1})$ is monotonic. There is at most one $\displaystyle k$ such that $\displaystyle 0=I(a_k)\ne I(a_{k+1})=1$. Thus, each interpretation distinguishes at most two consecutive formulas. Since there are $\displaystyle 2^n+1$ pairs of formulas in the sequence and only $\displaystyle 2^n$ interpretations, two formulas must be equal under all interpretations.

8. you are a saint for even looking into my problem. can't find words to express my graditute...
Another way i tried is by using Complete induction
For only one atom n=1 , n=k etc..but no luck there....
At least with your guidance i will try and finaly have some sleep...

9. Originally Posted by emakarov
I agree, and I like this idea. We have a sequence of $\displaystyle 2^n+1$ set inclusions $\displaystyle S(a_0) \subseteq S(a_1) \subseteq S(a_2)\subseteq\dots\subseteq S(a_{2^n+1})$, and the number of elements in the last set is at most $\displaystyle 2^n$. This means that at least one of the inclusions must be non-strict.

Thnx I m full of ideas .. i have some ideas even in my dream when i sleep if i sleep ..but i can't reach to a conclusion

10. If $\displaystyle S(a_0) \subset S(a_1) \subset S(a_2)\subset\dots\subset S(a_{2^n+1})$ and each inclusion is strict, then $\displaystyle |S(a_0)| < |S(a_1)| < |S(a_2)|<\dots< |S(a_{2^n+1})|$. (Here |A| denotes the number of elements in a set A.) There are $\displaystyle 2^n+1$ "less than" signs, and for each of them its right-hand side must be at least one greater than the left-hand side. Therefore, $\displaystyle 2^n + 1\le |S(a_0)| + 2^n + 1\le |S(a_{2^n+1})|$. However, this is impossible because $\displaystyle |S(a_{2^n+1})|\le 2^n$.

11. That seems a good start for the allnight session of PL.I ll try to involve the m counter...in this....thnx again....for all your trouble...

12. Thnx to your help i think i am one step before solving the problem..
$\displaystyle |S(a_i)|<|S(a_{i+1})|\leq2^n$

$\displaystyle |S(a_0)| < |S(a_1)| < |S(a_2)|<\dots< |S(a_{2^n+1})|\leq2^n$
So we want to prove that there is a natural number $\displaystyle m\leq2^n$
which gives $\displaystyle a_m \equiv a_m_+_1$
How can we prove that...
i feeel so close to the solution but lack the basis..
Thnx again

13. The sequence of numbers you have should be nonnegative and must be integers. They must be monotonically nondecreasing.
Is it possible to have the strictly increasing chain values that does not exceed 2^n?

If not, then there must be a point where (it cannot increase, but it cannot decrease either, which means) ...

14. i can't express it with mathimatical terms..i know that the sequence has an upper limit 2^n...but i can't present the right formula to say $\displaystyle m\leq2^n$ IFF $\displaystyle a_m \equiv a_{m+1}$

The basic idea is you are using proof by contradiction.
You know for a fact that
$\displaystyle |S(a_0)| \leq |S(a_1)| \leq |S(a_2)|\leq\dots\leq |S(a_{2^n+1})|\leq2^n$

Now, assume that for no $\displaystyle m$ does $\displaystyle a_m\equiv a_{m+1}$.
This means the inequalities must be strict:
$\displaystyle |S(a_0)| < |S(a_1)| < |S(a_2)| < \dots < |S(a_{2^n+1})| \leq 2^n$

But this lead to a contradiction because this forces $\displaystyle |S(a_0)| < 0$.

This means the initial assumption was incorrect, and there must exist an $\displaystyle m$ s.t. $\displaystyle a_m\equiv a_{m+1}$.

Page 1 of 2 12 Last