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.

Filter by
Sorted by
Tagged with
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(...
Sam Sanders's user avatar
  • 3,901
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 ...
Colin McLarty's user avatar
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. ...
Christopher King's user avatar
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 ...
Pablo's user avatar
  • 119
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 ...
Taras Banakh's user avatar
  • 40.8k
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?
Leo Marcus's user avatar
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 $...
Noah Schweber's user avatar
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 ...
saolof's user avatar
  • 1,823
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 ...
Pteromys's user avatar
  • 151
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$. ...
Noah Schweber's user avatar
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. ...
Noah Schweber's user avatar
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 ...
Pteromys's user avatar
  • 151
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 ...
Peter LeFanu Lumsdaine's user avatar
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 ...
Gro-Tsen's user avatar
  • 29.9k
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{...
Zuhair Al-Johar's user avatar
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 ...
Salvo Tringali's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
PW_246's user avatar
  • 184
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 ...
Zuhair Al-Johar's user avatar
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_\...
Zuhair Al-Johar's user avatar
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{...
Zuhair Al-Johar's user avatar
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: $$\...
Zuhair Al-Johar's user avatar
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 (...
Zuhair Al-Johar's user avatar
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 \...
mahu's user avatar
  • 63
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 ...
mahu's user avatar
  • 63
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 $\...
Zuhair Al-Johar's user avatar
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 ...
Noah Schweber's user avatar
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. ...
mahu's user avatar
  • 63
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 ...
mathoverflowUser's user avatar
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, ...
Victor Makarov's user avatar
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 ...
Zuhair Al-Johar's user avatar
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: $...
Zuhair Al-Johar's user avatar
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}<_{...
Reflecting_Ordinal's user avatar
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 ...
Noah Schweber's user avatar
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) ...
Noah Schweber's user avatar
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 ...
Zuhair Al-Johar's user avatar
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$ ...
Reflecting_Ordinal's user avatar
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 ...
Arshak Aivazian's user avatar
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}| > ...
Dominic van der Zypen's user avatar
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_{...
Zuhair Al-Johar's user avatar
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}...
Binary198's user avatar
  • 704
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 ...
Keshav Srinivasan's user avatar
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 $\...
Zuhair Al-Johar's user avatar
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. ...
Shthephathord23's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Peter Gerdes's user avatar
  • 2,551
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 ...
Zuhair Al-Johar's user avatar
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 ...
Eladio Vuente's user avatar
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}$...
Zuhair Al-Johar's user avatar
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....
Eladio Vuente's user avatar

1
5 6
7
8 9
103