Partial Ordering True/False

238 Views Asked by At

I have a math question for a computer science homework that looks like this:

State whether each of the following relations is a partial ordering, and explain why or why not.

  1. “isFatherOf” on the set of people.
  2. “isAncestorOf” on the set of people.
  3. “isOlderThan” on the set of people.
  4. "isSisterOf” on the set of people.
  5. {〈a,b〉,〈a,a〉,〈b,a〉}on the set{a,b}.
  6. {〈2,1〉,〈1,3〉,〈2,3〉}on the set{1,2,3}

I have the solution

  1. No - fails transitive clause (a is not the father of c)
  2. Yes
  3. Yes
  4. Yes
  5. Yes
  6. No - {1,2,3} is not an element of {{2,1},{1,3},{2,3}}

I did not do well on my discrete math class and was wondering if I have the correct logic.

1

There are 1 best solutions below

0
On

1 could be explained better: no person is his own father, so $x \text{ isFatherOf } x$ fails for all $x$, so no reflexivity.

2 is dubious: I say the same applies here. no-one is his/her own ancestor, really. Not in common parlance anyway. But if you extend the meaning in that way, it will work as a p.o.

  1. If isOlderThan is stricly older, no, as partial orders $R$ should obey $xRx$, otherwise yes.

  2. isSisterOf is again not reflexive, so I would say no.

  3. fails: $bRa$ and $aRb$ but not $bRb$, transivity fails, and reflexivity too, on $x=b$.

  4. no, because of the failure of reflexivity again. $(1,1)$ is not in the set. $\{1,2,3\}$ is totally irrelevant !