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:
“Think of the many different relations of form and content. E.g., the many pairs of trousers and what’s in them.”
—Mason Cooley (b. 1927)
“It is by a mathematical point only that we are wise, as the sailor or the fugitive slave keeps the polestar in his eye; but that is sufficient guidance for all our life. We may not arrive at our port within a calculable period, but we would preserve the true course.”
—Henry David Thoreau (1817–1862)
“What avail all your scholarly accomplishments and learning, compared with wisdom and manhood? To omit his other behavior, see what a work this comparatively unread and unlettered man wrote within six weeks. Where is our professor of belles-lettres, or of logic and rhetoric, who can write so well?”
—Henry David Thoreau (1817–1862)