1. Logic

Hi. I have this problem to solve:

(∀x(P(x,x)∧∀x∀y∀z[(P(x,y)∧P(y,z))→P(x,z)]∧∀x∀y[P(x,y)∨P(y,x)])→∃y∀xP(y,x).

In natural language this means that if a relation P is reflexive and transitive and for two elements a,b we have P(a,b)∨P(b,a) then there is another element d in the universe that for every other element c of the universe we have P(d,c).

Here is the first question:
Give an interpretation that is no model of the above type. Seek an interpretation in an infinitive universe. The universe could be the natural numbers and the interpretation some known relation among the natural numbers.

Some help ?? Thank you.

2. To understand this formula better, we could consider an obvious example of a reflexive, transitive and total (x <= y \/ y <= x) relation: non-strict order on natural numbers. The formula says that there is the least element. Well, on natural numbers with regular <= there is indeed the least element. But what if we choose a set other than natural numbers? Or we could recall that natural numbers don't have the largest element, so what relation could we choose to interpret <=?

Give an interpretation that is no model of the above type.
Do you by chance study type theory?

3. Originally Posted by emakarov
To understand this formula better, we could consider an obvious example of a reflexive, transitive and total (x <= y \/ y <= x) relation: non-strict order on natural numbers. The formula says that there is the least element. Well, on natural numbers with regular <= there is indeed the least element. But what if we choose a set other than natural numbers? Or we could recall that natural numbers don't have the largest element, so what relation could we choose to interpret <=?

Do you by chance study type theory?
Yes but I want something that it's not a model of the type. And <= is a model correct ?

4. What I am saying is that by considering a different set with regular <= or by considering natural numbers with a different <= you'll get a non-model.

5. Originally Posted by emakarov
What I am saying is that by considering a different set with regular <= or by considering natural numbers with a different <= you'll get a non-model.

Yes and thank you but I want the relation to be also reflexive and transitive. It must not satisfy just the third part : there is another element d in the universe that for every other element c of the universe we have P(d,c). Thats why I am so confused. And it must also be about natural numbers.

6. Well, all the hint I can give is that there is a set of numbers with <= without the least element, and the set of natural numbers does not have the greatest element.

7. Originally Posted by emakarov
Well, all the hint I can give is that there is a set of numbers with <= without the least element, and the set of natural numbers does not have the greatest element.
Do you mean to take >= on the natural numbers? Because if so I still dont get how it is not a model. I am confused. Because I understand that there would be no largest element but I have = (equality) also. So there could be the same element.

8. I just dont get how to say it.

9. Do you mean to take >= on the natural numbers? Because if so I still dont get how it is not a model. I am confused.
Yes, I am thinking about $\displaystyle \langle\mathbb{N},\ge\rangle$, i.e., natural numbers with the $\displaystyle \ge$ relation.
Because I understand that there would be no largest element but I have = (equality) also. So there could be the same element.
I don't understand your objection. Let's take 100. Is this the "least" element w.r.t. $\displaystyle \ge$, i.e., is it true that for every natural $\displaystyle m$, $\displaystyle 100 \ge m$? Can we say the same about other numbers?

10. Originally Posted by emakarov
Yes, I am thinking about $\displaystyle \langle\mathbb{N},\ge\rangle$, i.e., natural numbers with the $\displaystyle \ge$ relation.
I don't understand your objection. Let's take 100. Is this the "least" element w.r.t. $\displaystyle \ge$, i.e., is it true that for every natural $\displaystyle m$, $\displaystyle 100 \ge m$? Can we say the same about other numbers?
I think I took it the wrong way. I thought that 100 of course its not the greatest but m could be 100 (m=100) so I satisfy the type. Thank you very much.

11. I have also to prove with induction that this type applies to every definite universe. Any ideas there ?

Thank you again.

12. What is a "definite universe"? And what does "apply to a universe" mean? I am asking because these are not universally-accepted terms.

13. For example in another set of natural numbers that has both the greatest and the least element. Not infinite universe. And I have to prove that this type is correct for all the non infinite universes. Hope I explained.

14. For finite sets the formula can be proved by induction on the size of the set. A singleton has its minimum, and for the induction step, you remove one element x, find the minimum y of the rest of the elements, and then find the minimum of x and y. Note that the fact that any two elements are comparable is used to compare x and y.

In general, if some fact is true for finite sets and false for infinite ones, very often it is proved by induction on the size of the set.

15. Originally Posted by emakarov
For finite sets the formula can be proved by induction on the size of the set. A singleton has its minimum, and for the induction step, you remove one element x, find the minimum y of the rest of the elements, and then find the minimum of x and y. Note that the fact that any two elements are comparable is used to compare x and y.

In general, if some fact is true for finite sets and false for infinite ones, very often it is proved by induction on the size of the set.

Thankl you.

Page 1 of 3 123 Last