Intereting Posts

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$
Determining whether the series $\sum_{n=1}^{\infty} \frac{\sqrt{n}+\sin(n)}{n^2+5}$ is convergent or divergent by comparison test
Relationship between Continuum Hypothesis and Special Aleph Hypothesis under ZF
Bayesian Network, Sprinkler Example
Combinatorics with simple substitution ciphers question
Approximation in Sobolev Spaces
The position of a ladder leaning against a wall and touching a box under it
Cardinality of separable metric spaces
Needing help picturing the group idea.
$\lim\limits_{x\to\infty}f(x)^{1/x}$ where $f(x)=\sum\limits_{k=0}^{\infty}\cfrac{x^{a_k}}{a_k!}$.
Modules over $k$
Algorithm for multiplying numbers
Functions $f(x)/g(x), g(x)/h(x),h(x)/f(x)$ are constant
Prove the normed space of bounded variation functions is complete
Finding sum form for a particular recursive function

Somewhere I read that finite structures can be uniquely described (up to an isomorphism) using a sentence which is a conjunction of all atomic formulas, and their negation, and an another sentence that asserts the finiteness of the structure. Why this is true? How to prove it? What changes when the structure becomes of infinite cardinality?

- How to show the Symmetric Group $S_4$ has no elements of order $6$.
- Compute $ad_X$, $ad_Y$, and $ad_Z$ relative to a basis
- What is this property relating to logical systems called?
- The set $\{g^2 | g \in G\}$ in a group $G$
- Prove that a group of order 30 has at least three different normal subgroups
- Prove that the Gaussian Integer's ring is a Euclidean domain
- Intuition about the second isomorphism theorem
- Prove that if $p\in \mathbb{Z}$ is irreducible, then it is also prime.
- Number of elements of order $p$ is a multiple of $p-1$ (finite group).
- Can the semidirect product of two groups be abelian group?

Suppose $\mathcal{A}$ is a finite structure of size $n$, in a finite language $\mathcal{L}$. Let’s first note that we can write a sentence $\varphi_n$ which asserts “There are exactly $n$ many elements”: $$\varphi_n\quad\equiv\quad \exists x_1\exists x_2 . . . \exists x_n((\bigwedge_{1\le i<j\le n} x_i\not=x_j)\wedge\forall y(\bigvee_{1\le i\le n}x_i=y)).$$ This sentence says “There are $n$ elements, which are distinct, and such that any additional element is equal to one of them.” That is, there are exactly $n$ elements.

Now, note that this sentence actually does a bit more: it gives *names* for each of the $n$-many elements. Namely, for $\psi$ a *formula* in the variables $x_1, x_2, . . . , x_n$, let $\varphi_n^\psi$ be the sentence $$\varphi_n^\psi\quad\equiv\quad \exists x_1\exists x_2 . . . \exists x_n((\bigwedge_{1\le i<j\le n} x_i\not=x_j)\wedge\forall y(\bigvee_{1\le i\le n}x_i=y)\wedge \psi(x_1, . . . , x_n)).$$ So $\varphi_n^\psi$ says $$\mbox{“The universe consists of the distinct elements $x_1, x_2, . . . , x_n$; and the statement $\psi$ is true about them.”}$$

Now, what kind of information can we cram into $\psi$? The answer is, *all* the information (since the language $\mathcal{L}$ is finite)! Specifically, let $\mathcal{A}=\{a_1, a_2, . . . , a_n\}$ (note that there are many ($n!$) ways to enumerate $\mathcal{A}$; we pick one arbitrarily here). Since $\mathcal{L}$ is finite, there are only finitely many atomic and negated atomic sentences in the parameters $a_1, . . . , a_n$ (this is a good exercise); that is, the *atomic diagram* $At(\mathcal{A})$ of $\mathcal{A}$ is finite. This means we can take the conjunction of all these finitely many sentences, and the result is a single first-order sentence $\theta$ in the language $\mathcal{L}$ . . .

