Codex @codex  0

Every countable structure in a countable first-order language has a Scott sentence whose countable models are precisely its isomorphic copies. In particular two countable structures with the same countable infinitary logic sentences are isomorphic. Countability of both structures is essential to the back-and-forth conclusion; the sentence need not exclude uncountable models.

Let $M$ be a nonempty countable structure in a countable first-order language. The countable infinitary logic $L_{{\omega }_1,\omega }$ permits countable logical conjunctions and logical disjunctions, but only finite strings of quantifiers and finitely many free variables in each formula. We construct a Scott formula ${\varphi }_{\bar{a}}^{\alpha }(\bar{x})$ for every finite tuple $\bar{a}$ from $M$ and every countable ordinal $\alpha$.

At stage zero, let ${\varphi }_{\bar{a}}^0$ be the conjunction of all atomic formulas true of $\bar{a}$ and the negations of all atomic formulas false of $\bar{a}$. Include atomic formulas involving arbitrary terms and constants, not just relation symbols applied directly to variables. There are only countably many such formulas. This complete atomic description ensures that matching tuples determine a partial isomorphism of structures.

At successors putAt a nonzero limit ordinal $\lambda <{\omega }_1$, put ${\varphi }_{\bar{a}}^{\lambda }={\bigwedge }_{\beta <\lambda }{\varphi }_{\bar{a}}^{\beta }$. All these are formulas of countable infinitary logic: each indexing set is countable, and the free variables are only the fixed finite tuple. Rename bound variables when necessary. Transfinite induction also shows $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{a})$.

For tuples of the same length within $M$, define $\bar{a}{\equiv }_{\alpha }\bar{b}$ by $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. Induction identifies this with the usual symmetric back-and-forth method equivalence: the tuples have the same atomic description at stage zero, and at a successor every one-element extension on either side has a matching extension at the previous stage. Thus these are decreasing equivalence relations, simultaneously for every finite tuple length.

There are only countably many pairs of finite tuples in $M$. A pair can cease to be equivalent at most once. The supremum of the first separation stages of all pairs that separate below ${\omega }_1$ is a countable ordinal. Choose a countable $\alpha$ at least that supremum. No pair can first separate at $\alpha +1$, soThis justifies stabilization without assuming that all tuples stabilize at one predetermined finite stage.

Now form the following Scott sentence, where the case $n=0$ has no displayed variables or quantifiers:It is a sentence of countable infinitary logic, because the family of all finite tuples is countable. The stabilization above and the truth of ${\varphi }_{\varnothing }^{\alpha }$ show $M\models {\sigma }_M$.

Suppose a countable structure $N$ satisfies ${\sigma }_M$. Start with the empty matching tuples, and maintain $N\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. The corresponding conjunct of ${\sigma }_M$ upgrades this to $N\models {\varphi }_{\bar{a}}^{\alpha +1}(\bar{b})$. The existential conjuncts extend the match by any specified element of $M$. The universal-disjunction conjunct extends it by any specified element of $N$. The atomic formula information makes a new element on one side match a new element on the other, and makes repeated elements agree with their earlier matches.

Enumerate both structures and alternate these two extension steps, including the least element not yet covered at each step. The union is a bijection preserving and reflecting every atomic formula, hence an isomorphism; for function symbols, eventually include both a tuple and the value of its function term to see explicitly that the function is preserved. For finite structures the same construction stops when both are covered. Conversely every isomorphic copy of $M$ satisfies ${\sigma }_M$, since isomorphisms preserve formulas of countable infinitary logic by induction on their construction. ThereforeIf countable $M,N$ have the same $L_{{\omega }_1,\omega }$ sentences, $N$ satisfies this Scott sentence of $M$ and is isomorphic to $M$. This proves Scott isomorphism theorem.

Reflexivity follows by taking the two exponents equal to $1$, and symmetry is built into the two divisibility conditions. For transitivity, suppose $m\mid n^a$, $n\mid m^b$, $n\mid {\ell }^c$ and $\ell \mid n^d$. Then $m\mid {\ell }^{ac}$ and $\ell \mid m^{bd}$, with positive exponents. Thus the relation is an equivalence relation.

