5

My question is the title. I would be glad if someone could supply a proof if true, or a counterexample if false.

user107952
  • 20,508

2 Answers2

7

We assume that we are working in the predicate calculus with equality. Let $L$ be any language, and $M$ any finite $L$-structure, say with $n$ elements. Let $\Sigma$ be the set of sentences that says that there exist exactly $n$ elements, and that describes the full diagram of $M$. Then any model of $\Sigma$ is isomorphic to $M$. If the language is finite, instead of $\Sigma$ we can use a single sentence.

Remark: We consider the special case of groups, with language that has a single binary function symbol $\times$. Suppose that $M$ is a group, with elements $a_1,\dots,a_n$. In addition to the sentence that says there are exactly $n$ elements, we need as axioms that there exist $x_1,\dots,x_n$, all distinct, such that $x_i\times x_j=x_k$, for all triples $i,j,k$ such that $m_im_j=m_k$. The full diagram is unnecessary, the multiplication table is enough.

Ibrahim Tencer
  • 506
André Nicolas
  • 507,029
  • Did you assume that the language $L$ has only a finite number of non-logical symbols? The OP's question still has an affirmative answer for languages with infinitely many relations, but it no longer suffices to consider a single sentence. – bof Jul 13 '14 at 05:40
  • Thank you, I was half general language half group theory. Replaced $\sigma$ with $\Sigma$. – André Nicolas Jul 13 '14 at 05:45
  • Concerning your Remark: What are $x_1,...,x_n$ (e.g. are they "words" in the alphabet ${a_1,...,a_n}$)? And what are $m_i$, $m_j$, and $m_k$? Also, do the $x_i$ need to be distinct? For example, could we specify a group with two elements $e$ and $a$ by the rules $a\times a=e$, $e\times a=a$, etc.? – John Bentin Jul 13 '14 at 06:19
  • The $x_i$ are what are usually called variable symbols, every first-order language has a countable infinity of them. Yes, they are distinct, we need $n$ of them to make the sentence that says there are exactly $n$ distinct objects. – André Nicolas Jul 13 '14 at 06:25
  • 1
    @Ibrahim Tencer: Thank you for spotting and fixing the $\sigma$, $\Sigma$ TeX error. – André Nicolas Mar 02 '15 at 06:37
3

Let us spell out an example of Andre's answer (for concreteness).

Suppose a group $G$ satisfies the same first-order sentences as $C_2$, the cyclic group of order $2$.

  1. Then $G$ satisfies the following sentence, asserting that there are at most $2$ elements in the group. $$\forall xyz(x=y \vee y=z \vee x=z)$$

  2. And $G$ satisfies the following sentence, which encodes the diagram of $C_2$ (also known as its Cayley table) as a first-order formula.

$$\exists xy(x \neq y \wedge xx=x \wedge xy=y \wedge yx=y \wedge yy=x)$$

But this means that $G$ is isomorphic to $C_2$.

goblin GONE
  • 67,744
  • But this is kind of trivial in the first place, since there is only one group of order 2. But is does show that if G is any mathematical object satisfying the same F0 sentences as $C_2$ in the language of group theory, then $G\cong C_2$. – Kyle Gannon Jul 13 '14 at 08:48
  • @KyleGannon, sure. All I wanted was to "unpack" Andre's answer for the OP; concrete examples are good. I could have done it for $C_4$ instead, but that would make the whole thing exponentially more painful to write out. – goblin GONE Jul 13 '14 at 08:52
  • Understandable, I'm never against concrete examples. – Kyle Gannon Jul 13 '14 at 08:55
  • @goblin, the size is quadratic in n, no? – Mariano Suárez-Álvarez Mar 02 '15 at 06:54