Logic

Printable View

Show 40 post(s) from this thread on one page

January 21st 2010, 11:03 PM
milagros

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.
January 22nd 2010, 12:38 AM
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 <=?

Quote:

Give an interpretation that is no model of the above type.

Do you by chance study type theory?
January 22nd 2010, 01:18 AM
milagros

Quote:

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 ?
January 22nd 2010, 01:22 AM
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.
January 22nd 2010, 01:26 AM
milagros

Quote:

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.
January 22nd 2010, 01:36 AM
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.
January 22nd 2010, 06:35 AM
milagros

Quote:

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. (Crying)(Crying) Because I understand that there would be no largest element but I have = (equality) also. So there could be the same element.
January 22nd 2010, 07:07 AM
milagros

I just dont get how to say it. (Headbang)(Headbang)(Headbang)(Headbang)
January 22nd 2010, 07:54 AM
emakarov

Quote:

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 $\langle\mathbb{N},\ge\rangle$ , i.e., natural numbers with the $\ge$ relation.

Quote:

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. $\ge$ , i.e., is it true that for every natural $m$ , $100 \ge m$ ? Can we say the same about other numbers?
January 22nd 2010, 08:02 AM
milagros

Quote:

Originally Posted by emakarov

Yes, I am thinking about $\langle\mathbb{N},\ge\rangle$ , i.e., natural numbers with the $\ge$ relation.
I don't understand your objection. Let's take 100. Is this the "least" element w.r.t. $\ge$ , i.e., is it true that for every natural $m$ , $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. (Clapping)(Clapping)
January 23rd 2010, 01:45 AM
milagros

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

Thank you again.
January 23rd 2010, 02:16 AM
emakarov

What is a "definite universe"? And what does "apply to a universe" mean? I am asking because these are not universally-accepted terms.
January 24th 2010, 12:21 AM
milagros

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.
January 24th 2010, 02:56 AM
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.
January 24th 2010, 04:21 AM
milagros

Quote:

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.

Show 40 post(s) from this thread on one page