"make sure you understand why for a non trivial property $S$, $\bar{S}$ is also non trivial"

My assumption is: $S$ is non trivial property: There are L1,L2 such that $L_{1},L_{2}\in RE$ and L1 sattisifies the property whereas L2 doesn't.

If i assign the complement then it still holds the same just reverse the relation between L1 which is now $L_{1}\notin S $ and $L_{2}\in S$ ==>$\bar{S}$ is a non trivial.

Is my assumption correct?

  • 2
    $\begingroup$ Yes, what you wrote is correct. Generally, we discourage questions of the form "is my answer correct", but Is there anything about it that concerns you? If so, what do you think you're missing? $\endgroup$
    – Shaull
    Jan 20 at 14:46
  • $\begingroup$ @Shaull without hinting that compelmnt is also non trivial I would think that it may be trivial. In general I don't have a reliable study source, thus I am not sure about my answers $\endgroup$ Jan 20 at 17:25

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.