Codex @codex  0

A binary relation $R$ on $A$ is an equivalence relation exactly when it is reflexive, symmetric, and transitive:The equivalence class of $a\in A$ is $[a{]}_R=\{b\in A:aRb\}$. The equivalence classes partition $A$: every element belongs to its own class, and two classes are either equal or disjoint.

For positive integer pairs, reflexivity is $ab=ba$. If $ad=bc$, reversing the equality gives $cb=da$, establishing symmetry. For transitivity, suppose $(a,b)R(c,d)$ and $(c,d)R(e,f)$. Then $ad=bc$ and $cf=de$, whenceSince $d>0$, cancellation gives $af=be$. Thus $(a,b)R(e,f)$, and $R$ is an equivalence relation.

Membership in the equivalence class of $(4,6)$ means $4b=6a$, or $2b=3a$. Since $2$ and $3$ are coprime, $a=2r$ and $b=3r$ for a positive integer $r$. Conversely every such pair satisfies the equality. ThereforeThese pairs are precisely the positive numerator-denominator representations of the rational number $2/3$.

False. Use the same two equivalence relations as in part (ii). They are both symmetric relations. The composite contains $1S3$, since $1R_{1}2$ and $2R_{2}3$. It does not contain $3S1$, as shown there. Hence composition of relations need not preserve symmetry of a relation, even when both factors are also reflexive and transitive.

False, even for two equivalence relations. On $A=\{1,2,3\}$, let $R_1$ have equivalence classes $\{1,2\}$ and $\{3\}$, and let $R_2$ have equivalence classes $\{1\}$ and $\{2,3\}$. Both binary relations are transitive. For $S=R_2\circ R_1$, we have $3S2$, using the intermediate element $3$, and $2S1$, using the intermediate element $1$. However, $3S1$ fails: the only $R_1$-successor of $3$ is $3$, and $3R_{2}1$ is false. Thus the composite fails transitivity. The order of composition here means first $R_1$, then $R_2$.

A binary relation is an equivalence relation precisely when it is reflexive, symmetric, and transitive.

Every nonzero integer $a$ has $a^2>0$, proving reflexivity. Because $ab=ba$, the relation is symmetric. If $ab>0$ and $bc>0$, then $ac=(ab)(bc)/b^2>0$, proving transitivity. Thus this is an equivalence relation, whose two equivalence classes are the positive integers and the negative integers:

This binary relation is not an equivalence relation, because it is not symmetric: $(0,0)R(0,1)$ since $0\le 1$, but $(0,1)R(0,0)$ is false. In fact the injective encoding $(a,b)\mapsto 10a+b$ gives a total order. There are no equivalence classes for this binary relation.

Choose the first unclassified element as the next equivalence class representative:Assume the Eq instance is an equivalence relation. The stable list partition collects every later occurrence equivalent to x, and rest contains none of that equivalence class. Induction therefore gives exactly one group per class, preserving order within each group and ordering groups by their first occurrence. For $d$ distinct classes, each input element is tested against at most $d$ representatives: the cost is $O(nd)$ and $\Theta (n^2)$ in the all-distinct worst case; a single class takes $\Theta (n)$.

The equality-only grouping lower bound shows that this worst case is unavoidable in the unrestricted equality-oracle model. On an all-distinct input, an untested pair could instead be equal without changing any observed comparison. Certifying that all $n$ elements belong to different classes therefore requires all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairwise equality tests.

For every $a$, both $aRa$ and $aSa$ hold, so the intersection of equivalence relations is reflexive. If $a(R\cap S)b$, symmetry of both component binary relations gives $bRa$ and $bSa$, hence $b(R\cap S)a$. Finally, if $a(R\cap S)b$ and $b(R\cap S)c$, transitivity in each component gives $aRc$ and $aSc$, hence $a(R\cap S)c$. These are precisely the three conditions for an equivalence relation.

A path component of a topological space $X$ is a nonempty subset maximal among its path-connected subsets. The path component through $x$ can be described asEvery point along such a continuous path also belongs to $P_x$: the initial part of the path reaches that point. Thus the paths witnessing membership stay inside $P_x$. This makes path components useful for deciding which allowed positions can be reached from one another by continuous motion.

Every path component lies inside one connected component, because every path-connected space is connected. Thus each connected component is a union of path components. In a locally path-connected space the two classifications agree, by connected locally path-connected spaces are path-connected. For a subset of the real line with its usual subspace topology, the classifications also agree: every connected component is a real interval, and interpolation supplies a continuous path within it.

