# Logic

Show 40 post(s) from this thread on one page
Page 1 of 3 123 Last
• Jan 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.
• Jan 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?
• Jan 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 ?
• Jan 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.
• Jan 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.
• Jan 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.
• Jan 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.
• Jan 22nd 2010, 07:07 AM
milagros
• Jan 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?
• Jan 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)
• Jan 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.
• Jan 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.
• Jan 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.
• Jan 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.
• Jan 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
Page 1 of 3 123 Last