The Gateway to Computer Science Excellence
+1 vote

The number of totally ordered set compatible to the given POSET are __________

in Set Theory & Algebra by Veteran (119k points) | 118 views

@Satbir is the ans clear to u??

1 Answer

+2 votes
Best answer

The word $\textrm{ "partial" }$ in the names $\textrm{ "partial order" }$or $\textrm{ "partial ordered set " }$ is used as an indication that not every pair of elements needs to be comparable.

So to make this $\textrm{ "partial order" }$ a $\textrm{ "total order" }$, we need the relation to hold for every two element of the $\textrm{ "partial order" }$such that the properties that is shown by the given $POSET$ is also maintained after adding relations.

Currently between the set ${i,g,e}$ and ${j,h,f}$ there is no relation but there is some relation between ${i,g,e}$ ( since ${i,g,e}$ set and ${j,h,f}$ set are at same level in the given hasse diagram )

similarly we have no relation between $b$ and $c$.( since  they are at different level in the given hasse diagram. )

for eg:-

let the $POSET$ be defined by the binary relation $\leq$

this means  i$\leq$g$\leq$e and j$\leq$h$\leq$f  but we don't know any relation between i and h.

So the question is asking that in how many ways we can add some relation in the  POSET such that the properties shown in the given hasse daigram holds between the nodes after adding the new relations also.

for eg :- we can add the relation i$\leq$j  or g$\leq$j but not g$\leq$e because e$\leq$g in the given POSET.

In how many ways we can add relation e,f,g,h,i,j such that i$\leq$g$\leq$e and j$\leq$h$\leq$f always holds = $\frac{6!}{3! * 3!}$

similarly for b and c we can add b$\geq$c or b$\leq$c i.e. $2$ ways.

So total ways = $2*\frac{6!}{3! * 3!}$ = 40 ways.

by Boss (24.2k points)
selected by
yes $^{6}C_{3}$
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,386 users