Questions tagged [lo.logic]
first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, theories of truth, truth revision, consistency.
5,135
questions
3
votes
0
answers
51
views
Closely related definitions with and without approximation built-in
Let us say that a (real) function class $A$ has 'approximation built-in' in case for every $f:\mathbb{R}\rightarrow\mathbb{R}$ in $A$ and any $x\in \mathbb{R}$, we can approximate $f(x)$ using only $f(...
12
votes
1
answer
469
views
Is there a useful measure of density of decidable sentences in PA?
Essential undecidability of PA says every complete extension of PA includes a non r.e. set of new "axioms," all undecidable in PA. In that sense lots of sentences of PA are undecidable in ...
13
votes
1
answer
449
views
How much determinacy do you need for second order arithmetic to be as strong as ZFC?
From Wikipedia (I couldn't find the original source):
$\text{ZFC} + \{\text{there are $n$ Woodin cardinals: $n$ is a natural number}\}$ is conservative over $\text{Z}_2$ with projective determinacy.
...
1
vote
0
answers
175
views
Theorem constructing a mathematical structure from a set of internal isomorphisms
I am searching for information about a specific theorem mentioned in the book "Discriminator-algebras: algebraic representation and model theoretic properties" by Heinrich Werner. The ...
6
votes
1
answer
525
views
Does Playfair imply Proclus?
I am interested in the interplay between the Playfair and Proclus Axioms in linear spaces.
By a linear space I understand a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of ...
20
votes
2
answers
1k
views
Non-definability of graph 3-colorability in first-order logic
What is a proof that graph 3-colorability is not definable in first order logic? Where did it first appear?
8
votes
1
answer
200
views
Can totally inhomogeneous sets of reals coexist with determinacy?
A special case of a theorem of Brian Scott (from On the existence of totally inhomogeneous spaces) is that there is a size-continuum set $S\subset\mathbb{R}$ such that if $x,y\in S$ are distinct then $...
4
votes
0
answers
135
views
Do presheaf toposes satisfy the full fan theorem?
Presheaf toposes satisfy LPO and (edit: if over categories with binary products) PAx and countable choice internally, so they automatically satisfy the stable fan theorem (every bar which is the ...
3
votes
1
answer
256
views
Ultra*powers* in the category of structures and elementary embeddings
This is based on a few previous questions.
Can one characterize ultrapowers in the category of L-structures (modeling a fixed complete theory, say) and elementary embeddings?
Previous posts showed ...
13
votes
3
answers
1k
views
Can ultraproducts avoid all "factor structures"?
This came up in the comments to an answer of Joel's. Suppose $\mathcal{M}_i$ ($i\in I$) are elementarily equivalent structures in the same fixed signature and $\mathcal{U}$ is an ultrafilter on $I$. ...
11
votes
1
answer
334
views
Lattices of clones: is 4 worse than 3?
Let $\mathscr{C}_n$ be the lattice of clones on the $n$-element set $\{1,...,n\}$. $\mathscr{C}_2$ is complicated but countable, but $\mathscr{C}_3$ (and all higher lattices) is of size continuum.
...
6
votes
1
answer
539
views
Ultraproducts in the category of structures and elementary embeddings
A previous question on the categorical nature of ultraproducts had great answers, mostly categorically characterizing ultraproducts in the category of $L$-structures and homomorphisms for a fixed ...
8
votes
1
answer
223
views
Reference for precise form of Mostowski: “sets correspond to rooted, well-founded, extensional graphs”?
I’m looking for a reference for a certain precise form of the Mostowski collapse theorem, which I’ve long known as folklore but am having trouble finding in the literature. In lieu of a printed ...
5
votes
1
answer
99
views
Understanding the definition of a (computably / continuously) “transparent” function
The following definitions of a “transparent function” are essentially taken from references [1] (where it is called a “jump operator”), [2] and [3], except that the variation “primitively recursively ...
1
vote
0
answers
136
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{...
17
votes
2
answers
859
views
Do $X$ and $Y$ have the same cardinality if their families of finite subsets do?
Let $X$ and $Y$ be sets. It is undecidable in ZFC whether $2^{|X|} = 2^{|Y|}$ implies $|X| = |Y|$ (in Cohen's original model for ZFC + $\neg$CH, one has $2^{\aleph_0} = 2^{\aleph_1}$). What if we ...
1
vote
1
answer
145
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 ...
4
votes
1
answer
237
views
How to use Meredith’s axiom for classical logic?
I’ve been self-studying axiomatic systems for classical logic for a while. The standard Hilbert/Mendelssohn/Lukasiewicz axiomatizations were a bit tough for me to get used to without using the ...
2
votes
1
answer
146
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 ...
1
vote
0
answers
154
views
Can ordinal definability be defined using no more than one ordinal parameter?
This answer shows that one can indeed define ordinal definable this way:
$\begin{align} \textbf{Define: } & \operatorname {OD} (X) \iff \\& \exists \theta \, \exists \varphi: X= \{y \in V_\...
3
votes
1
answer
243
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{...
3
votes
1
answer
225
views
Does V=HOD prove all kinds of consistent universal hereditary definability?
Is the following a theorem of $\sf ZF+[V=HOD]$?
If $Q$ is a property definable in a parameter free manner, then: $$\operatorname {Con}(\sf ZF + [V=HQD]) \implies V=HQD$$
where $\sf V=HQD$ means:
$$\...
1
vote
1
answer
166
views
Can we state $\sf V=HOD$ using a single ordinal parameter(other than the formula code)?
$\sf V=HOD$ is stated as:
$\forall X \, \exists \theta \, \exists \alpha < \theta \, \exists \varphi : X=\{y \in V_\theta\mid V_\theta\models\varphi(y,\alpha)\}$
This use two ordinal parameters (...
2
votes
0
answers
69
views
A formula which is true in all possibilities for variables in IPL
Let $\mathcal{F}(n, 2^m)$ be an intuitionistic Kripke in Fig. 1, which is formed by the set
$$
\left\{(i, j)\in \omega \times \omega \mid (0 \leq i \leq n-3, 0 \leq j \leq 1) \vee (i= n-2, 0 \leq j \...
3
votes
0
answers
123
views
A class of Kripke frames which preserves validity
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $1\leq s\leq n-2$, the frame $\mathcal{C}_n(s)$ denotes the frame which is ...
3
votes
2
answers
258
views
Is every countable model of ZFC a subset of some parameter free definable pointwise-definable model of ZFC?
Is it consistent with $\sf ZFC + \text{ countable models of } ZFC \text { exist}$, that every countable model of $\sf ZFC$ is a subset of some parameter free definable pointwise-definable model of $\...
6
votes
0
answers
119
views
Detecting uncountable cardinalities, this time with determinacy
By "small cardinality" I mean a Scott cardinality onto which $\mathbb{R}$ surjects ($0$ isn't interesting here). $\mathcal{R}=(\mathbb{R};+,\times,\mathbb{Z})$ is the field of real numbers ...
6
votes
1
answer
197
views
Preserve validity between the two Kripke frames
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $n \geq 1$, let $\mathcal{C}_n$ denote the frame which is shown in Fig.1. ...
1
vote
0
answers
114
views
Logic which depends on the point of view / perspective? (Semantic space of logic)
I am not sure if this question is appropriate for MO, since I have only a basic understanding of Boolean logic, and am maybe not qualified to ask questions beyond that, but still I will try to write ...
7
votes
1
answer
225
views
Formulas that are valid simultaneously in a power set Boolean algebra $B$ and the 2-element Boolean algebra $\mathbf2$ [duplicate]
Note 1. Early I posted a related question Set-theoretic tautologies. But the answer did not contain any concrete references to the literature. So I posted this, more precisely formulated question, ...
1
vote
1
answer
117
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 ...
13
votes
1
answer
592
views
Can $L$ be defined without parameters?
If we omit parameters in the definition of $L$ would the result still be $L$?
That is, we define a successor stage $L_{\alpha+1}$ in the constructible universe $L$, without including parameters; as:
$...
5
votes
1
answer
440
views
How to solve this exercise about large countable ordinals?
In this note (Notes on Higher Type ITTM-recursion, 2021) written by Philip Welch, I'm trying to solve exercise 3.5(i), but I don't know how to solve it.
The problem is: assume that $L_{\gamma_0}<_{...
4
votes
1
answer
215
views
Comparing bornologies for cardinal characteristics via Borel maps
This question is "take 2" of this older one, following a suggestion of Francois Dorais. Consider the following bornologies $\mathbb{D},\mathbb{E}$ on the set $\mathcal{N}$ of all functions ...
5
votes
2
answers
262
views
Is the usual enumeration of $\mathsf{PA}$ "minimal for consistency strength"?
This question is about a technical imprecision which is easily avoidable but whose details I'd like to understand better. When we refer to "the consistency strength of $\mathsf{PA}$" (say) ...
0
votes
1
answer
142
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 ...
17
votes
1
answer
414
views
End-extension which Mostowski collapses a fake well ordering
Assume $\alpha$ is admissible, $R\in L_\alpha$ is a linear order that don't have any infinite descending chain in $L_\alpha$. Is there always an end extension $M$ of $L_\alpha$, such that $M\vDash KP$ ...
6
votes
1
answer
185
views
Multiplicative group of a ring as a morphism of theories
On nlab I read
For instance, there is a morphism of theories from the theory of commutative rings to the theory of abelian groups which sends a ring to its multiplicative group of units, but this is ...
1
vote
0
answers
130
views
Infinite Steiner systems
Let $\kappa<\lambda$ be cardinals where $\lambda \geq \aleph_0$ and $\kappa>1$. Is there necessarily a set ${\cal S}\subseteq {\cal P}(\lambda)$ with the following properties?
${|\cal S}| > ...
1
vote
1
answer
126
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_{...
1
vote
0
answers
119
views
Can every set be ordinal definable?
From Wikipedia:
OD is not necessarily transitive, and need not be a model of ZFC.
This obviously means that, assuming ZFC is consistent, there is a model $M \models \mathrm{ZFC}$ so that $\mathrm{OD}...
1
vote
0
answers
90
views
What computable pseudo-ordinals are there with initial segment $\omega_1^{CK}(1+\eta+1)$?
The notion of a “computable pseudo-ordinal”, i.e. a computable linear order with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the definitive ...
0
votes
1
answer
107
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 $\...
5
votes
0
answers
322
views
How to study formal logic without formally using the notion of a set?
I have recently begun curious in set theory, and when I researched this subject I saw that all axiomatizations of set theory, such as ZFC and NBG, are expressed in the language of first order logic. ...
2
votes
1
answer
198
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 ...
1
vote
1
answer
84
views
Intersection of (relativized/preimage) measure 0 with every hyperarithmetic perfect set
Given a perfect tree $T$ on $2^{<\omega}$ viewed as a function from $2^{<\omega}$ to $2^{<\omega}$ define the measure of a subset of $[T]$ to be the measure of it's preimage under the usual ...
2
votes
1
answer
300
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 ...
2
votes
1
answer
95
views
Baur-Monk quantifier elimination (BG-invariants in 1-free variable)
$\DeclareMathOperator\Inv{Inv}$Baur-Monk quantifier elimination implies that a sentence in the language of modules is a combination of BG invariant statements.
A BG invariant sentence is a boolean ...
2
votes
1
answer
132
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}$...
2
votes
1
answer
122
views
Question on Baur-Monk quantifier elimination for modules
Baur-Monk quantifier elimination theorem asserts that any formula in the language of modules is modulo the theory a boolean combination of BG-Invariants and positive primitive formulas. However, in p....