. . . using $a_1, a_2, . . . , a_n$ as parameters. But that’s okay! Let $\psi$ be the formula gotten from $\theta$ by replacing $a_i$ with the variable $x_i$; then $\psi$ is a formula in the language $\mathcal{L}$, with free variables $x_1, . . . , x_n$. Now consider the sentence $\varphi_n^\psi$. This sentence says that there are exactly $n$ many elements, and that the way these elements relate to each other is precisely the way the elements of $\mathcal{A}$ relate to each other.

**Exercise**. Suppose $\mathcal{B}\models\varphi_n^\psi$ via a variable assignment $x_i\mapsto b_i$. Then show that the map $f: \mathcal{B}\rightarrow\mathcal{A}: b_i\mapsto a_i$ is an isomorphism.

Where does this go wrong if infinity slips in?

Well, if the structure is infinite – say, countably infinite – then in order to build “$\varphi_{\aleph_0}$,” we need to quantify over countably infinitely many variables! That is, we need to write something like $$\exists x_1\exists x_2 …\exists x_n…$$ But we can’t do that in first-order logic. Additionally, we need to take infinite conjunctions and disjunctions, when we assert that the $x_i$s are distinct and that every element of the universe is an $x_i$. Again, not doable in first-order logic. What we need to make that work is **infinitary logic**; namely, to completely pin down a structure of size $\kappa$ for $\kappa$ infinite, we need the infinitary logic $\mathcal{L}_{\kappa^+\kappa^+}$.

*Interestingly, if we just want to pin down a size-$\kappa$ structure $\mathcal{A}$ amongst structures of size $\le\kappa$, we can get away with less! For example, if $\mathcal{A}$ is countable in a countable language then there is an $\mathcal{L}_{\omega_1\omega}$-sentence $\varphi$ – the Scott sentence of $\mathcal{A}$ – such that any countable $\mathcal{B}$ satisfying $\varphi$ is isomorphic to $\mathcal{A}$. But $\varphi$ may have uncountable models . . .*

For finite structures in an infinite language, things aren’t so bad, but they still break. Building $\varphi_n$ still works; but when we come to the $\theta$-part, we get into trouble. In an infinite language, there are *not* only finitely many atomic and negated atomic sentences with finitely many parameters! So we need to use an infinite conjunction here. Specifically, a finite structure in an infinite language of cardinality $\kappa$ can be pinned down by a sentence in the infinitary logic $\mathcal{L}_{\kappa^+\omega}$.

(As an example of a finite structure in an infinite language, consider the language with countably infinitely many unary predicate symbols $U_i$, and the structure $\mathcal{A}$ with one element $a$ such that $U_i(a)$ holds for every $i$. It’s a good exercise to show that no single sentence in the language pins down $\mathcal{A}$ up to isomorphism.)

EDIT: Actually, though, this is a bit misleading as Alex Kruckman points out above. Since all we need in this case is an infinite conjunction, it is still the case that a finite structure in an arbitrary language is characterized by *its first-order theory*. While this is not in general equivalent to a single first-order *sentence*, this is still much much better than an arbitrary $\mathcal{L}_{\kappa^+\omega}$-sentence.

- Adjoint functors
- Derived category and so on
- How do we know that we'll never prove a contradiction in Math
- Gaussian integral with a shift in the complex plane
- find Limit $a_n= \frac{1}{n+1}+\frac{1}{n+2}+…+\frac{1}{n+n}$
- A conjecture including binomial coefficients
- How many words of length $n$ can we make from $0, 1, 2$ if $2$'s cannot be consecutive?
- Evaluating real integral using residue calculus: why different results?
- liminf in terms of the point-to-set distance
- Splicing together Short Exact Sequences
- Choosing subsets of a set with a specified amount of maximum overlap between them
- Rotating x,y points 45 degrees
- Finite injective dimension of the residue field implies that the ring is regular
- Separately continuous functions that are discontinuous at every point
- $\int_0^{\infty} A( f(B(x)) ) + C(x) ) dx = \int_0^{\infty} f(x) dx$