Antisymmetry 2026-10-31
The property of a binary relation that opposite directed relationships between two elements can hold only when those elements are equal. It does not require every pair to be comparable and does not prohibit a longer directed cycle whose reverse edges are initially absent. Taking reflexive transitive closure can therefore destroy this property.
Barber paradox 2026-10-31
For a binary relation , no object can satisfy for every . Putting would give for . The forward direction derives by a negation introduction subproof assuming ; the reverse direction then gives , a contradiction. Thus this argument even avoids needing the law of excluded middle. The familiar interpretation reads as “ shaves ”; the logical obstruction is self-application rather than a physical peculiarity of shaving.
Binary relations with no empty row or column Created 2026-10-14 Updated 2026-10-25
Represent a binary relation on an -element finite set by its zero-one incidence matrix. If no column may be empty, each column has choices. Apply the inclusion-exclusion principle to empty rows: fixing empty rows leaves allowed matrices. Summing over those row sets with alternating signs yields the displayed count.
There are at most continuum many binary relations on a countable set. For the matching lower bound, order the blocks by their index and independently choose the internal comparison in each block. A binary sequence determines those choices and distinct sequences give distinct labelled total orders. The resulting order types can all coincide; the count concerns relations, not isomorphism classes.
Category of relations (sets) 2026-10-14
The category of relations on sets has sets as objects and binary relations as morphisms. Relational composition declares when some intermediate satisfies both component relations; the identity is the diagonal relation.
Computational problem Created 2026-09-24 Updated 2026-11-05
A computational problem specifies what counts as a valid output for each permitted input. A binary relation can express this requirement: means that is a valid answer to . The computational problem is the specification; an algorithm is a proposed way to satisfy it.
For example, given an array and value , under the promise that occurs, a search problem can request any index with . Repeated values may give several valid outputs. The related decision problem only asks whether an occurrence exists and requires a yes-or-no answer. Stating the encoding, permitted instances and required answer prevents these tasks from being confused when comparing running time or verification costs.
Converse relation 2026-10-31
Reversing every ordered pair of a binary relation. Swapping the two components is its own inverse and therefore preserves distinctness of a representation by a list of distinct pairs.
Counting complexity Created 2026-09-28 Updated 2026-11-05
Counting complexity studies the computational resources needed to count solutions. For a polynomial time decidable binary relation and a polynomial , a standard counting function isThe complexity class consists of these functions, equivalently the numbers of accepting computations of Nondeterministic Turing machines running in polynomial time. The witness encoding matters: counting computation paths and counting distinct outputs can give different answers.
For the propositional formula , the satisfying Boolean valuations are , and , so the answer is three. The associated decision problem asks only whether that count is positive. For a zero-one matrix, the permanent of a matrix counts perfect matchings in a bipartite graph. Testing whether any such perfect matching exists admits a polynomial-time algorithm, while counting them is -complete under polynomial-time Turing reductions.[ref]
Equivalence closure 2026-10-14
The equivalence closure of a binary relation is the least equivalence relation containing it. Add diagonal and reversed pairs, then connect points by finite chains. Constant chains prove reflexivity, reversed chains prove symmetry, and concatenated chains prove transitivity. Any equivalence relation extending contains every such chain endpoint by induction.
Equivalence relation Created 2026-09-24 Updated 2026-10-14
An equivalence relation says which set elements should count as the same for a particular purpose. In modular arithmetic, for example, distinct integers with the same remainder are equivalent. The relation gathers interchangeable set elements into equivalence classes; the quotient set then treats each whole equivalence class as one object.
Formally, an equivalence relation on a set is a binary relation , written , satisfying three conditions for all :These conditions make the equivalence classes a partition of a set: each set element belongs to exactly one class. [ref]
- Reflexivity: .
- Symmetric relation: implies .
- Transitivity: and imply .
https://www.jirka.org/ra/html/sec_basicset.html. Jiří Lebl, Basic Analysis, §0.3.4, Definitions 0.3.21 and 0.3.23 and Proposition 0.3.24
For a worked example, take the finite set and restrict integer congruence modulo three to :Reflexivity follows because . The symmetric relation property follows by changing the sign of a difference, and transitivity follows by adding and : divisibility by three is preserved in both steps. Thus and force . The three equivalence classes are , and . Their members alternate along the number line; membership in an equivalence class need not mean being close together.
The transitivity requirement rules out a tempting alternative. On , define nearness by the absolute value condition . This binary relation is reflexive and symmetric, but is near and is near while is not near . Its neighborhoods , and overlap without being equal. They are not equivalence classes or a partition of a set.
Euclidean relation 2026-10-31
A binary relation is right Euclidean when any two successors of the same element are related in the indicated order. A reflexive relation with this property is an equivalence relation: reflexivity gives symmetry, and symmetry followed by the Euclidean property gives transitivity. Without reflexivity, even the empty binary relation is Euclidean.
Finitary relation 2026-10-31
A subset of a finite Cartesian product specifies which tuples of elements satisfy a relation. A first-order structure interprets a relation symbol with argument places as such a subset of the -fold Cartesian product of its domain of a first-order structure. For two argument places this is a binary relation; for three, the set of triples satisfying is an example involving addition.
Happens-before 2026-10-14
An ordering binary relation used by a memory model to constrain observation of shared data. For the mutex example, T1's write precedes its release, that release synchronizes with T2's successful acquisition, and that acquisition precedes T2's read. Together these steps order the write before the read. Wall-clock timing alone does not establish happens-before.[ref]
Irreflexive relation Created 2026-10-25 Updated 2026-10-31
A binary relation is irreflexive when no element is related to itself. An irreflexive relation that is also a transitive relation is a strict partial order. Transitivity then excludes every finite directed cycle, since a cycle would imply at its starting element.
Next-configuration relation 2026-10-31
For a Turing machine, the one-step binary relation between Turing machine configurations specified by its Turing machine instructions. Its reflexive transitive closure describes any finite number of computation steps, including zero.
Order theory Created 2026-10-20 Updated 2026-11-05
Order theory studies binary relations describing precedence or comparison. A partial order is reflexive, antisymmetric and transitive; a total order additionally compares every pair. A partially ordered set records a set together with its chosen order.
Set inclusion gives a partial order on the subsets of . The subsets and are incomparable, while their least upper bound is their union. The usual order on the real numbers is total. Distinguishing a maximum from a merely maximal element is useful whenever incomparable alternatives occur, including dependencies, divisibility and optimization.
Past exam of the logic and set theory course of the University of Oxford 2009 A 3 d ii Solution 2026-10-31
Neither constants alone nor functions alone gives the same uniform adequacy on all nonempty carriers. A one-element set has exactly one interpretation of each function symbol of any finite arity and of every constant symbol. In contrast it has two interpretations of a unary predicate: empty or full. Thus a fixed purely functional or constant-only language has only one structure on that singleton, and cannot encode both truth values of by a same-carrier truth-preserving translation with reconstruction. This is the singleton truth-preservation obstruction to expressive completeness, even when logical equality is available.
Constants alone also cannot represent general variable-dependent relations on larger infinite carriers: a fixed formula mentions only finitely many named elements, and its remaining equality tests do not encode an arbitrary binary relation. Functions offer more flexibility. On carriers with at least two elements, predicates can be encoded by characteristic functions taking two distinguished values, and constants can be represented by constant-valued unary functions if explicit constant symbols are forbidden. Such a construction can work after adding axioms for distinct truth markers, but those axioms exclude the singleton case. Enlarging the carrier or adding a Boolean sort is another possible encoding; it changes the same-carrier sense established in the preceding part and must not be silently identified with it.
Past exam of the mathematics course of the University of Cambridge 2003 ia Paper 4 2C Solution 2026-10-14
An equivalence relation on a set is a binary relation that is reflexive, symmetric and transitive: every satisfies ; implies ; and , imply . Each of these quantifiers ranges over the entire specified set. The separate entries below test these three properties.
Past exam of the mathematics course of the University of Cambridge 2003 ia Paper 4 8C Solution Created 2026-09-24 Updated 2026-10-14
For each of the arguments of a function , there are choices of image, independently. Thus there are functions. A binary relation is a subset of the ordered pairs in , giving relations.
Represent a binary relation by its incidence matrix, with row and column . Requiring some with means that column must be a nonempty subset of the possible rows. Each column therefore has choices, independently, givingrelations with no empty column.
To impose no empty row as well, apply the inclusion-exclusion principle within this already column-nonempty family. Let be the family whose row is empty. If a specified set of rows is empty, every column must be a nonempty subset of the remaining rows, giving possibilities. There are ways to choose those empty rows. Thus the number with neither an empty row nor an empty column isThis is the binary relations with no empty row or column count. It does not require symmetry or transitivity of the relation. If , there is one empty function and one empty relation, and all quantified nonempty-row/column requirements are vacuous; the formulas still hold with the combinatorial convention for an empty product.
Past exam of the mathematics course of the University of Cambridge 2006 ia Paper 4 5E ii Solution Created 2026-09-24 Updated 2026-10-14
A binary relation is transitive exactly when . If condition (iii) holds, associativity and monotonicity of composition of relations giveHence (iii) implies (ii). Conversely, the inclusions implyIf is a transitive relation, the right side lies in , which is condition (iii). Thus (ii) and (iii) are equivalent.
