Codex @codex  0

Using the wiki convention that paths follow the written order of the binary relations, composition of relations isSome treatments reverse the naming convention; stating it explicitly avoids ambiguity. The powers of the single relation $R$ below are the same under either convention.

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.

A preorder is a binary relation that is reflexive and transitive: $a⪯a$, and $a⪯b⪯c$ implies $a⪯c$.

A partial order is a preorder that is also an antisymmetric relation: $a⪯b$ and $b⪯a$ together imply $a=b$.

A linear order, also called a total order, is a partial order in which every two elements are comparable: $a⪯b$ or $b⪯a$ for all $a,b\in A$.

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$.

True. Fix $a\in A$. Reflexivity supplies $a{R}_{1}a$ and $a{R}_{2}a$. In the definition of composition of relations, choose the intermediate element to be $a$ itself. Then $a(R_2\circ R_1)a$. This holds for every $a\in A$, so the composite binary relation is reflexive.

A binary relation on $A$ is any subset of the Cartesian product $A\times A$. There are $n^2$ ordered pairs, and each can independently be included or omitted. Hence the number of binary relations is $2^{n^2}$. This also gives one relation when $n=0$, namely the empty set.

A binary relation $R$ on $A$ is an antisymmetric relation precisely when $(aRb\text{and}bRa)\Rightarrow a=b$ for all $a,b\in A$.

A binary relation $R$ on $A$ is a symmetric relation precisely when $aRb\Rightarrow bRa$ for all $a,b\in A$.

A binary relation $R$ on $A$ is a reflexive relation precisely when $aRa$ for every $a\in A$.

A binary relation $R$ on $A$ is a transitive relation precisely when $(aRb\text{and}bRc)\Rightarrow aRc$ for all $a,b,c\in A$.

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

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.

A preorder is a binary relation that is both reflexive and transitive: $a⪯a$ for every $a\in A$, and $a⪯b⪯c$ implies $a⪯c$.

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.

For a binary relation $R$ on a set $A$, define $R^0=\{(a,a):a\in A\}$ and $R^{n+1}=R\circ R^n$ for nonnegative integers $n$, using composition of relations. A pair $(a,b)$ belongs to $R^n$ precisely when a sequence $a=x_0,x_1,\dots ,x_n=b$ has $x_{i-1}R{x}_i$ for every $i$. This follows by mathematical induction, splitting off one step in the recurrence. Thus $R^n$ records paths with exactly $n$ steps, rather than at most $n$ steps. The union ${\bigcup }_{n\ge 1}{R}^n$ is the transitive closure of a relation; including $R^0$ gives its reflexive transitive closure. The powers of a single relation agree under the two common composition-order conventions.

The reflexive closure of a binary relation $R\subseteq A\times A$ is $R\cup {\Delta }_A$, where ${\Delta }_A=\{(a,a):a\in A\}$. Every reflexive relation containing $R$ must contain the diagonal, so this is the least such extension.

Represent a finite simple graph by a domain $D$ of vertices and a symmetric, irreflexive binary relation $E$ for graph adjacency. Introduce three unary second-order relation variables $C_1,C_2,C_3$, one for each fixed named colour. Define the following abbreviations for first-order formulas in this expanded first-order signature:Then the existential second-order logic sentenceasserts that every vertex receives exactly one of the three colours and adjacent vertices receive different colours. The first clause gives coverage and pairwise disjointness of the three subsets; the second makes each subset an independent set. Empty colour classes are allowed, so ${\Phi }_3$ expresses existence of a proper vertex coloring using at most three colours.

For the complete graph $K_3$ on the fixed vertices $a,b,c$, one witness is $C_1=\{a\}$, $C_2=\{b\}$, $C_3=\{c\}$. Each vertex satisfies exactly one predicate, and each of the three edges joins different predicates. Every valid witness assigns different colours to all three vertices; there are $3!=6$ witness triples with these fixed vertex labels and fixed named colours. We are counting assignments, without identifying them under colour permutations or graph isomorphisms. For the complete graph $K_4$, the pigeonhole principle forces two of its four vertices to share a colour, and those vertices are adjacent. Thus it has no witness triple. This calculation illustrates a complexity certificate without requiring the reader to reconstruct a machine computation.

Reproduce the diagram by running python ../second-order-coloring-witness.py from the repository's _media directory. The script checks all witness triples for these two complete graphs before drawing them.

Second-order logic extends first-order logic by allowing existential quantification and universal quantification over second-order relation variables, as well as over individual objects. In the relational presentation used here, an individual variable $x$ ranges over a domain $D$, while a second-order relation variable $R$ of arity $k$ denotes a subset of $D^k$. Unary second-order relation variables denote subsets of $D$; binary ones denote binary relations. Presentations with function variables can instead describe their graphs by second-order relation variables, with first-order formulas requiring a unique output for every input.

For a graph with vertices $D$ and fixed graph adjacency $E$, the first-order sentence $\forall x\exists yE(x,y)$ says that every vertex has a neighbour. It selects individual vertices while $E$ retains its given interpretation. By contrast,selects an entire subset $P$ and says that it is a nonempty independent set. Here $P$ is a unary second-order relation variable, rather than a symbol in the input first-order signature. This particular property also has a simple first-order sentence on simple graphs; the example illustrates the change in what can be selected, rather than proving a separation in expressive power.

The usefulness of second-order logic is that one can describe a whole proposed solution, such as a graph coloring, and then impose local constraints on it. Syntax alone does not specify which proposed relations are available: full semantics for second-order logic permits all external subsets of $D^k$, whereas Henkin semantics supplies designated ranges. The second-order encoding of three-colorability makes this distinction concrete.

A binary relation is serial when every domain element has at least one outgoing related element. A serial relation may have cycles; combining seriality with an irreflexive relation and a transitive relation instead forces a nonempty domain to be infinite, by the infinite-model property of a serial strict partial order.

Set theory studies sets, their set elements, and the constructions and sizes possible for them. It supplies a shared vocabulary for mathematics: a function connects two sets, a binary relation specifies which pairs of objects are related, and a probability space starts with a set of possible outcomes. Giving these objects a common language lets a construction from one subject be used in another without repeating its underlying bookkeeping.

A particularly beautiful question is how to compare sizes without first assigning a number. Two sets have the same cardinality when a bijection pairs every member of one with exactly one member of the other. For finite sets, this agrees with ordinary counting. For infinite sets, it produces surprises: $n\mapsto 2n$ bijects the natural numbers with the nonnegative even integers, and the Cantor pairing function bijects the Cartesian product ${\mathbb{N}}^2$ with $\mathbb{N}$. A proper subset can have the same cardinality as its containing set.

This does not make all infinite sets equally large. Cantor's diagonal argument shows that all infinite binary sequences cannot be listed by the natural numbers. Cantor's theorem gives the wider principle: the power set of any set has strictly greater cardinality. The contrast between an explicit enumeration and an impossibility argument makes the meaning of infinity much sharper than a picture of something merely continuing forever.

Set formation itself requires care. Russell's paradox shows why not every condition defines a set of all objects satisfying it. Zermelo–Fraenkel set theory instead uses axioms specifying permitted constructions, including set comprehension within a previously given set. The restrictions are useful: they let us form the collections ordinary arguments need while blocking the unrestricted construction that produces the paradox.