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,133
questions
7
votes
0
answers
205
views
Possible cofinalities of cuts of ultraproducts
Suppose $\kappa$ is a regular cardinal, $\bar{\mu}=(\mu_i: i<\kappa)$ is an increasing sequence of regular cardinals ($>\kappa$) and set
$pcut(\bar \mu)=\{ (\lambda_1, \lambda_2):$ for some ...
7
votes
0
answers
134
views
When are two pregeometries equivalent?
Some model theorists / combinatorial geometers like to think about pregeometries (matroids with a weak finiteness condition) associated to first-order theories. But the usual way of constructing a ...
7
votes
0
answers
211
views
Automorphisms that preserve every algebraically closed set
Let $T$ be a theory, and $A$ be an algebraically closed set. Let $L$ be the lattice of algebraically closed subsets of $A$. Can one understand the kernel of the natural map $\chi: Aut(A) \to Aut(L)$? (...
7
votes
0
answers
201
views
Does Solovay's $\Sigma$-construction preserve "niceness"?
Suppose I have two forcing notions $\mathbb{P}$ and $\mathbb{Q}$, and a $\mathbb{Q}$-name $\nu$ for a real. Let $G$ be $\mathbb{P}$-generic, and suppose $r$ is a real in $M[G]$ such that for some $H$ ...
7
votes
0
answers
370
views
Sheafs in O-minimal Structures
Let $\mathcal{N} = (N, <, \ldots)$ be an o-minimal structure and let $X \subset N^m$ be a definable set. Following the procedure stablished by Edmundo, Jones and Peatfield in "Sheaf cohomology in o-...
7
votes
0
answers
137
views
Natural theories for the failure of gap-1 transfer principle
The gap-1 transfer principle says that the transfer principle $(\kappa^+, \kappa) \to (\lambda^+, \lambda)$ holds for all infinite cardinals $\kappa, \lambda.$
It is known that for some sentence $\...
7
votes
0
answers
155
views
Woodin's theorem about the existence of sharps for the Chang's model
In The sharp for the Chang model is small, Mitchell has stated a result of Woodin about the Chang's model, and he has produced a result using much weaker assumptions.
As it is stated in the paper, ...
7
votes
0
answers
243
views
Tree property using side conditions
The following problems were asked during the high and low forcing workshop:
Question 1. Can one force tree property at $\kappa^{++}$ for $\kappa$ singular using side conditions?
Question 2. Can one ...
7
votes
0
answers
166
views
Choice and the Baire property in non-separable complete metric spaces
It's known to be consistent with ZF+DC that every subset of $\mathbb{R}$ has the Baire property (BP). (E.g. Shelah's model). If so, then every subset of every complete separable metric space has ...
7
votes
0
answers
206
views
Complexity of integer programming with added predicates
A classical theorem in Integer Programming by Lenstra says that any integer system
$$A x \le b$$
can be solved in polynomial time, where $A \in \mathbb{Z}^{m \times n}, x \in \mathbb{Z}^n, b \in \...
7
votes
0
answers
240
views
Adding minimal subsets to $\aleph_\omega$
Given a cardinal $\kappa,$ recall that $X \subset \kappa$ is called fresh (over $V$), if $X \notin V,$ but $X \cap \alpha \in V$ for all
$\alpha < \kappa.$
Question. Is it consistent that there ...
7
votes
0
answers
129
views
Finitely presented algebras with isomorphic semilattices of congruences
Let $\mathbb{T}$ be a finitary algebraic theory. For each $\mathbb{T}$-algebra $A$, let $Q (A)$ be the join semilattice of finitely generated congruences on $A$. There is an evident pushforward ...
7
votes
0
answers
603
views
Proving Richardson's theorem for constants
(I asked this a little over 3 months ago on math.SE, and when I initially re-asked here, no one had responded there. $\:$ After I re-asked here, Eric Towers responded there, since I had forgotten to ...
7
votes
0
answers
168
views
Sacks minimality without choice
The usual argument for the minimality result for Sacks forcing uses choice.
Theorem (Sacks): Let $s \subseteq \mathbb S_\kappa$ be generic for the forcing to add a Sacks subset to $\kappa$, where $\...
7
votes
0
answers
245
views
$V$ as a $HOD$ of its class generic extension
By an old result of Roguski, The theory of the class $HOD$, any model $V$ of $ZFC$ has a class generic extension $V[G]$ such that $HOD$ of $V[G]$ equals $V$.
This result is also stated and generalized ...
7
votes
0
answers
271
views
A strengthening of Chang's conjectures
In the Handbook of Set Theory, Foreman has (essentially) the following proposition (3.9):
Suppose $\kappa_n>...>\kappa_0$ and $\lambda_n>...>\lambda_0$ are regular cardinals and $(\...
7
votes
0
answers
280
views
How "small" can an ordinal be made by forcing?
I know that forcing essentially does not change the ordinals, but by small I mean in comparison with other ordinals whose definition might not be stable under forcing, like the smallest uncountable ...
7
votes
0
answers
195
views
$\alpha$-minimal degrees for singular $\alpha$
An important question in $\alpha$-recursion theory is whether there is a minimal $\alpha$-degree at $\alpha=\aleph_\omega.$
Question 1. Who first introduced the above question, and where can I find ...
7
votes
0
answers
132
views
O-Minimal sentences in $L_{\omega_1,\omega}$?
Is there any meaningful sense in which we can talk about o-minimal sentences of $L_{\omega_1,\omega}$? I can give a first attempt, easily; given a countable fragment $F$ and a sentence $\Phi$ in that ...
7
votes
0
answers
461
views
Godel's second incompleteness theorem for non-r.e. theories
R. Jeroslow in this paper proves that a non-recursively enumerable theory whose set of theorems is $\Delta_2$-definable may prove consistency of itself
but it can not prove 2-consistency of itself.
...
7
votes
0
answers
390
views
Universal anti-Horn classes?
Is there published work about universal anti-Horn classes?
Anti-Horn formulas are also sometimes known as dual Horn.
See also related question Is there any research of universal algebras axiomatized ...
7
votes
0
answers
270
views
What is the Turing degree of $\mathbb{C}_{exp}$?
Let $\mathbb{C}_{exp}$ be the theory of the complex numbers in the language of exponential rings. I am interested in the Turing degree of $\mathbb{C}_{exp}$. As the natural numbers are definable in ...
7
votes
0
answers
237
views
Countable choice in $L(\mathbb{R}^*_G)$
Let $\lambda$ be a singular strong limit cardinal and let $G \subset \text{Col}(\omega,\mathord{<}\lambda)$ be a $V$-generic filter. Let $\mathbb{R}^*_G = \bigcup_{\alpha < \lambda} \mathbb{R}^{...
7
votes
0
answers
248
views
When is a reduction not a reduction?
Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of "...
7
votes
0
answers
248
views
cut-elimination for infinitary logic
Takeuti (1987, 223) deduces a cut-elimination theorem for infinitary logic from the corresponding soundness-and-completeness theorems. However, is there a way to adapt the basic Gentzen-style ...
7
votes
0
answers
348
views
What is known of the reverse math of Riemann-Roch?
I hope this is not too trivial, but I think this may be well known to someone (not me).
7
votes
0
answers
293
views
Feasible Type Theories
I am looking for references about efficient type theories,
efficiency in the sense of computational complexity,
and type theory in the sense of Martin-Lof's type theories.
Has there been any studies ...
7
votes
0
answers
601
views
A question about Paraconsistent Set Theory and the Continuum Hypothesis
In question No.134351 it is asserted that there exists a Paraconsistent Set Theory in which the
Continuum Hypothesis (CH) is disproved. I would like to know more about this theory, which I will
call ...
7
votes
0
answers
296
views
Infinity-Borel sets in ZFC
The notion of an $\infty$-Borel set of reals is useful in the study of AD. Under ZFC it becomes trivial: every set of reals is $\infty$-Borel. However, the notion of an $\infty$-Borel code is still ...
7
votes
0
answers
377
views
Sets of reals amenable to each L[x]
If $A$ is a set of reals such that $A \cap L[x] \in L[x]$ for each real $x$, is there a real $z$ such that $A \cap L[x] \in OD_z^{L[x]}$ for a cone of $x$?
This can be proved under the Axiom of ...
7
votes
0
answers
263
views
Problem with Shelah and Stern's paper on the Hanf number of the theory of Banach spaces
I have been trying to understand "The Hanf number of the first order theory of Banach spaces" by Shelah and Stern (Trans. AMS 244 (1978) 147-241). They construct a normed space $M$ from a Hilbert ...
7
votes
0
answers
1k
views
Is there a finite-dimensional vector space whose dimension cannot be found? [closed]
Is there a finite-dimensional vector space whose dimension cannot be found? Assume, we have somehow constructed a vector space whose dimension is finite, but yet unknown. Is there always an algorithm ...
7
votes
0
answers
2k
views
Is there a chess position equivalent to the Collatz conjecture?
Suppose we have an infinite board with a finite number of chess pieces. The question is whether white can checkmate black (without the after 50 moves it is a draw rule). Can you give an explicit ...
7
votes
0
answers
1k
views
Undecidability degree of some elementary theories (two equivalence relations, ...)
I have a question about some results in the paper
I. A. Lavrov. Effective inseparability of the sets of identically true formulae and finitely refutable formulae for certain theories (in Russian). ...
6
votes
9
answers
7k
views
Ultrainfinitism, or a step beyond the transfinite
Cantor has, in the immortal words of D. Hilbert, given all of us a paradise (or perhaps, I would rather say, a great vacation spot), the TRANSFINITE.
$\aleph_0, \aleph_1,\aleph_2\dots$
the lists ...
6
votes
6
answers
2k
views
Formal proof of Con(ZFC) => Con(ZFC + not CH) in ZFC
Is it possible to prove $Con(ZFC) \rightarrow Con(ZFC + \neg CH)$ purely within ZFC? To prove this (using forcing) one seems to need a countable transitive model of ZFC. The texts I am reading avoid ...
6
votes
4
answers
10k
views
About the proof of the proposition "there exists irrational numbers a, b such that a^b is rational"
What does the classical proof of the proposition "there exists irrational numbers a, b such that $a^b$ is rational" want to reveal? I know it has something to do with the difference between classical ...
6
votes
5
answers
1k
views
How to tell a paradox from a "paradox"?
Russell's paradox showed that naive set theory leads to a contradiction. This was something that was taken seriously and caused a lot of work.
Now, Banach–Tarski paradox is arises from a result that a ...
6
votes
5
answers
2k
views
Zermelo-Frankel set theory for algebraists
$\DeclareMathOperator\Var{Var}\DeclareMathOperator\CRings{CRings}\DeclareMathOperator\Grp{Grp}\DeclareMathOperator\Sets{Sets}$I'm not a logician/set theorist, and I have some questions on set theory ...
6
votes
7
answers
5k
views
Compactness Theorem for First Order Logic
Hi all,
I am interested in proofs without using Goedel's completeness theorem.
Does anyone have a reference to a proof of this theorem that uses Skolem Functions?
How come Enderton's (Introduction to ...
6
votes
5
answers
2k
views
What axioms are stronger than the Axiom of choice?
What other axioms in set theory are stronger than AC ? I mean what are those axioms that will imply AC ?
6
votes
4
answers
2k
views
Why is Cohen's result insufficient to settle CH?
OK, Cohen has constructed a model in which both ZFC and ~CH are true. Isn't this model an answer to the continuum problem? Hasn't he showed that it is indeed possible to construct a set with ...
6
votes
3
answers
451
views
Can every $\mathcal{L}_{\omega_1,\omega}$ formula be expressed as a type? What about canonical forms?
If $\mathcal{L}$ is a countable, first-order language, it is easy to see that every $n$-type $p$ (over $\emptyset$) can be expressed as an $\mathcal{L}_{\omega_1,\omega}$-formula, namely $\bigwedge_{\...
6
votes
5
answers
3k
views
A meta-mathematical question related to Hilbert tenth problem
I am reading Bjorn Poonen's very nice survey on Hilbert's Tenth problem
(http://www-math.mit.edu/~poonen/papers/uniform.pdf), and while I believe I understand the mathematics well, I have widespread ...
6
votes
3
answers
1k
views
Is there an "undecided" assertion of which a proof that it's not undecidable is known?
Just a curiosity:
Is there an assertion of which a proof (formalizable, say, in ZFC) is not known but a proof that it's not undecidable (in ZFC) is known?
Edit: after the comments, I think the ...
6
votes
3
answers
3k
views
The Lucas argument vs the theorem-provers -- who wins and why?
In his paper, "Minds, Machines and Gödel", J.R. Lucas writes the following:
Gödel's theorem [First Incompleteness Theorem, that is—my comment] must apply to cybernetic machines, because it is of ...
6
votes
4
answers
1k
views
Is the theory of incidence geometry complete?
Consider the basic axioms of planar incidence geometry, which allow us to speak of in-betweeness, collinearity and concurrency. These axioms per se are not complete, since for example, Desargues ...
6
votes
5
answers
2k
views
Standard models of N and R: An Alice/Bob approach
This is a question about a comment in a recent publication by Roman
Kossak. Kossak wrote:
"Nonstandardness in set theory has a different nature. In
arithmetic, there is one intended object of ...
6
votes
1
answer
1k
views
Countable group with uncountable number of subgroups $< 2^{\aleph_0}$ [duplicate]
Is it consistent that there is a countable group $G$ such that the cardinality of the set of subgroups of $G$ is uncountable, but strictly less than $2^{\aleph_0}$?
6
votes
2
answers
1k
views
What are the models of Peano Arithmetic plus the negation of the corresponding Gödel sentence like?
Since the Godel sentence for PA (G henceforth) is independent of PA, if PA is consistent, so is PA plus not-G. Thus, since PA is a first-order theory, if PA is consistent, PA plus not-G has some ...