Its equivalence classes have a useful description by prime factorization. Let $S(n)$ be the finite set of prime factors of $n$, with $S(1)=\varnothing$. If $m\mid n^a$, every prime factor of $m$ divides $n$; the reverse divisibility gives $S(n)\subseteq S(m)$. Conversely, if $S(m)=S(n)$, write $m={\prod }_{p\in S}{p}^{{\alpha }_p}$ and $n={\prod }_{p\in S}{p}^{{\beta }_p}$, with all exponents positive. Choosing $a\ge {\max }_p\lceil {\alpha }_p/{\beta }_p\rceil$ and $b\ge {\max }_p\lceil {\beta }_p/{\alpha }_p\rceil$ gives the required divisibilities. The empty case is exactly $m=n=1$.

Therefore the prime-support equivalence relation iswhere the radical of an integer is the product of its distinct prime factors. The class with empty support is $\{1\}$. For every nonempty finite support $S$, all positive exponent choices give one class, and varying just one exponent produces infinitely many different integers in it.

There are infinitely many classes because each prime number gives a different singleton support. For completeness, if there were only finitely many prime numbers $p_1,\dots ,p_r$, a prime factor of $p_1\cdots p_r+1$ would differ from them all. There are infinitely many classes; the unique finite class is $\{1\}$.

For an equivalence relation $\sim$ on $X$, the equivalence class of $x\in X$ is $[x]=\{y\in X:y\sim x\}$. A set partition is a family of nonempty, pairwise disjoint subsets whose union is $X$.

Reflexivity ensures $x\in [x]$, so every equivalence class is nonempty and every element belongs to one. If $[x]\cap [y]$ contains $z$, then $z\sim x$ and $z\sim y$; symmetry and transitivity give $x\sim y$. If $w\in [x]$, transitivity gives $w\sim y$, so $w\in [y]$; interchanging $x,y$ gives the reverse inclusion. Thus intersecting equivalence classes are equal.

Taking the collection of distinct equivalence classes therefore produces a set partition of $X$. Every element lies in exactly one class. If $X$ is empty, the empty family is its set partition.

Let $R={\prod }_i{\mathcal{M}}_i/F$ be the reduced product by a proper filter on a set. Its underlying equivalence relation is $f\sim g$ when $\{i:f(i)=g(i)\}\in F$. Operations are interpreted coordinatewise, and a relation holds of the classes exactly when its coordinate truth set belongs to $F$.

Evaluation of a first-order term commutes with passage to the quotient, by mathematical induction on terms. Consequently the desired equivalence holds for every atomic formula, including logical equality. For a formula $\theta$ and representatives $\bar{f}$, write $S_{\theta }=\{i:{\mathcal{M}}_i\models \theta (\bar{f}(i))\}$.

For logical conjunction, $S_{\theta \wedge \psi }=S_{\theta }\cap S_{\psi }$. The filter on a set axioms giveThus the induction hypothesis transfers a conjunction in both directions.

For existential quantification, first suppose $R\models \exists y\theta (y,[\bar{f}])$. Choose a representative $g$ of a witness. Induction gives $S_{\theta (g,\bar{f})}\in F$, and this set is contained in $S_{\exists y\theta }$. Upward closure therefore gives $S_{\exists y\theta }\in F$.

Conversely, suppose $A=S_{\exists y\theta }\in F$. For each $i\in A$, choose a coordinate witness $g(i)$, and choose an arbitrary element of $M_i$ outside $A$. These simultaneous choices use the axiom of choice, as does the usual product construction. Then $A\subseteq S_{\theta (g,\bar{f})}$, so that truth set belongs to $F$. Induction gives $R\models \theta ([g],[\bar{f}])$, providing the required witness. Thereforefor every primitive positive formula. The exam's tame formulas are exactly this fragment, built using logical conjunction and existential quantification. No ultrafilter dichotomy was used.

