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
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 ...
Mohammad Golshani's user avatar
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 ...
Tim Campion's user avatar
  • 60.6k
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)$? (...
Tim Campion's user avatar
  • 60.6k
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$ ...
Noah Schweber's user avatar
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-...
Jonas Gomes's user avatar
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 $\...
Mohammad Golshani's user avatar
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, ...
Mohammad Golshani's user avatar
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 ...
Mohammad Golshani's user avatar
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 ...
Nate Eldredge's user avatar
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 \...
Danny Nguyen's user avatar
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 ...
Mohammad Golshani's user avatar
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 ...
Zhen Lin's user avatar
  • 14.9k
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 ...
user avatar
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 $\...
Kameryn Williams's user avatar
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 ...
Mohammad Golshani's user avatar
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 $(\...
Monroe Eskew's user avatar
  • 18.1k
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 ...
Simon Henry's user avatar
  • 39.9k
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 ...
Mohammad Golshani's user avatar
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 ...
Richard Rast's user avatar
  • 1,969
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. ...
Payam Seraji's user avatar
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 ...
András Salamon's user avatar
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 ...
M Carl's user avatar
  • 335
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}^{...
Trevor Wilson's user avatar
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 "...
Timothy Chow's user avatar
  • 78.1k
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 ...
mmw's user avatar
  • 171
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).
Colin McLarty's user avatar
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 ...
Kaveh's user avatar
  • 5,362
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 ...
Garabed Gulbenkian's user avatar
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 ...
Trevor Wilson's user avatar
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 ...
Trevor Wilson's user avatar
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 ...
Rob Arthan's user avatar
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 ...
Yrogirg's user avatar
  • 443
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 ...
domotorp's user avatar
  • 18.3k
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). ...
boumol's user avatar
  • 788
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 ...
Mirco A. Mannucci's user avatar
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 ...
Tobias Neukom's user avatar
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 ...
day's user avatar
  • 179
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 ...
user avatar
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 ...
user avatar
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 ...
Eran's user avatar
  • 649
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 ?
user avatar
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 ...
Zirui Wang's user avatar
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_{\...
Iian Smythe's user avatar
  • 3,001
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 ...
Joël's user avatar
  • 25.7k
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 ...
Qfwfq's user avatar
  • 22.7k
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 ...
Thomas Benjamin's user avatar
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 ...
user avatar
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 ...
Mikhail Katz's user avatar
  • 15.1k
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}$?
Dominic van der Zypen's user avatar
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 ...
Pablo's user avatar
  • 61

1
44 45
46
47 48
103