I get that something such as R={(0, 0),(0, 1),(1, 1),(1, 2),(0, 2),(2, 2)} on the set {0, 1, 2} would be reflexive, anti-symmetric, transitive and a total ordering, however things that are less cut and dry such as:

Suppose that F is a set of files, and R is the relation on F where fRg if g depends on f. That is, f must come before g. Noting that the dependency may not be direct - g might depend on f through some intermediary files such as h or j.

I can tell that it is transitive (based on last part of question), that is fRh ∧ hRg → fRg, but am unsure how to prove whether or not R is reflexive, irreflexive, symmetric, anti-symmetric, partial ordering or total ordering (strict or not) and the equivalence class.

How would I go about identifying these?

  • $\begingroup$ Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, use MathJax. $\endgroup$ – dantopa May 20 at 4:16
  • $\begingroup$ Is it possible for $f$ to depend on $g$ and simultaneously $g$ to depend on $f$ (for $f\ne g$)? Is it possible for a file $f$ to depend on itself? $\endgroup$ – Gerry Myerson May 20 at 4:45
  • $\begingroup$ @GerryMyerson I do not believe fRf is valid and that f≠g, and so if gRf is not valid and only fRg is, then it cannot cannot be symmetric, making it anti-symmetric, I don't think elements relate to themselves (I assume based on f≠g, not sure how to prove/ if correct), thus is irreflexive, making this irreflexive, anti-symmetric and transitive, which is a strict partial ordering correct? $\endgroup$ – Anan May 20 at 5:14
  • $\begingroup$ Sounds good to me. You could write it up and post it as an answer. $\endgroup$ – Gerry Myerson May 20 at 5:27
  • $\begingroup$ @GerryMyerson so because f≠g, fRf is invalid, this all creates a strict partial ordering, but how would I go about showing whether or not it is actually a strict total ordering or not? I know to be a total ordering it must first suffice partial ordering. $\endgroup$ – Anan May 20 at 5:57

Your Answer

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

Browse other questions tagged or ask your own question.