0
$\begingroup$

My question is really simple.

Can a set $A$ and its complement $\bar{A}$ have intersection? I cannot prove it nor find a counterexample.

EDIT

My question is general but it comes to my mind after seeing the well open problem in computational complexity, is NP=coNP?. Here NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs and coNP is its complement. How a set and its complement be equal?

$\endgroup$
  • 2
    $\begingroup$ How do you define the complement? $\endgroup$ – Lee Mosher Feb 8 '17 at 2:03
  • 1
    $\begingroup$ Um... by definition.... If foozlenucks are precisely everything that is not a duck, then is it possible for there to be a duck that is a foozlenuck? $\endgroup$ – fleablood Feb 8 '17 at 2:13
  • $\begingroup$ Take an element $x$ from the intersection, is it in A? $\endgroup$ – dave Feb 8 '17 at 2:14
  • $\begingroup$ A decision-problem is in coNP iff its complement (as a problem not as a set) is in NP. So it's prefectly possible to be in both NP and coNP, this just depends on the problem at hand. $\endgroup$ – Henno Brandsma Feb 8 '17 at 5:11
4
$\begingroup$

Of course they have an intersection. Any two sets have an intersection.

In this case the intersection is the empty set. But that doesn't stop it from being the intersection.


As for NP and coNP, they are not complements. There are problems that are in both NP and coNP -- such as all the decidable ones -- and problems that are in neither, such as the set of true statements of first-order integer arithmetic.

CoNP is the set of decision problems for which the instances where the answer is "no" have efficiently verifiable proofs. A given set is in coNP iff its complement is in NP, but coNP itself is not the complement of NP.

$\endgroup$

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.