# Propotional Logic Problem

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Dec 14th 2010, 06:35 PM
nick1978
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$

• Dec 15th 2010, 02:01 AM
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.
• Dec 15th 2010, 04:34 AM
nick1978
by $a_i=a_{i+2}\ne a_{i+1}$ you mean $a_i \models a_{i+2} \nvDash a_{i+1}$????
• Dec 15th 2010, 04:35 AM
nick1978
Thank you very much...
I Hope to solve this since i m new to maths....
and finally sleep before 6AM(everyday)...
many many thnx
• Dec 15th 2010, 05:25 AM
nick1978
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$)
• Dec 15th 2010, 07:34 AM
nick1978
Quote:

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}$????
• Dec 15th 2010, 07:44 AM
emakarov
Quote:

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.

Quote:

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.
• Dec 15th 2010, 08:01 AM
nick1978
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... :)
• Dec 15th 2010, 08:25 AM
nick1978
Quote:

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 :(
• Dec 15th 2010, 10:45 AM
emakarov
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$.
• Dec 15th 2010, 11:58 AM
nick1978
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...
• Dec 15th 2010, 10:21 PM
nick1978
Thnx to your help i think i am one step before solving the (Headbang) 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
• Dec 15th 2010, 10:28 PM
snowtea
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) ...
• Dec 16th 2010, 09:25 AM
nick1978
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}$
• Dec 16th 2010, 09:58 AM
snowtea

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}$.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last