7
$\begingroup$

Recall that a set is amorphous iff it is infinite but has no partition into two infinite subsets. I'm interested in the possible structure (in the sense of model theory) which an amorphous set can carry. For example, if $T$ is a complete first-order theory with an amorphous model then $T$ must be strongly minimal; however, the converse fails badly (consider $Th(\mathbb{C};+,\times)$).

I'm curious whether second-order logic does a better job. For $T$ a complete second-order theory with no finite models, say that $T$ is second-order strongly minimal iff every second-order-definable subset of every model $\mathcal{A}\models T$ is either finite or cofinite in $\mathcal{A}$. For example, $Th(\mathbb{C};+,\times)$ is not second-order strongly minimal since $\mathbb{Z}\subset\mathbb{C}$ is second-order definable.

EDIT: by "complete" I mean "maximally satisfiable:" a second-order theory $T$ is complete iff it is satisfiable and for each second-order sentence $\varphi$, either $\varphi\in T$ or $\neg\varphi\in T$.

To be reasonably concrete, my main question is the following:

Question 1: Is it consistent with $\mathsf{ZF}$ that every second-order strongly minimal theory has an amorphous model?

(More broadly, I'm interested in whether there is a reasonably natural logic $\mathcal{L}$ such that consistently with $\mathsf{ZF}$ every "$\mathcal{L}$-strongly-minimal" theory has an amorphous model. Second-order logic just seems like a good candidate at the moment.)

There's also a "virtual" version of the question which makes sense even in the presence of choice:

Question 2: Is it consistent with $\mathsf{ZFC}$ that for every second-order strongly minimal theory $T$, there is some (set) symmetric extension in which $T$ has an amorphous model?

The exact relationship between these two questions isn't clear to me. That said, an affirmative answer to question 2 seems much more plausible than an affirmative answer to question 1.

$\endgroup$
5
  • $\begingroup$ The second question implies the first, by the way. (And not only in the sense that both have a negative answer...) $\endgroup$
    – Asaf Karagila
    Commented Jul 9, 2021 at 8:18
  • $\begingroup$ There are complete second-order theories with no models at all in ZF. To be concrete, take Asaf's example here and complete it (which doesn't require choice): math.stackexchange.com/questions/1005283/…). $\endgroup$
    – Harry West
    Commented Jul 9, 2021 at 8:50
  • 2
    $\begingroup$ @HarryWest That does not make much sense to me. Second-order logic has no sensible proof system, and it is not compact, thus consistency in second-order logic is defined by the existence of a model. Also, due to lack of compactness, second-order theories cannot be completed by the usual inductive procedure; the way to complete a consistent second-order theory is to pick its model, and take the complete theory of that model. $\endgroup$ Commented Jul 9, 2021 at 9:32
  • $\begingroup$ @EmilJeřábek: the question doesn't restrict to consistent theories though - that's all I wanted to point out. (I thought we could just complete a theory using Henkin semantics, though I haven't thought this through.) $\endgroup$
    – Harry West
    Commented Jul 9, 2021 at 9:55
  • $\begingroup$ @HarryWest I've addressed the completeness issue above - you're right, I should have been clearer. $\endgroup$ Commented Jul 9, 2021 at 16:31

2 Answers 2

6
$\begingroup$

Here's a monadic example. The second-order theory of the vector space $\mathbb F_2^{\oplus\omega}$ as a vector space over $\mathbb F_2$ is second-order strongly minimal because given a finite subspace $X$ of any model of this theory, any two points outside $X$ are related by an automorphism of the whole space fixing $X.$

There is a subtlety here pointed out by Emil Jeřábek in the comments. For Question 2, where we check strong minimality in ZFC, it is of course true that any automorphism of a subspace extends to the whole space. In ZF, this might not be true, but as Emil suggested we can use the axiom that there are complemented subspaces: $(\forall Y)(\exists Z)$ such that if $Y$ is a subspace then: $Z$ is a subspace with $Y\cap Z=\{0\},$ and $(\forall v)(\exists y\in Y)(\exists z\in Z)(v=y+z).$

This theory contains the second order axiom "($\exists P$) $P$ is a subspace of codimension 2", i.e. $P$ is closed under addition and there exists $v\notin P$ such that every $w\notin P$ satisfies $w+v\in P.$ So it can't have an amorphous model.

$\endgroup$
11
  • $\begingroup$ Interestingly, there can be an amorphous vector space over $\Bbb F_2$. Nice. $\endgroup$
    – Asaf Karagila
    Commented Jul 9, 2021 at 8:29
  • 2
    $\begingroup$ I’m not quite sure I understand how this works. Can you exhibit a monadic second-order sentence that implies “given a finite subspace $X$, any two points outside $X$ are related by an automorphism”? (In ZFC, this is true in any model of the first-order theory of $\mathbb F_2$-linear spaces, but in ZF, it is not, as far as I can tell.) $\endgroup$ Commented Jul 9, 2021 at 9:19
  • 1
    $\begingroup$ On a second thought, the sentence “all subspaces are complemented” should work, as it allows to extend an automorphism of a finite subspace to an automorphism of the whole space. $\endgroup$ Commented Jul 9, 2021 at 9:24
  • 1
    $\begingroup$ @JoelDavidHamkins: right, I just wanted to say that the model we start with should actually have that property. So you can't just take any old vector space. The well-order wasn't supposed to be part of the structure. Hopefully clearer now... $\endgroup$
    – Harry West
    Commented Jul 9, 2021 at 10:48
  • 1
    $\begingroup$ @JoelDavidHamkins: I see what you mean. I've now mentioned that we need to consider an arbitrary model. $\endgroup$
    – Harry West
    Commented Jul 9, 2021 at 11:27
5
$\begingroup$

The answer to both questions seems to be negative. In the language having only equality, let $T$ be any completion of the theory of a set admitting an endless linear order. This property is expressible in a single sentence of second-order logic, $$\exists\leq\ (\leq\text{ is an endless linear order}).$$

This theory is strongly minimal, since any permutation of the domain of any model of this theory is an automorphism, as there is no structure to preserve. All points look alike, even when finitely many other points have been fixed as parameters. So every definable set (using finitely many parameters) is either finite or cofinite.

But this theory can have no amorphous model, since in that model, there would be an endless linear order on the set, and by cutting that order at any point, we would split the set into two infinite sets.

A more to-the-point observation would be that being amorphous is itself expressible in the language of equality in second-order logic. This seems directly to answer the question of the title.

Theorem. There is a sentence in the second-order language of equality that is true in a model if and only if the domain is an amorphous set.

Proof. A set $A$ is amorphous if and only every subset $X\subseteq A$ is either finite or cofinite. A set $X$ is finite if and only if it is isomorphic to a finite ordinal, which is equivalent to saying that it admits a well order with a top element and no limits. This is expressible in second-order logic with equality (needed for anti-symmetry), and so we may also express that the domain is amorphous. $\Box$

Any theory in the language of equality containing the assertion that the domain is not amorphous will be strongly minimal, since any permutation is an automorphism. This seems to provide a counterexample for both questions.

Note that the argument uses full second-order logic, by quantifying over binary relations, and not merely monadic second-order logic, where one quantifies only over sets. So there would seem to be an interesting question remaining concerning monadic second-order logic.

(I wonder whether one can use a similar idea with monadic second-order logic, by aiming to make a theory asserting merely that there could be a structure of a certain kind. By not making the structure part of the model, but only quantified over, you will again have strong minimality. But I don't have a working example for this case.)

$\endgroup$
5
  • $\begingroup$ Alternatively, just say that there exists a function which is injective but not surjective. $\endgroup$
    – Asaf Karagila
    Commented Jul 9, 2021 at 8:18
  • $\begingroup$ Sure, same idea. I think there are many theories that work. But can you find a monadic theory? $\endgroup$ Commented Jul 9, 2021 at 8:20
  • 1
    $\begingroup$ Yes, but the point in my comment is that you get a stronger result. No Dedekind-finite set can be a model of such theory. In contrast, many Dedekind-finite sets can be linearly ordered. (The monadic theory question is interesting.) $\endgroup$
    – Asaf Karagila
    Commented Jul 9, 2021 at 8:21
  • 1
    $\begingroup$ Yes, I agree with that. So the two theories separate amorphous from nonamorphous infinite Dedekind finite. $\endgroup$ Commented Jul 9, 2021 at 8:21
  • $\begingroup$ Ouch, this is pretty embarrassing! I guess I was thinking about monadic second-order logic without realizing it. (Regardless, +1 of course.) $\endgroup$ Commented Jul 9, 2021 at 17:42

You must log in to answer this question.

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