Questions tagged [infinitary-logic]
The infinitary-logic tag has no summary.
30 questions
6 votes
1 answer
361 views
Measuring subsets of a cardinal definable in infinitary logic
Fix an infinite regular cardinal $\kappa$. One can define the $\Sigma_\alpha$ ($\Pi_\alpha$, $\Delta_\alpha$) $\mathcal{L}_{\kappa, \omega}$-formulae for $\alpha < \kappa$ analogously to the ...
- 2,033
14 votes
1 answer
556 views
Infinitary logic at singular cardinals
One of the (many) applications of pcf theory given by Shelah in his book Cardinal Arithmetic is that whenever $\lambda$ is a singular cardinal of cofinality at least $\aleph_2$, there are structures $...
- 7,487
6 votes
1 answer
322 views
Equivalence of models in infinitary logic
In finite model theory we work a lot with a notion weaker than isomorphism, the k-equivalence. Given two structures of the same signature $M$ and $N$, we say that $M =_k N$ if they satisfy the same ...
- 495
4 votes
0 answers
210 views
Infinitary provability logics
For $A$ a countable admissible set, let $\mathcal{L}_A=\mathcal{L}_{\infty,\omega}\cap A$ be the fragment of infinitary first-order logic living inside $A$. Let $\mathsf{PA}_A$ be the following $\...
- 19.3k
11 votes
1 answer
744 views
Infinitary logics and the axiom of choice
Suppose we want to enhance ZF by allowing for infinitary formulas instead of just first-order ones in our axiom schema of separation and/or replacement. It seems that we don't need much power in our ...
- 5,005
1 vote
0 answers
180 views
Must models of the following theory satisfying opposing infinitary sentences, satisfy opposing finitary sentences?
This is a follow-up to posting titled "Is this theory finitary first order complete?" Recall the theory presented at that posting. Replace the size axiom by the following: $\textbf{...
- 13k
1 vote
1 answer
190 views
Are there strong set theories written in infinitary language, that are finitary FOL complete?
Are there set theories that extend some complete infinitary language $\mathcal L_{\kappa, \lambda}$, prove all axioms of $\sf ZFC$, and are finitary $\textbf{FOL}$ complete? That is, every sentence in ...
- 13k
2 votes
1 answer
227 views
Is this theory finitary first order complete?
If we coin a theory in $\mathcal L_{\omega_1, \omega}$ that begins with constructing pure true well founded finite sets, then the set of all true well founded hereditarily finite sets, then builds up ...
- 13k
4 votes
1 answer
343 views
Is ZF + Def a conservative extension of ZFC+HOD? If not, what are counter-examples?
$\sf ZF + Def$ is the theory that extends $\mathcal L(=,\in)_{\omega_1,\omega}$ with axioms of $\sf ZF$ (written in $\mathcal L(=,\in)_{\omega, \omega}$) and the axiom of definability:- $\textbf{...
- 13k
1 vote
0 answers
69 views
Can generalization of non-redundant construction in $V_\omega$ be consistent?
The following posting is along the general line of thought presented in this earlier posting titled "Is it possible to derive the rules of set theory as transfers from the pure finite set world, ...
- 13k
1 vote
1 answer
182 views
Are there second (or higher) order infinitary logic languages? References?
Reading on Infinitary languages I'm only seeing first order infinitary languages $\mathcal L_{\kappa, \lambda}$, i.e. in all of these languages no quantification over predicate and function symbols is ...
- 13k
1 vote
1 answer
166 views
Is bounded-$\mathcal L_{\omega_1,\omega_1}$ significantly different from $\mathcal L_{\omega_1,\omega_1}$?
Take the language $\mathcal L(=,\in)_{\omega_1,\omega_1}$, if we restrict infinite quantification strings, i.e. of the forms $``(\forall v_i)_{i \in \omega}"; ``(\exists v_i)_{i \in \omega}"$, to ...
- 13k
0 votes
1 answer
189 views
How do these two principles of Foundation written in $\mathcal L_{\omega_1,\omega}$ compare?
This comes in continuation to posting titled "Can Foundation be captured for some $\mathcal L_{\omega_1, \omega}$ theories?". Here, an attempt at a stronger notion of Foundation, yet ...
- 13k
1 vote
1 answer
182 views
Can we have ZF + Definability + True Foundation + True Finiteness? Can it be Categorical?
Lets extend $\mathcal L_{\omega_1, \omega_1}$ with axioms of equality and of: $\sf ZF + Definability+Ture$-$\sf Foundation+True$-$\sf Finiteness $ Where $\sf ZF$ is written, as usual, in $\mathcal L_{...
- 13k
0 votes
1 answer
151 views
Can Foundation be captured for some $\mathcal L_{\omega_1, \omega}$ theories?
This posting is a continuation to an earlier one titled "Can Foundation be captured in $\mathcal L_{\omega_1, \omega}$ ?" It appears that capturing foundation is problematic at every $\...
- 13k
2 votes
1 answer
271 views
Can Foundation be captured in $\mathcal L(\omega_1,\omega)$?
Working in $\mathcal L_{\omega_1, \omega}$, can Foundation be captured? My idea is to formalize a theory where all of its models are the well founded pointwise definable models of $\sf ZFC$. I attempt ...
- 13k
2 votes
1 answer
355 views
Is this theory of well founded countable sets formalized in infinitary logic, complete and categorical?
Working in $\mathcal L_{\omega_1, \omega_1}$, add symbol $=$ with its axioms; add symbol $\in$ and axiomatize: $\textbf{Extensionality: } \forall x \forall y : \forall z (z \in x \leftrightarrow z \in ...
- 13k
2 votes
1 answer
190 views
Does adding definability axiom expressed in infinitary language to ZF, let all models be pointwise definable?
This posting is generally related to a prior posting titled "Are all constructible from below sets parameter free definable?" If we work in infinitary language $\mathcal L_{\omega_1, \omega}$...
- 13k
2 votes
1 answer
286 views
End elementary extension in infinitary logic of some $L_\alpha$ producing a $L_\beta$
Let $L_\alpha$ be some admissible level of the constructible hierarchy and $M \supseteq L_\alpha$ an extension of $L_\alpha$. I am looking for conditions under which $M \simeq L_\beta$. It is not ...
- 531
7 votes
1 answer
292 views
Complexity of infinitary satisfiability, part 2
This question is a follow-up to this one, which was almost entirely answered by Farmer S. Throughout, we work in $\mathsf{ZFC+V=L}$. Given a "pre-admissible" (= admissible or limit of ...
- 19.3k
5 votes
1 answer
329 views
What does the Ehrenfeucht-Fraïssé game on structures with infinitely many relations tell us?
EF-games are typically presented for structures with finitely many relations, and if you want to extend them to structures with functions, you can relationalize the functions. This seems to be to ...
- 489
-3 votes
1 answer
199 views
Can having no more than countably many classes, be inferred from, having every class being countable?
In a theory having proper classes it won't be that easy to phrase how many classes we have in comparison to the number of elements of some class. Here, I'll adopt the following method: We'd say that: ...
- 13k
1 vote
1 answer
210 views
Can ZFC + Classes + definability rule manage to prove all classes countable?
Working in bi-sorted $L_{\omega_1,\omega} (=, \in)$, if we write $\sf ZFC + Classes$ as it is; i.e., in bi-sorted $L_{\omega, \omega} (=,\in)$, and add the following definability rule written in bi-...
- 13k
6 votes
1 answer
291 views
Sharp Craig interpolation theorem for $L_{\omega_1 \omega}$
I’d like to know if a sharp version of Craig’s interpolation theorem for $L_{\omega_1 \omega}$ is already known or exists in the literature. By a “sharp” version of this theorem, I mean something like ...
- 203
10 votes
1 answer
547 views
When do infinitary compactness numbers exist?
For a logic $\mathcal{L}$, let the compactness number of $\mathcal{L}$ (if it exists) be the least $\kappa$ such that every $(<\kappa)$-satisfiable $\mathcal{L}$-theory is satisfiable. Note that ...
- 19.3k
8 votes
0 answers
393 views
On undefinability of well-orderings in $L_{\omega_1,\omega}$
It is a well-known theorem that well-orderings can not be characterized in $L_{\omega_1,\omega}$. In particular, if $\psi$ is an $L_{\omega_1,\omega}$-sentence in a vocabulary $\tau$ that contains a ...
- 2,972
3 votes
1 answer
340 views
The Strong Compactness Cardinal of $n$-th Order Logic
I was reading Kanamori's The Higher Infinite, when I came across the fact that for any extendible cardinal $\kappa$ and any $\mathcal{L}_{\kappa,\kappa}^n$-theory $T$, $Sat(T)\Leftrightarrow \forall t\...
- 695
4 votes
1 answer
530 views
How expressive can $\mathcal{L}_{\kappa,\kappa}$ be?
(Note that the logic systems described in this question only refer to logic systems restricted to the language $\in$) 1. Can $\mathcal{L}_{\kappa,\kappa}$ express $n$-th order finitary logic? It is ...
- 1,260
2 votes
1 answer
431 views
Elementary extensions of infinitary languages
Let $R_\alpha$ be the $\alpha$-th infinite regular ordinal. This question assumes AC, so the following is true: $$R_\alpha=\left\{ \begin{array}{ll} \omega_\alpha & \alpha=\kappa+n\;\mathrm{...
- 1,260
12 votes
1 answer
472 views
Models with few types in infinitary logics
Let $\mathcal{L}_{\kappa \lambda}$ denote the infinitary logic that allows conjunction of less than $\kappa$-many formulas and simultaneous quantification of less than $\lambda$-many variables. It is ...
- 4,345