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 $T=$ and those formulae involve atoms from a finite set $M=$.
Show that if $a_i \models a_i _+_1 , i=0,1,2,..$, then there is a natural number $m\leq2^n$ which $a_m \equiv a_m_+_1$

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

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

Use pigeonhole principle where pigeons are pairs of formulas $(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 $a_i=a_{i+2}\ne a_{i+1}$ you mean $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 $S(a_i)$ the set of interpretations that satisfy $a_i$, $S(a_{i+1})$ the set of interpretations that satisfy $a_{i+1}$, then $a_i \models a_{i+1}$ Iff $S(a_i) \subseteq S(a_{i+1})$

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

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

then since $a_i \models a_{i+1}$ then $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 $a_0,\dots, a_{2^n+1}$.

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

Use pigeonhole principle where pigeons are pairs of formulas $(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 $a_i=a_{i+2}\ne a_{i+1}$ you mean $a_i \models a_{i+2} \nvDash a_{i+1}$????

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

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

then since $a_i \models a_{i+1}$ then $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 $2^n+1$ set inclusions $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 $2^n$. This means that at least one of the inclusions must be non-strict.

by $a_i \models a_{i+2} \nvDash a_{i+1}$ you mean $a_i \models a_{i+2} \nvDash a_{i+1}$????
No, I was referring to the truth values of $a_i$, $a_{i+1}$ and $a_{i+2}$ under some fixed interpretation. Fix an interpretation $I$, and let $I(a_k)$ denote the truth value, say 0 or 1, of $a_k$ at $I$. Then the sequence $I(a_0),\dots,I(a_{2^n+1})$ is monotonic. There is at most one $k$ such that $0=I(a_k)\ne I(a_{k+1})=1$. Thus, each interpretation distinguishes at most two consecutive formulas. Since there are $2^n+1$ pairs of formulas in the sequence and only $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 $2^n+1$ set inclusions $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 $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 $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 $|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 $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, $2^n + 1\le |S(a_0)| + 2^n + 1\le |S(a_{2^n+1})|$. However, this is impossible because $|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..
$|S(a_i)|<|S(a_{i+1})|\leq2^n$

$|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 $m\leq2^n$
which gives $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 $m\leq2^n$ IFF $a_m \equiv a_{m+1}$

The basic idea is you are using proof by contradiction.
You know for a fact that
$|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 $m$ does $a_m\equiv a_{m+1}$.
This means the inequalities must be strict:
$|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 $|S(a_0)| < 0$.

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

Page 1 of 2 12 Last