Equivalence Relations and Mathematical Logic
Equivalence relations are a ready source of examples or counterexamples. For example, an equivalence relation with exactly two infinite equivalence classes is an easy example of a theory which is ω-categorical, but not categorical for any larger cardinal number.
An implication of model theory is that the properties defining a relation can be proved independent of each other (and hence necessary parts of the definition) if and only if, for each property, examples can be found of relations not satisfying the given property while satisfying all the other properties. Hence the three defining properties of equivalence relations can be proved mutually independent by the following three examples:
- Reflexive and transitive: The relation ≤ on N. Or any preorder;
- Symmetric and transitive: The relation R on N, defined as aRb ↔ ab ≠ 0. Or any partial equivalence relation;
- Reflexive and symmetric: The relation R on Z, defined as aRb ↔ "a − b is divisible by at least one of 2 or 3." Or any dependency relation.
Properties definable in first-order logic that an equivalence relation may or may not possess include:
- The number of equivalence classes is finite or infinite;
- The number of equivalence classes equals the (finite) natural number n;
- All equivalence classes have infinite cardinality;
- The number of elements in each equivalence class is the natural number n.
Read more about this topic: Equivalence Relation
Famous quotes containing the words relations, mathematical and/or logic:
“If one could be friendly with women, what a pleasure—the relationship so secret and private compared with relations with men. Why not write about it truthfully?”
—Virginia Woolf (1882–1941)
“As we speak of poetical beauty, so ought we to speak of mathematical beauty and medical beauty. But we do not do so; and that reason is that we know well what is the object of mathematics, and that it consists in proofs, and what is the object of medicine, and that it consists in healing. But we do not know in what grace consists, which is the object of poetry.”
—Blaise Pascal (1623–1662)
“Our argument ... will result, not upon logic by itself—though without logic we should never have got to this point—but upon the fortunate contingent fact that people who would take this logically possible view, after they had really imagined themselves in the other man’s position, are extremely rare.”
—Richard M. Hare (b. 1919)