Math 2.0

Mathematical logic and foundations Theorem

Correspondence between equivalence relations and partitions

Builds on Equivalence classes form a partitionBijective function

Statement

Let AA be a set. Send each equivalence relation ∼\sim on AA to its set of equivalence classes A/∼A/{\sim}. This map is a bijection from the set of equivalence relations on AA to the set of partitions of AA. Its inverse sends a partition PP to the relation ∼P\sim_P with a∼Pba \sim_P b when aa and bb are in the same block of PP.

Remarks

The relation ∼P\sim_P is an equivalence relation, and its classes are the blocks of PP. A smaller equivalence relation, one that relates fewer pairs, gives a finer partition. The number of partitions of a set with nn elements is the Bell number BnB_n. For example, B3=5B_3 = 5.

Reading path

To understand this page from the ground up, read these 34 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 levelImplicationdefinitionPredicate, definition, no evidence levelPredicatedefinitionEmpty set, object, no evidence levelEmpty setobjectFamily of sets, definition, no evidence levelFamily of setsdefinitionOrdered pair, definition, no evidence levelOrdered pairdefinitionIntersection, definition, no evidence levelIntersectiondefinitionUnion, definition, no evidence levelUniondefinitionSet-builder notation, concept, no evidence levelSet-builder notationconceptExistential quantifier, definition, no evidence levelExistential quantifierdefinitionUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionDisjoint sets, definition, no evidence levelDisjoint setsdefinitionCartesian product, definition, no evidence levelCartesian productdefinitionSubset, definition, no evidence levelSubsetdefinitionUnion of a family of sets, definition, no evidence levelUnion of a family of …definitionUniqueness quantifier, definition, no evidence levelUniqueness quantifierdefinitionBinary relation, definition, no evidence levelBinary relationdefinitionPartition of a set, definition, no evidence levelPartition of a setdefinitionReflexive relation, definition, no evidence levelReflexive relationdefinitionSymmetric relation, definition, no evidence levelSymmetric relationdefinitionTransitive relation, definition, no evidence levelTransitive relationdefinitionFunction, definition, no evidence levelFunctiondefinitionEquivalence relation, definition, no evidence levelEquivalence relationdefinitionCodomain, definition, no evidence levelCodomaindefinitionInjective function, definition, no evidence levelInjective functiondefinitionSurjective function, definition, no evidence levelSurjective functiondefinitionEquivalence class, definition, no evidence levelEquivalence classdefinitionBijective function, definition, no evidence levelBijective functiondefinitionEquivalence classes form a partition, statement, no evidence levelEquivalence classes f…statementCorrespondence between equivalence relations and partitions, statement, no evidence levelCorrespondence betwee…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. Predicate definition
  8. Empty set object
  9. Family of sets definition
  10. Ordered pair definition
  11. Intersection definition
  12. Union definition
  13. Set-builder notation concept
  14. Existential quantifier definition
  15. Universal quantifier definition
  16. Disjoint sets definition
  17. Cartesian product definition
  18. Subset definition
  19. Union of a family of sets definition
  20. Uniqueness quantifier definition
  21. Binary relation definition
  22. Partition of a set definition
  23. Reflexive relation definition
  24. Symmetric relation definition
  25. Transitive relation definition
  26. Function definition
  27. Equivalence relation definition
  28. Codomain definition
  29. Injective function definition
  30. Surjective function definition
  31. Equivalence class definition
  32. Bijective function definition
  33. Equivalence classes form a partition statement
  34. Correspondence between equivalence relations and partitions statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Partition_of_a_set, Partitions and equivalence relations
About this page
Tag074482Q7CD
URIm2://074482Q7CD
Aliasesfundamental-theorem-of-equivalence-relations
Kindstatement, theorem
WritingW0 stub
MSC03E20
StatusThis copy of the site has no build data. Run m2 status 074482Q7CD.
UsesEquivalence classes form a partition, Bijective function

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

No page links to this page yet.