Let $A=\{1,2,3,4\}$. Let $K$ be the set of all transitive relations over $A$ except for the empty relation which is not an element of $K$. As we know $\subseteq$ relation is a partially ordered relation therefore $\subseteq$ is a relation over $K$, which means that $K$ is a partially ordered set. Prove that $K$ has a greatest element and find it. Find minimal element of $K$ and prove that it's minimal.

In order to avoid confusion the definitions of greatest and minimal elements are according to Wikipedia.

Let $G$ be: $$ \bigg\{(1,1), (2,2), (3,3), (4,4),(1,2),(2,1), (1,3), (3,1),\\ (1,4), (4,1), (2,3), (3,2), (2,4), (4,2), (3,4), (4,3)\bigg\} $$ There're $16$ unique ordered pairs in $K$ and $G$ contains all of them. Also any subset of $K$ is a combination of the $16$ unique pairs which are all contained in $G$. Therefore $G$ is the greatest element of $K$.

I think there're $16$ minimal elements in $K$ as each unique ordered pair doesn't contain any other subsets. We're given that the empty set is not part of $K$ and the $16$ pairs are unique, therefore cannot contain each other. Therefore they're minimal members.

There's no least element because it only the empty set is the subset of any set but it's given that it's not part of $K$.

I'm not sure whether my proof is formal enough and I really prove the greatest and minimal elements.

  • $\begingroup$ It's ok. (Just mention that [ $A$ with the only relation $(j,k)$ ] for some fixed values $j,k$, that may coincide is indeed transitive.) It was hard to find the question, the title is not really reflecting it. $\endgroup$ – dan_fulea Jun 13 '18 at 17:15
  • $\begingroup$ @dan_fulea please let me know of a better title, I'll edit it $\endgroup$ – user123429842 Jun 13 '18 at 17:20
  • $\begingroup$ The "How to find" inside the title was misleading. You know how to find them! Just ask for a check of argument, correctness, completeness... $\endgroup$ – dan_fulea Jun 13 '18 at 17:32
  • 1
    $\begingroup$ As an aside... you could have more simply written $G$ as $A\times A$ without needing to explicitly write out all of its elements. $\endgroup$ – JMoravitz Jun 13 '18 at 17:32

You are correct. The set $G$ of all possible pairs is always transitive, and is maximal since if $R$ is any relation it must be a subset of $G$. Since they took out the empty relation, which is also transitive, you do get 16 minimal elements, since any one element set is transitive whether or not it is a pair of distinct or the same elements.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.