Question about partially ordered sets

Printable View

April 6th 2011, 08:59 AM
posix_memalign

Question about partially ordered sets

Is (S, R) a poset if S is the set of all people in the world and $(a, b) \in R$ , where a and b are people if a = b or a is an ancestor of b?

I know that I have to determine if this is reflexive, antisymmetric and transitive.

So I start with reflexivity and imagine that I have two people, I can either pick two people who are identical (a = b) or I can pick a person a who is an ancestor of a person b.

If I pick two who are identical then it is trivially reflexive, but if I choose a person a who is an ancestor of b, then it is not reflexive, as obviously a cannot be ancestor of him or herself.

Thus it is not reflexive and is not a poset either.

Yet, I see that in the solution for this problem that it is indeed reflexive, how is that possible?
April 6th 2011, 09:27 AM
Plato

Quote:

Originally Posted by posix_memalign

Is (S, R) a poset if S is the set of all people in the world and $(a, b) \in R$ , where a and b are people if a = b or a is an ancestor of b?
Yet, I see that in the solution for this problem that it is indeed reflexive, how is that possible?

Read the definition again.
April 6th 2011, 11:34 AM
posix_memalign

Quote:

Originally Posted by Plato

Read the definition again.

I did but I think I fail to understand something really fundamental; is it sufficient that only some of the people maintain the a = b property for R to be reflexive? If not, how does the definition ensure that they are all equal when the very same definition states that they might not be (i.e. because of the 'or')?
April 6th 2011, 11:57 AM
Plato

Quote:

Originally Posted by posix_memalign

I did but I think I fail to understand something really fundamental; is it sufficient that only some of the people maintain the a = b property for R to be reflexive? If not, how does the definition ensure that they are all equal when the very same definition states that they might not be (i.e. because of the 'or')?

Reflexive simply means that each element is the set is related to itself. For each $a$ in the set the pair $(a,a)$ is in the relation. That is laid in the very definition of this particular relation.

Equality is the very basic and simple reflexive relation.
April 6th 2011, 12:17 PM
MoeBlee

Let 'Rab' stand for '<a b> in R'.

Let 'Cab' stand for 'a is an ancestor of b'.

The problem, as you stated it, is a bit deceptive.

Ordinarily, we would think we are given:

(1) Rab if and only if (a=b or Cab)

But the problem, as you stated it, actually gives only:

(2) If a=b or Cab, then Rab.

Now we have to check:

Reflexive: Is it the case that, for any a, we have Raa?

For (1) or (2) it's easy.

Antisymmetric: Is it the case that, for any a and b, we have 'if Rab and Rba, then a=b'?

With (1) it's easy. But with (2) we get a different answer.

Transitive: Is it the case that, for any a, b, and c, we have 'Rab and Rbc, then Rac'?

With (1) it's easy. But with (2) we get a different answer.
April 6th 2011, 12:34 PM
MoeBlee

Quote:

Originally Posted by Plato

Read the definition again.

To be precise, as the problem is stated, no definition was given. A definition would be a biconditional, but the statement of the problem gives only a conditional. It is not clear that a biconditional was what was actually intended.
April 6th 2011, 12:39 PM
Plato

Quote:

Originally Posted by MoeBlee

To be precise, as the problem is stated, no definition was given. A definition would be a biconditional, but the statement of the problem gives only a conditional. It is not clear that a biconditional was what was actually intended.

I totally disagree with that.
The relation was clearly defined in the OP.
April 6th 2011, 12:45 PM
MoeBlee

The wording given was:

<a b> in R IF a=b or a is an ancestor of b.

That is, (a=b or a is an ancestor of b) -> <a b> in R.

The wording was not given as:

<a b> in R if AND ONLY IF a=b or a is an ancestor of b.
April 6th 2011, 12:51 PM
posix_memalign

Quote:

Originally Posted by Plato

Reflexive simply means that each element is the set is related to itself. For each $a$ in the set the pair $(a,a)$ is in the relation. That is laid in the very definition of this particular relation.

Equality is the very basic and simple reflexive relation.

Ah, I see ... however, I thought I finally understood this but even when it means that a and b should only be related, I still don't see how this can be true.
There are two cases, if a = a, then they are obviously related, no problem.
But the case a = a does not necessarily hold for every element in the set? For at least some of them there is the possibility that a is the ancestor of b, and for this particular a, how does the reflexive property hold? Doesn't it have to hold for every element in the set?
April 6th 2011, 12:54 PM
MoeBlee

Quote:

Originally Posted by posix_memalign

But the case a = a does not necessarily hold for every element in the set? For at least some of them there is the possibility that a is the ancestor of b, and for this particular a, how does the reflexive property hold? Doesn't it have to hold for every element in the set?

You're mixed up about the tests for the relation.

Go back to the precise tests (here, a, b, and c are assumed to be people):

Reflexive: Is it true that, for any a, we have Raa?

That is, is every person either him(her)self or an ancestor of him(her)self?

Antisymmetric: Is it true that, for any a and b, we have 'if Rab and Rba, then a=b'?

That is, is it true that if either a and b are ancestors of each other or a and b are the same person, then a and b are the same person?

Transitive: Is it the true that, for any a, b, and c, we have 'Rab and Rbc, then Rac'?

That is, it true that if a, b, and c are the same person or a is an ancestor of b is an ancestor of c then either a and c are the same person or a is an ancestor of c?

That's all there is to it.