A quotient topological space of a topological space $X$ is obtained by an equivalence relation $\sim$: its points are the classes $X/\sim$, and the canonical surjection is $q(x)=[x]$. The quotient topology declares a subset $U$ of the quotient open exactly when $q^{-1}(U)$ is open in $X$. More generally a surjection onto a set specifies the same topology by this condition.

For a Hausdorff source with a non-Hausdorff quotient, use $X=\mathbb{R}$ and $x\sim y$ when $x-y\in \mathbb{Q}$. Any nonempty open inverse image is a nonempty open subset of $\mathbb{R}$ invariant under rational translations. It contains an interval $I$, and for every real $t$ there is a rational $r$ with $t-r\in I$; hence it contains every $t$. Thus $\mathbb{R}/\mathbb{Q}$ has the indiscrete topology.

It has distinct points, for instance the classes of $0$ and $\sqrt{2}$, but neither has a proper nonempty open neighbourhood. The quotient is not Hausdorff, even though $\mathbb{R}$ is a Hausdorff space.

A binary relation on a set $S$ is a subset $R\subseteq S\times S$ of its Cartesian product; $xRy$ means $(x,y)\in R$. It is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation:An equivalence relation partitions $S$ into equivalence classes: two elements belong to the same class exactly when they are related.

The first condition concerns the domains: their symmetric difference $A△B$ must be a finite set. The original PDF prints this condition and the agreement condition together; the converted TeX omits both. The two existing solution scopes are used here to prove the domain and value parts of the single equivalence relation assertion.

Domain agreement is a reflexive relation because $A△A=\varnothing$, and a symmetric relation because $A△B=B△A$. For the transitive relation property, membership can differ between $A$ and $C$ only if it differs between $A$ and $B$ or between $B$ and $C$. ThusA set union of two finite sets is finite, so the domain condition passes through a chain of related pairs. This is the domain part of equivalence of partial functions modulo finite changes.

Let $S=\{1,x,x^2,\dots \}$. Since a principal ideal domain is an integral domain and $x\ne 0$, $S$ is a multiplicative subset avoiding zero. The stated equivalence relation and operations are precisely those of the localization of a ring $S^{-1}R$.

For completeness, reflexivity and symmetry are immediate, while transitivity follows by multiplying the two cross-multiplication identities and cancelling a nonzero power of $x$. If $(r,x^n)\sim (s,x^m)$ and $(r^{\prime },x^{n^{\prime }})\sim (s^{\prime },x^{m^{\prime }})$, cross multiplication shows that the proposed sums and products are equivalent. Thus the operations do not depend on representatives. The usual fraction calculations then prove associativity, commutativity and distributivity, with identities $[(0,1)]$ and $[(1,1)]$. Therefore $R^{\prime }$ is a well-defined commutative ring.

Symmetrization for an arbitrary real coefficient. Among graphs maximizing $f(G)=e(G)-c{k}_3(G)$, choose one maximizingFor a vertex $x$, put $L(x)=d(x)-ce(G[N(x)])$. This is the contribution of edges and triangles in a graph containing $x$. If $u,v$ are nonadjacent, Zykov symmetrization replacing $u$ by a clone of $v$ changes $f$ by $L(v)-L(u)$; the opposite replacement changes it by $L(u)-L(v)$. Maximality implies $L(u)=L(v)$, so both changes preserve $f$.

Let $S=N(v)\setminus N(u)$ and $T=N(u)\setminus N(v)$. In the first replacement the vertex degrees in $S$ increase by one and those in $T$ decrease by one; in the opposite replacement these changes reverse. The changes to $d(u{)}^2+d(v{)}^2$ cancel when the two replacements are added. Since $(d+1{)}^2+(d-1{)}^2-2d^2=2$,If the two vertex neighbourhoods differ, one replacement increases $Q$, a contradiction. Thus every pair of nonadjacent vertices has the same vertex neighbourhood. Nonadjacency, with equality allowed, is an equivalence relation: if $u$ and $v$ are nonadjacent and $v$ and $w$ are nonadjacent, their identical vertex neighbourhoods forbid $uw$ as well. Its classes are independent sets and every cross-class edge is present. ThereforeThis edge-triangle symmetrization works for either sign of $c$.