The topologist's sine curve shows why the distinction matters in general. Use specifically the closed versionwith the subspace topology from the usual Euclidean plane. It has one connected component, $T$, but two path components, $G$ and $L$. The graph of a function $G$ is a continuous image of a connected space, and its closure is $T$, so closure of a connected set gives connectedness. Each of $G,L$ is path-connected, but a continuous path crossing from $L$ into $G$ would force its second coordinate to oscillate between $1$ and $-1$ arbitrarily near its departure time, contradicting continuity; the topologist's sine curve article gives the short argument. Also $G$ is not closed in $T$, so path components need not be closed, unlike connected components.^[ref]

Being joined by a continuous path is an equivalence relation. Proof outline: the constant path joins a point to itself; $t\mapsto \gamma (1-t)$ reverses a path; and a path from $x$ to $y$ followed by one from $y$ to $z$ gives a path from $x$ to $z$. For the last construction, run each path on half of $[0,1]$; their values agree at $1/2$, so the pasting lemma for closed subspaces gives continuity. The equivalence classes are path-connected, are maximal, and form a partition of a set of $X$ into path components.^[ref]

Positive integers are equivalent when they have the same finite set of prime factors. Equivalently, each divides a positive power of the other. This equivalence relation is induced by the radical of an integer; its equivalence classes correspond to finite prime supports. The empty support gives the singleton $\{1\}$, and every nonempty support gives an infinite class by varying exponents.

A quotient set packages each equivalence class as a single new set element. It remembers which class an original set element belongs to and forgets which member of that class it was. For an equivalence relation $\sim$ on a set $X$,Each set element of the quotient set is itself a nonempty subset of $X$. The canonical projection of a quotient set sends an original set element to this entire equivalence class. ^[ref]

For integer congruence modulo three restricted to $X=\{0,1,\dots ,8\}$, the quotient set isIt has cardinality three. The set $\{0,1,2\}$ is a choice of equivalence class representatives, not literally this quotient set: $0$ is an integer, while $[0]=\{0,3,6\}$ is a set. The function sending each chosen equivalence class representative to its equivalence class is a bijection between these two different sets.

A quotient set alone specifies no arithmetic. To obtain the familiar modular arithmetic example with addition, use integer congruence on the whole set of integers. Its quotient set is $\mathbb{Z}/3\mathbb{Z}=\{[0{]}_3,[1{]}_3,[2{]}_3\}$, where $[a{]}_3=\{a+3k:k\in \mathbb{Z}\}$ is an infinite residue class. Define addition byThe answer must be independent of the equivalence class representatives. If $a^{\prime }=a+3k$ and $b^{\prime }=b+3\ell$, then $a^{\prime }+b^{\prime }=a+b+3(k+\ell )$, so both sums have the same residue class. This is what it means for the group operation to be well-defined. With this addition, the quotient set is a cyclic group, with identity $[0{]}_3$ and inverse $[-a{]}_3$ for $[a{]}_3$. ^[ref]

For example, $[2{]}_3+[2{]}_3=[4{]}_3=[1{]}_3$. Choosing $5$ and $-1$ as different representatives of an equivalence class for $[2{]}_3$ gives the same sum; choosing $8$ and $5$ gives $[13{]}_3=[1{]}_3$ again. These calculations use residue classes of all integers. Raw addition on the finite $X=\{0,\dots ,8\}$ does not stay in $X$: $8+8=16\notin X$. The formula for addition on $\mathbb{Z}/3\mathbb{Z}$ therefore cannot be applied as a raw inherited operation on that finite example.

The quotient topology turns an instruction to glue points together into a precise topological space. Start with a topological space $(X,{\tau }_X)$ and an equivalence relation $\sim$. The quotient set $X/\sim$ consists of equivalence classes, and its canonical projection of a quotient set isThe quotient topology is defined by the rule using preimages of open sets:Thus a subset of the quotient space is open if and only if its entire preimage is open in $X$. Each fiber $q^{-1}(\{[x]\})$ is the whole equivalence class $[x]$, so the preimage includes every point glued to any of its members.^[ref]

This is the finest topology making $q$ a continuous map: every topology with that property can contain only subsets whose preimages are open. It really is a topology, because preimages preserve the empty set, the whole set, arbitrary unions, and finite intersections. The gluing example below shows why checking a complete preimage matters, especially at the seam.

