7
$\begingroup$

Definitions. By a structure, I mean a set equipped with some finitary operations and finitary relations. By a non-standard model of a structure $X$ with respect to a logic, I mean a model of the complete theory (in the sense of that logic) of $X$ that isn't isomorphic to $X$. Let us define that a logic pins down $X$ iff $X$ has no non-standard models with respect to that logic.

(These are a vague definitions, of course, since I haven't defined the term "logic.")

Question. Is there a logic so powerful it pins down every structure up to isomorphism?

Background.

It is well-known that first-order logic often doesn't pin down structures up to isomorphism. For instance, $\mathbb{N}$ has non-standard first-order models, meaning that there exist models of the first-order theory of $\mathbb{N}$ that aren't isomorphic to $\mathbb{N}$. From what I've read, these are important in Abraham Robinson's approach to non-standard analysis (about which I know almost nothing.).

Second-order logic fares a bit better. For instance, $\mathbb{R}$ has no non-standard second-order models; more precisely, the axioms of a Dedekind-complete totally-ordered field have precisely one model up to isomorphism, namely $\mathbb{R}.$ But second-order logic doesn't pin down every structure, see here. Hence the question.

$\endgroup$
7
  • $\begingroup$ Nor "pins down," for that matter. A far more vague term. $\endgroup$ Oct 2, 2015 at 1:30
  • $\begingroup$ @ThomasAndrews, see the edit. $\endgroup$ Oct 2, 2015 at 1:33
  • 1
    $\begingroup$ This sounds like the premise for an over-the-top anime series. "His logic! It's... too powerful!!" $\endgroup$
    – user856
    Oct 2, 2015 at 2:47
  • 2
    $\begingroup$ goku's logic is over 9000 @Rahul $\endgroup$ Oct 2, 2015 at 3:05
  • 3
    $\begingroup$ "You have bested me in battle before, but you will never defeat . . . my cofinal form!" . . . Okay, I'll stop. :P $\endgroup$ Oct 2, 2015 at 4:11

1 Answer 1

14
$\begingroup$

I think the most direct way to answer your question is provided by infinitary logic.

Given cardinals $\kappa, \lambda$ - with $\kappa\ge\lambda$ (you'll see why) - we let $\mathcal{L}_{\kappa\lambda}$ be the logic which you get by taking first-order logic and

  • closing under $(<\kappa)$-ary conjunctions, and

  • allowing quantification over $(<\lambda)$-tuples of variables.

For example, $$\bigvee_{n\in\omega} e=x*. . . *x \mbox{ ($n$-many "$*$"s)}$$ is a formula of $\mathcal{L}_{\omega_1\omega}$ in the language of groups asserting that $x$ has finite order.

The class-sized "superlogics" (not a technical term, just my term) $\mathcal{L}_{\infty\omega}$ and $\mathcal{L}_{\infty\infty}$ are defined in the obvious way. (We can similarly define $\mathcal{L}_{\infty\lambda}$ for $\lambda$ arbitrary, but generally it's the two extremes that are most interesting.)

Exercise. For every (set-sized) structure $\mathcal{A}$, there is a single sentence $\varphi\in \mathcal{L}_{\infty\infty}[\Sigma]$ (where $\Sigma$ is the language of $\mathcal{A}$) such that $\varphi$ characterizes $\mathcal{A}$ up to isomorphism.


Now, you might look at this and think, "That's kind of trivial." Let me convince you that this is in fact really cool!

First, note that the proper-class-sized-ness of $\mathcal{L}_{\infty\infty}$ is unavoidable, since there are proper-class-many set-sized structures, even of a fixed (fine, nonempty :P) language. So the fact that $\mathcal{L}_{\infty\omega}$ is big isn't a cop-out, but a necessary aspect.

Second, note that $\mathcal{L}_{\infty\infty}$ is the "smallest" infinitary logic which has this property! For each $\kappa$, we can find two non-isomorphic structures $\mathcal{A}$ and $\mathcal{B}$ which are $\mathcal{L}_{\infty\kappa}$-equivalent. This is a good exercise.

EDIT: Actually, there is a sense in which the vastly weaker logic $\mathcal{L}_{\infty\omega}$ captures every structure up to isomorphism: by a theorem of Karp (and an observation of Barwise), $\mathcal{A}\equiv_{\infty\omega}\mathcal{B}$ iff there is some forcing extension in which $\mathcal{A}\cong\mathcal{B}$! So $\mathcal{L}_{\infty\omega}$ captures every structure up to "potential isomorphism" (which is a rich concept; see e.g. http://arxiv.org/abs/math/9301208 for an analysis of how hard it can be to make two $\mathcal{L}_{\infty\omega}$-equivalent structures isomorphic, and http://www.jstor.org/stable/1997774?seq=1#page_scan_tab_contents for a beautiful result that there is no similar characterization of $\mathcal{L}_{\infty\lambda}$ for $\lambda$ uncountable).

Third, these infinitary logics are actually really interesting in and of themselves! By far the most interesting is $\mathcal{L}_{\omega_1\omega}$, which - together with its reasonably-closed countable fragments - has deep connections with descriptive set theory, model theory, and computability theory.

Fourth and finally, note that infinitary logic(s) provides a really nice way to sharpen your question. You may well ask:

For $\mathcal{A}, \mathcal{B}$ nonisomorphic structures in the same language, how hard is it to tell them apart?

One way of answering this is by asking:

For which infinitary logics $\mathcal{L}_{\kappa\lambda}$ do we have $\mathcal{A}\not\equiv_{\kappa\lambda}\mathcal{B}$?

There is a ton of research in this and related directions; let me just start you off with a fundamental result about countable structures:

(Scott's isomorphism theorem.) For $\mathcal{A}$ a countable structure in a countable language, there is a single $\varphi\in\mathcal{L}_{\omega_1\omega}$ - the Scott sentence of $\mathcal{A}$ - such that $\varphi$ characterizes $\mathcal{A}$ up to isomorphism.

By looking at fragments $\mathcal{L}_{\alpha\omega}$ of $\mathcal{L}_{\omega_1\omega}$ for $\alpha$ a countable ordinal (note that the definition given above doesn't work; my notation is purely suggestive), we can sharpen this theorem, and attach to each countable structure a countable ordinal, called the Scott rank, which measures how hard the structure is to pin down up to isomorphism.

Remark 1: Scott sentences and ranks make sense for uncountable structures, too!

Remark 2: There are sadly several different nonequivalent definitions of Scott rank; they're all basically the same, except they sometimes differ e.g. by +1. See https://math.berkeley.edu/~antonio/papers/scottRank.pdf.

$\endgroup$
3
  • $\begingroup$ We could consider "infinitarizing" other logics than first-order - e.g., start with second-order logic on the bottom - and look at the different notions of Scott rank that emerge. However, as far as I know nothing really interesting has been done along these lines (although of course that doesn't preclude interesting things from being do-able!). $\endgroup$ Oct 2, 2015 at 2:16
  • $\begingroup$ Isn't there a connection with Ehrenfeucht–Fraïssé games as well? $\endgroup$
    – Zhen Lin
    Oct 2, 2015 at 15:22
  • $\begingroup$ Would it be correct to understand these infinitary logics as "existing inside of" or being interpreted in some finitary theory (e.g. ZFC) capable of defining ordinals and cardinals? Do these infinitary logics then have different properties depending on which (first-order) structure they are interpreted in (e.g. ZFC vs MK)? If they are more powerful than second-order logic with full semantics at pinning down structures, and second-order logic with full semantics is "set theory in sheep's clothing", I don't see how these infinitary logics could avoid also being "set theory in sheep's clothing"? $\endgroup$ Jan 16, 2023 at 17:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .