Math 2.0

Mathematical logic and foundations Theorem

De Morgan's laws for sets

Builds on ComplementUnionIntersectionDe Morgan's laws

Statement

Let UU be a set and let AA and BB be subsets of UU. Write Xc=U∖XX^c = U \setminus X for the complement of a subset XX in UU. Then (A∪B)c=Ac∩Bc,(A \cup B)^{c} = A^{c} \cap B^{c}, (A∩B)c=Ac∪Bc.(A \cap B)^{c} = A^{c} \cup B^{c}.

Remarks

The laws come from De Morgan's laws of logic, applied to x∈Ax \in A and x∈Bx \in B. They hold also for arbitrary families: the complement of ⋃iAi\bigcup_i A_i is ⋂iAic\bigcap_i A_i^c, and the complement of ⋂iAi\bigcap_i A_i is ⋃iAic\bigcup_i A_i^c. With set differences, C∖(A∪B)=(C∖A)∩(C∖B)C \setminus (A \cup B) = (C \setminus A) \cap (C \setminus B) for each set CC.

Reading path

To understand this page from the ground up, read these 21 pages in order. The foundations come first.

Show the path as a graph
Element, definition, no evidence levelElementdefinitionProposition, concept, no evidence levelPropositionconceptSet, definition, no evidence levelSetdefinitionConjunction, definition, no evidence levelConjunctiondefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionNegation, definition, no evidence levelNegationdefinitionPredicate, definition, no evidence levelPredicatedefinitionIntersection, definition, no evidence levelIntersectiondefinitionUnion, definition, no evidence levelUniondefinitionBiconditional, definition, no evidence levelBiconditionaldefinitionTruth table, concept, no evidence levelTruth tableconceptUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionSubset, definition, no evidence levelSubsetdefinitionPropositional logic, concept, no evidence levelPropositional logicconceptUniversal set, definition, no evidence levelUniversal setdefinitionTautology, definition, no evidence levelTautologydefinitionComplement, definition, no evidence levelComplementdefinitionLogical equivalence, definition, no evidence levelLogical equivalencedefinitionDe Morgan's laws, statement, no evidence levelDe Morgan's lawsstatementDe Morgan's laws for sets, statement, no evidence levelDe Morgan's laws for …statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Element definition
  2. Proposition concept
  3. Set definition
  4. Conjunction definition
  5. Disjunction definition
  6. Implication definition
  7. Negation definition
  8. Predicate definition
  9. Intersection definition
  10. Union definition
  11. Biconditional definition
  12. Truth table concept
  13. Universal quantifier definition
  14. Subset definition
  15. Propositional logic concept
  16. Universal set definition
  17. Tautology definition
  18. Complement definition
  19. Logical equivalence definition
  20. De Morgan's laws statement
  21. De Morgan's laws for sets statement

Where this leads

5 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/De_Morgan's_laws, lead section
About this page
Tag0VK0W4D5Y5
URIm2://0VK0W4D5Y5
Kindstatement, theorem
WritingW0 stub
MSC03E20
StatusThis copy of the site has no build data. Run m2 status 0VK0W4D5Y5.
UsesComplement, Union, Intersection, De Morgan's laws

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by