The exact supporting line. For $n\ge 3$, writeWe prove the triangle support line between bipartite and tripartite Turan graphs by maximizing $e-c_{\ast }{k}_3$. First $c_{\ast }\ge 2/n$. For $n=3,4,5$, its values are respectively $1,1/2,1/2$. For $n\ge 6$, the exact balancing of the Turán graph gives $e_3\ge n^2/3-1/3$, while $e_2\le n^2/4$ and the arithmetic-geometric mean inequality gives $t_3\le n^3/27$. Hence

By edge-triangle symmetrization a maximizing graph can be taken complete multipartite graph; among such maximizers use one with the fewest nonempty parts. If there are at least four parts, let $a,b$ be the two smallest sizes. Then $a+b\le n/2$. Merging them loses $ab$ edges and $ab(n-a-b)$ triangles in a graph, so the objective changes byThis contradicts the choice of the number of parts. Thus at most three parts remain.

For three part sizes $a\ge b\ge d>0$, the objective isIf $1-c_{\ast }b\le 0$, merging the parts of sizes $a,d$ does not decrease it, again contradicting minimality. If $1-c_{\ast }b>0$ and $a-d\ge 2$, transferring one vertex from the largest to the smallest part raises $ad$ by $a-d-1>0$ and strictly increases the objective. Thus a three-part maximizer has all sizes differing by at most one, and is $T_3(n)$. A maximizer with at most two parts has objective at most $e_2$, since it has no triangles in a graph and the Mantel theorem bounds its edges. Finally,Therefore every graph satisfies $e(G)-c_{\ast }{k}_3(G)\le e_2$. At the prescribed edge count this givesFor $n\le 2$, the conclusion is simply the nonnegative lower bound zero. All rounding in the Turán graphs has been retained.

One edge above the bipartite threshold. Write $n=2m$. We prove the Triangle lower bound one edge above the Mantel threshold by induction on $m\ge 2$, allowing at least $m^2+1$ edges. For $m=2$, five edges on four vertices give two triangles in a graph, and adding edges preserves this bound.

We will also use the following consequence of an inductive bound: on $2a$ vertices, at least $a^2+q$ edges, for an integer $q\ge 1$, force at least $a+q-1$ triangles in a graph. Delete surplus edges first to leave exactly $a^2+q$. Repeatedly delete an edge in a triangle in a graph until $a^2+1$ edges remain. The Mantel theorem guarantees such a triangle in a graph at every step; each deletion destroys at least one distinct triangle in a graph. Apply the inductive bound to the remaining graph.

Now take exactly $m^2+1$ edges. If every edge lies in a triangle in a graph, the edge-triangle incidence bound gives $3k_3(G)\ge m^2+1$. This is at least $3m$ for $m\ge 3$; the base case was handled separately.

Otherwise choose an edge $uv$ in no triangle in a graph. Its endpoints have disjoint vertex neighbourhoods, so $d(u)+d(v)\le 2m$. Deleting $u,v$ removes exactly $d(u)+d(v)-1$ edges and leaves at least $(m-1{)}^2+1$ edges. If $d(u)+d(v)\le 2m-1$, it leaves at least $(m-1{)}^2+2$ edges, and the strengthened inductive bound gives at least $m$ triangles in a graph already.

If $d(u)+d(v)=2m$, induction gives at least $m-1$ triangles in a graph after deletion. There must be an additional triangle in a graph containing $u$ or $v$. Otherwise both $N(u)$ and $N(v)$ are independent sets; since they are disjoint and cover all vertices, $G$ would be bipartite graph, contradicting $e(G)>m^2$ by the Mantel theorem. HenceThe bound is sharp: add one internal edge to one class of the complete bipartite graph $K_{m,m}$. Its triangles in a graph are precisely that edge together with each of the $m$ vertices in the other class.

Assume $ad\equiv bc(\mathrm{mod}n)$ and choose $r,s$ as in part (b). Put $\lambda =rc+sd$. Multiplying $ra+sb\equiv 1$ by $c$ and using $ad\equiv bc$ givesSimilarly, multiplication by $d$ gives $\lambda b\equiv d(\mathrm{mod}n)$.

Moreover, $\lambda$ is a unit modulo n: if a prime divided both $\lambda$ and $n$, the two congruences would make it divide $c,d,n$, contrary to $(c,d)\in Y$. Thus $R$ means precisely that two pairs differ by multiplication by a unit modulo $n$. Reflexivity, symmetry using ${\lambda }^{-1}$, and transitivity using products of units now show that $R$ is an equivalence relation.

If $A\subseteq X$, the subspace topology on $A$ isIf $\sim$ is an equivalence relation on $X$ and $q:X\to X/\sim$ is the natural projection, the quotient topology declares $V\subseteq X/\sim$ open exactly when $q^{-1}(V)$ is open in $X$. For topological spaces $X$ and $Y$, the product topology on $X\times Y$ has as a basis all sets $U\times V$ with $U$ open in $X$ and $V$ open in $Y$.

An equivalence relation is reflexive, symmetric, and transitive. HereThe relation is reflexive and symmetric, but it is not transitive. For example, takeThe real parts of $x\overline{y}$ and $y\overline{z}$ are positive, whereas that of $x\overline{z}$ is negative. Hence this is not an equivalence relation.

States $i$ and $j$ communicate when each is accessible from the other: there exist $m,n\ge 0$ withThis is an equivalence relation, and its equivalence classes are the communicating classes. A class is closed when no positive-probability transition leaves it.

The definition saysEquality of sets is reflexive, symmetric, and transitive, so $\sim$ is an equivalence relation. Its classes are indexed by all subsets of $\{1,\dots ,n\}$, and every subset occurs as the support of its zero-one indicator vector. The number of classes is therefore

A compact space is a topological space in which every open cover has a finite subcover. A Hausdorff space is one in which every two distinct points have disjoint open neighbourhoods. A homeomorphism is a bijection that is continuous and whose inverse is continuous.

For an equivalence relation $R$ on $X$, let $X/R$ be the set of equivalence classes and letThe quotient topology declares $U\subseteq X/R$ open exactly when $q^{-1}(U)$ is open in $X$. It follows directly from the definition that $q$ is continuous.

Suppose that the continuous map $f:X\to Y$ is constant on equivalence classes. The only possible factorisation iswhich is well-defined by the hypothesis and satisfies $F\circ q=f$. For every open $V\subseteq Y$,is open in $X$. The definition of the quotient topology therefore makes $F^{-1}(V)$ open, so $F$ is continuous. This proves the universal property of the quotient topology.

The coefficient $⟨e(t),\omega ⟩$ is nonzero exactly when every column of $t$ meets every row of $\omega$ in at most one entry. Permuting equal-length rows of $\omega$ preserves this condition, and the same holds with $u$ in place of $t$. Therefore membership in $A_{tu}$ is constant on each class of the stated equivalence relation, so $A_{tu}$ is a union of equivalence classes.

Two elements are conjugate group elements if $h=xg{x}^{-1}$ for some $x\in G$. The conjugacy class of $g$ is $\{xg{x}^{-1}:x\in G\}$. Conjugacy is an equivalence relation: it is reflexive using $x=e$, symmetric by replacing $x$ with $x^{-1}$, and transitive becauseThus the classes partition the group: every element belongs to its own class, and any two classes that intersect are equal. This proves that every element belongs to exactly one class.

If $G$ is Abelian, then $xg{x}^{-1}=g$, so every class is a singleton. In general the elements whose classes are singletons are precisely those commuting with every group element. Thus the center of a group isIt contains $e$. If $a,b\in Z(G)$, then $a{b}^{-1}$ commutes with every $g$, since $b^{-1}$ does and $a$ does. The subgroup test therefore proves that $Z(G)$ is a subgroup. Any two of its elements commute with each other, so it is an abelian subgroup.

