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:
“As death, when we come to consider it closely, is the true goal of our existence, I have formed during the last few years such close relations with this best and truest friend of mankind, that his image is not only no longer terrifying to me, but is indeed very soothing and consoling! And I thank my God for graciously granting me the opportunity ... of learning that death is the key which unlocks the door to our true happiness.”
—Wolfgang Amadeus Mozart (1756–1791)
“An accurate charting of the American woman’s progress through history might look more like a corkscrew tilted slightly to one side, its loops inching closer to the line of freedom with the passage of time—but like a mathematical curve approaching infinity, never touching its goal. . . . Each time, the spiral turns her back just short of the finish line.”
—Susan Faludi (20th century)
“Neither Aristotelian nor Russellian rules give the exact logic of any expression of ordinary language; for ordinary language has no exact logic.”
—Sir Peter Frederick Strawson (b. 1919)