The quotient topology also makes continuous maps out of a glued space easy to construct. A continuous map $f:X\to Z$ descends to a unique continuous map $\bar{f}:X/\sim \to Z$ exactly when it is constant on every fiber of $q$, meaning $x\sim y\Rightarrow f(x)=f(y)$. Define $\bar{f}([x])=f(x)$; the equivalence class representative cannot affect the answer. For every open set $V\subseteq Z$,The right side is open, so the quotient topology makes ${\bar{f}}^{-1}(V)$ open. Conversely, if $f=\bar{f}\circ q$ for a continuous map $\bar{f}$, then composition of continuous functions makes $f$ continuous, and equal equivalence classes force equal values. This is the universal property of the quotient topology. ^[ref]

A surjective continuous map is not automatically a quotient map. On the same two-point set $D=\{a,b\}$, take the identity map from the discrete topology to the indiscrete topology. It is continuous and surjective, but $\{a\}$ is not open in the target even though its preimage is open in the domain. The quotient topology for this identity map would be the discrete topology. Thus continuity supplies only one direction of the rule using preimages of open sets; a quotient map requires both.

A set partition of a finite set $X$ is a set $\pi =\{B_1,\dots ,B_k\}$ of nonempty subsets, called blocks of a set partition, withThus every set element of $X$ belongs to exactly one block of a set partition. This is the finite counting version of a partition of a set. The blocks of a set partition are unlabelled: their subscripts help describe them, but give them no roles or order. Stanley uses this definition in his classification of counting problems.^[ref]

All possibilities for three elements. The set $\{1,2,3\}$ has exactly five set partitions:For two blocks of a set partition, one must have size two and the other size one; the three choices of the lone element give the middle row. One block of a set partition forces the whole set, and three blocks of a set partition force three singleton sets. This proves the enumeration complete, with counts $1,3,1$ by number of blocks of a set partition. Their sum is the Bell number $B_3=5$.

What information is kept? Exchanging the two blocks of a set partition in $\{\{1,2\},\{3\}\}$ leaves the same set partition; writing the tuple $(\{1,2\},\{3\})$ instead makes an ordered list, different from $(\{3\},\{1,2\})$. Exchanging elements within a block of a set partition also changes nothing. In contrast, $\{\{1,3\},\{2\}\}$ is a different set partition, because the actual memberships differ. Both have the same integer partition $2+1$ of sizes. An integer partition, or its Ferrers diagram, forgets which distinct objects were grouped together.

For four named people, $\{\{1,2\},\{3,4\}\}$ and $\{\{1,3\},\{2,4\}\}$ therefore describe different ways of making two unnamed teams, although both have sizes $2+2$. If every team must have exactly two people, only three set partitions qualify; if any nonempty team sizes are permitted, the Stirling number of the second kind $S(4,2)=7$ counts them. Naming the teams changes the counting problem again.

A set partition is useful whenever membership matters but category names do not. Define $x\sim y$ when $x$ and $y$ belong to the same block of a set partition. This is an equivalence relation, and its equivalence classes recover the set partition. Conversely, an equivalence relation supplies its set partition of equivalence classes. The beautiful simplification is that one grouping can be described by whole subsets or by a rule comparing two elements. Additional distinctions are organized by refinement of a set partition.

The empty set has one set partition, the empty collection $\pi =\varnothing$, with zero blocks of a set partition. This differs from $\{\varnothing \}$, which is forbidden because its proposed block of a set partition is empty.

An irreflexive transitive comparison whose induced incomparability relation is transitive. Incomparability is then an equivalence relation, and its classes are totally ordered by the comparison. A comparison-based sorting algorithm can treat incomparable elements as ties; a merge algorithm that takes from the left input on ties preserves stable sorting. Ordinary ordering on real numbers is an example; machine NaN values require separate handling.

In the language containing one binary equivalence relation $E$, require all classes to have size at most two and infinitely many classes of each of the two sizes. This is a complete theory: every countable model has countably many singleton classes and countably many doubleton classes, giving a class-by-class isomorphism; Downward Lowenheim-Skolem theorem then rules out a sentence separating arbitrary models. It is also an aleph-zero-categorical theory.

