4
$\begingroup$

As I mentioned in my previous question, I am reading the following paper:

One-dimensional asymptotic classes of finite structures.

by: Macpherson and Steinhorn


I have some crazy questions!

  1. What is the idea behind the notion of asymptotic class. All of the papers mention the theorem of Chatzidakis, van den Dries, and Macintyre [Theorem 1.1 in the paper]. But that is not what I'm looking for!

  2. Let $\mathcal{C}$ be a one-dimensional asymptotic class of finite structures. Let $\mathcal{M}$ be an infinite ultraproduct of members of $\mathcal{C}$. Is there a first order sentence $\phi$ that is true in $\mathcal{M}$ but it does not hold in infinitely many members of $\mathcal{C}$?

$\endgroup$
  • $\begingroup$ Can you explain why references to Theorem 1.1 are not satisfactory? The definition of asymptotic class is a direct abstraction of that theorem. $\endgroup$ – Alex Kruckman Aug 14 at 2:21
  • $\begingroup$ @AlexKruckman My problem is exactly what you mentioned! Actually, my question is the idea behind Theorem 1.1? Honestl, for me this theorem is an interesting technical lemma (which should be used to get other results!) not an interesting Theorem just for itself! $\endgroup$ – Mark Smith Aug 14 at 21:00
  • $\begingroup$ Well, there are definitely some people who would disagree with you. Some people like counting for the sake of counting! $\endgroup$ – Alex Kruckman Aug 14 at 21:49
4
$\begingroup$

The answer to your second question is "no", but this doesn't have anything to do with $1$-dimensional asymptotic classes specifically, just ultraproducts.

Suppose $\mathcal{C}$ is a class of finite structures and $\mathcal{M}=\prod_{\mathcal{U}}C_i$ is an infinite ultraproduct of members of $\mathcal{C}$, where $\mathcal{U}$ is an ultrafilter on some index set $I$.

Now suppose $\phi$ is a first-order sentence true in $\mathcal{M}$. Let $J=\{i\in I:C_i\models\phi\}$. Then $J\in\mathcal{U}$ by Los's Theorem. It follows that the collection $\{C_i:i\in J\}$ contains structures of arbitrarily large cardinality. So, in particular, $\phi$ holds for infinitely many structures in $\mathcal{C}$.

To justify the last claim, suppose there is some integer $N$ such that if $i\in J$ then $C_i$ has cardinality at most $N$. Let $J'=\{i\in I:|C_i|\leq N\}$. Then $J\subseteq J'$, and so $J'\in\mathcal{U}$. By Los's Theorem (note that "cardinality at most $N$" can be written as a first-order sentence), $|\mathcal{M}|\leq N$, which contradicts the assumption that $\mathcal{M}$ is infinite.

EDIT: Someone else who studies 1-dimensional asymptotic classes more than me would provide a better answer to the first question. But a major motivation for the definition was to isolate broad combinatorial conditions on classes of finite structures under which behavior similar to the results of Chatzidakis, van den Dries, and Macintyre would be found. In general, when studying classes of finite structures through pseudofinite constructions, one always has ways of "counting" or "measuring" definable sets via the pseudofinite counting measure (which can be defined on sets in any dimension), for example. In one-dimensional asymptotic classes, this "counting and measuring" apparatus is much more finitely tuned, which allows for stronger results.

EDIT #2. The answer above shows that if $\mathcal{M}$ is an infinite ultraproduct of finite structures, and $\mathcal{M}\models\phi$, then $\phi$ is true in infinitely many members of $\mathcal{C}$. One can also arrange for $\phi$ to be false in infinitely many members of $\mathcal{C}$. For example, let $\mathcal{C}=\{G_n:n\geq 1\}$ where $G_n$ is the cyclic group of order $n$. (Incidentally, $\mathcal{C}$ is a $1$-dimensional asymptotic class.) Let $\mathcal{U}$ be a nonprincipal ultrafilter on $\mathbb{Z}^+$ which contains the set of even integers. Let $\mathcal{M}=\prod_{\mathcal{U}}C_n$. Then $\mathcal{M}$ satisfies the sentence $\phi$ saying "there is an element of order 2" since this sentence is true in $G_n$ for any even $n$. But there are infinitely many members of $\mathcal{C}$ where $\phi$ fails, namely $G_n$ for odd $n$.

$\endgroup$
  • 1
    $\begingroup$ Yeah! if $\phi$ is true in $\mathcal{M}$, it holds for infinitely many members of $\mathcal{C}$. But $\phi$ might be false in infinitely many members of $\mathcal{C}$ as well! Does asymptoticness quarantee that $\phi$ can not be false in infinitely many structures? $\endgroup$ – Mark Smith Aug 13 at 21:03
  • $\begingroup$ Oh ok, I interpreted that wording differently. Let me add another edit. $\endgroup$ – Gabe Conant Aug 13 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.