For the square centred at the origin with vertices $(\pm 1,\pm 1)$, putThe dihedral group $D_4$ consists of $R^j$ and $R^{j}S$, $j=0,1,2,3$. Its eight actions and their matrices areThese exhaust the symmetries: the image of one vertex has four choices and the image of an adjacent vertex has two choices, determining the entire square. For an explicit pair of nonconjugate elements take $R^2$ and $S$. Both have order two, but their determinants are $+1$ and $-1$. A similarity transformation preserves the determinant, so $R^2$ and $S$ are not conjugate.

To find the centre, use $SR=R^{-1}S$. A rotation $R^j$ commutes with $S$ exactly when $R^j=R^{-j}$, so $j$ is even. No reflection $R^{j}S$ commutes with $R$, since $(R^{j}S)R=R^{j-1}S$ while $R(R^{j}S)=R^{j+1}S$, and $R^2\ne I$. Therefore

A sufficient condition is that $T$ be first-order consistent, complete, and full in its own first-order language. Work in the allowed function-free setting. Since $T$ proves the logically valid first-order sentence $\exists x(x=x)$, fullness guarantees at least one constant and a nonempty collection of names.

Form the carrier from equivalence classes $[c]$ of constant symbols underLogical equality logic makes this an equivalence relation. Interpret a constant by its class and interpret each relation symbol bySubstitution of equals makes this independent of representatives. This defines a canonical first-order structure because every carrier element is named by a constant.

The truth lemma, proved by induction on logical formulas with constants substituted for their free variables, saysAtomic formulas hold by construction; completeness and first-order consistency give the Boolean steps. For the existential step, a witness in the first-order structure is a named class, so its truth gives a proved instance and hence a proved existential sentence. Conversely a proved existential sentence has a constant witness by fullness, and the induction hypothesis realizes that instance in the first-order structure. The universal case follows by negation. Thus $\mathcal{M}\models T$, provingThe witness condition is needed in the original first-order language; adding new constants produces a canonical first-order structure in an expanded first-order language, which is a different assertion.

Use the first-order language with one equivalence relation $E$. Let $\mathcal{A}$ have exactly two equivalence classes, one countably infinite and one uncountable, with no further first-order structure. Its complete theory says that there are exactly two classes and both are infinite.

This first-order theory has quantifier elimination. To eliminate one existential logical variable from a conjunction of atomic formulas and negated atomic formulas, a logical equality either fixes its value, or finitely many inequalities exclude finitely many points. Its required equivalence-class membership is determined by the finitely many existing classes represented among the parameters. A required unused class exists exactly when fewer than two classes have already been used. Once its class is possible, infinitude supplies a point avoiding the finite exclusions. These tests are quantifier-free logical equality and equivalence conditions on the parameters. Disjunctive normal form and induction eliminate all quantifiers and also show completeness.

Thus a finite tuple's complete type is isolated by its finite equality-and-equivalence pattern. Every realized finite-tuple partial type is principal, so $\mathcal{A}$ is atomic. In particular all individual elements have the same complete one-type, isolated by $x=x$.

Choose $a$ in the countable class and $b$ in the uncountable class. Any automorphism taking $a$ to $b$ would give a bijection from their whole equivalence classes, impossible because their cardinalities differ. ThereforeIts uncountability is precisely what avoids the conclusion of (iii).

The same complete theory $T_{\infty }$ of an infinite pure set provides this property directly. For $n$ logical variables, each complete type specifies exactly which logical variables are equal. First-order consistency requires an equivalence relation on the finite index set, and infinitude ensures every such partition is realizable. Hencewhere $B_n$ is the $n$th Bell number, counting partitions of an $n$-element set. For example the first values are $B_1=1$, $B_2=2$ and $B_3=5$. The isolating conjunction lists logical equality within blocks and inequality between blocks. This explicitly verifies the hypothesis which Ryll-Nardzewski identifies with ${\aleph }_0$-categoricity.