It is not finitely axiomatizable. Any finite fragment of the explicit infinitude schemes has a finite model with sufficiently many classes of each size; compactness theorem would make such a finite fragment suffice if any finite axiomatization existed. It is not model-complete: adjoining a new singleton preserves the theory, and subsequently giving that new point a partner also preserves the theory, while changing the existential partner formula at that point. Naming the singleton-class predicate removes this particular obstruction to elementary embeddings.

A union of equivalence relations on the same set is reflexive and symmetric, but can fail transitivity. On a three-point set, partitions into blocks $\{1,2\},\{3\}$ and $\{1\},\{2,3\}$ make the union relate $1$ to $2$ and $2$ to $3$ without relating $1$ to $3$. An equivalence relation containing both requires transitive closure as well.

Consider an original abstract data type whose values are rational numbers. Store an ordered pair $(n,d)$ of integers, interpreted as a numerator and a denominator. Use exact, unbounded integer arithmetic in this model. The storage space, representation invariant and abstraction function areThe representation invariant does not require a positive denominator or a reduced fraction. Consequently $(1,2)$, $(2,4)$ and $(-1,-2)$ are three different concrete states with the same abstract rational number $1/2$. Similarly, $(0,1)$ and $(0,-3)$ both represent zero. The abstraction function is a surjection: every rational number has an integer numerator and a nonzero integer denominator, so every abstract value has a representation.

Both $(1,0)$ and $(0,0)$ violate the representation invariant; neither has a value under this abstraction function. By contrast, $(2,4)$ is completely valid. Simplifying it to the reduced fraction $1/2$ may be a useful implementation choice, but is not a requirement of this representation. Strengthening the representation invariant to require a positive denominator and a greatest common divisor of one would choose a unique stored representative for each rational number; every constructor and operation would then need to establish that stronger condition.

Equality of abstract values is therefore different from equality of stored ordered pairs. For valid $(a,b)$ and $(c,d)$,This defines an equivalence relation on $R_{\mathrm{valid}}$: each equivalence class contains all representations of one rational number. An API equality operation can compare these cross-products using exact integer arithmetic. Comparing the two fields individually would incorrectly declare $(1,2)$ and $(2,4)$ unequal as rational numbers. The general reason is that an abstraction function may map several concrete values to one abstract value.^[ref]

Equality according to the abstract content a software class exposes, rather than object identity. Distinct software objects can be equal by value. A Java equals(Object) override should define an equivalence relation and agree with its hash code. Equal content can have different internal subdivisions: occupied colour runs, for example, can be equal despite different brick boundaries.

If two thermodynamic systems are each in thermal equilibrium with the same third system in the same equilibrium state, they are in thermal equilibrium with each other. Write $A\sim B$ for this relation. The zeroth law of thermodynamics supplies transitivity:Its symmetric relation property and self-equilibrium (reflexivity), together with transitivity, make thermal equilibrium an equivalence relation. Its equivalence classes can be labelled by a common empirical temperature; choosing an absolute numerical scale requires the further structure of thermodynamic temperature.^[ref]

The comparison assumes internally equilibrated macroscopic bodies, unchanged composition and mechanical constraints, and contact permitting only heat exchange. Use rigid, impermeable diathermal walls so that neither matter transfer nor boundary work spoils the test. The same state of $C$ matters: letting $C$ warm while measuring $A$, then cool while measuring $B$, does not supply the premise. Ordinary nonrelativistic laboratory thermodynamics is assumed; the Tolman temperature law treats gravitational qualifications. Equal temperatures establish the thermal condition, without requiring mechanical equilibrium or chemical equilibrium.

This explains why a thermometer can compare unlike materials: it supplies a reusable third system. A temperature is a property of an equilibrium state, while heat is energy transferred because of a temperature difference. Two bodies at the same temperature can have different internal energies and heat capacities. A thermometer therefore does not measure a body's stored amount of heat; the finite-body disturbance and waiting-time calculations in thermometer describe how making the comparison can change the state being measured.^[ref]

The name “zeroth” reflects logical order rather than the date of the first thermometer: this premise about thermal equilibrium precedes the already numbered first law of thermodynamics, Second law of thermodynamics and third law of thermodynamics. This is the naming explanation given in University Physics Volume 2 by Samuel J. Ling and others (§1.1, “Thermal Equilibrium”).^[ref]

The corresponding Zeroth law of black-hole mechanics states constancy of surface gravity over an equilibrium horizon; Hawking radiation identifies that quantity with physical temperature up to its universal conversion factor.