By "logic" I mean the definition gotten by removing the relativization property from "regular logic" — see e.g. Ebbinghaus/Flum/Thomas — and adding the condition that for every language $\Sigma\in\mathsf{HF}$ the set of sentences $\mathcal{L}[\Sigma]$ is also in $\mathsf{HF}$ (where $\mathsf{HF}$ is the set of hereditarily finite sets) so that we can talk about computability-theoretic properties appropriately.
The second part of Lindström's theorem states the following:
Suppose $\mathcal{L}$ is a regular logic containing $\mathsf{FOL}$ which has the downward Löwenheim–Skolem property for individual sentences (dLS) and an r.e. set of validities. Then $\mathcal{L}\equiv\mathsf{FOL}$.
The argument is very similar to the proof of the first part (which uses compactness in place of r.e.-ness), and crucially uses both the relativization property of regular logics and Fraïssé's characterization of elementary equivalence. We can drop relativization and want to keep the conclusion of the first part of Lindstrom's theorem if we strengthen dLS substantially. I'm curious if this change also salvages the second part of Lindström's theorem. I suspect it doesn't, but I don't immediately see a counterexample.
Question: Is there a (necessarily non-regular) logic $\mathcal{L}$ strictly stronger than $\mathsf{FOL}$ with the following properties?
The set of $\mathcal{L}$-validities is r.e.
$(\mathsf{dLS}^+)$ There is a computable function sending each pair $(\Sigma,\varphi)$ with $\Sigma\in\mathsf{HF}$ and $\varphi\in\mathcal{L}[\Sigma]$ to a pair $(\Pi,\psi)$ such that
$\Sigma\subseteq\Pi\in\mathsf{HF}$ and $\psi\in\mathcal{L}[\Pi]$,
the $\Sigma$-reducts of models of $\psi$ are exactly the $\Sigma$-structures satisfying $\varphi$, and
the model class of $\psi$ is closed under taking substructures.
The property $(\mathsf{dLS}^+)$ is an effective version of what I called "internal dLS" in an earlier question; that question also sketches how the Łoś–Tarski argument shows that no logic proper strengthening $\mathsf{FOL}$ has both this and the compactness property, without using Fraïssé's theorem or assuming relativization. Skolemization establishes that $\mathsf{FOL}$ has $(\mathsf{dLS}^+)$, and I don't offhand know of any natural examples of logics with the downward Löwenheim–Skolem property for which even the non-effective version of $(\mathsf{dLS}^+)$ fails.
