Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

36
votes
0answers
2k views

Concerning the various proofs from the axiom of choice that R^3 admits of surprising geometrical decompositions into circles, skew lines and so on: can we prove in any instance that there are no Borel such decompositions? Or that AC is required?

This question follows up on a comment I made on Joseph O'Rourke's recent question, one of several questions here on mathoverflow concerning surprising geometric partitions of space using the axiom of ...
32
votes
0answers
1k views

Peano Arithmetic and the Field of Rationals

In 1949 Julia Robinson showed the undecidability of the first order theory of the field of rationals by demonstrating that the set of natural numbers $\Bbb{N}$ is first order definable in $(\Bbb{Q}, +,...
28
votes
0answers
840 views

Where do uncountable models collapse to?

Suppose $T$ is a complete first-order theory (in an finite, or at worst countable, language). Given any model $\mathcal{M}\models T$ of cardinality $\kappa$, we can ask whether $\mathcal{M}$ can be ...
25
votes
0answers
1k views

Supercompact and Reinhardt cardinals without choice

A friend of mine and I ran into the following question while reading about proper forcing, and have been unable to resolve it: Definition. A cardinal $\kappa$ is supercompact if for all ordinals $\...
24
votes
0answers
538 views

Can one divide by the cardinal of an amorphous set?

This question arose in a discussion with Peter Doyle. It is provable in ZF that one can divide by any positive finite cardinal $k$: if $X \times \{1,\ldots,k\} \simeq Y \times \{1,\ldots,k\}$ then $X ...
24
votes
0answers
481 views

Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them. Define the set $\mathcal{E}$ of ...
24
votes
0answers
1k views

Defining $\mathbb{Z}$ in $\mathbb{Q}$

It was proved by Poonen that $\mathbb{Z}$ is definable in the structure $(\mathbb{Q}, +, \cdot, 0, 1)$ using $\forall \exists$ formula. Koenigsmann has shown that $\mathbb{Z}$ is in fact definable by ...
21
votes
0answers
435 views

CH and automorphisms of ultrapowers of $\mathbb{Z}$ and $\mathbb{R}$

Notation and motivation. Given an algebraic structure $\mathbb{M}$ of cardinality at most the continuum and with countably many operations, and a nonprincipal ultrafilter $\cal{U}$ on a countably ...
21
votes
0answers
639 views

Relative null-ness

Here, "measure" always means Lebesgue measure on $\mathbb{R}$. This question is partly motivated by my answer https://math.stackexchange.com/questions/1444498/is-there-a-categorizaiton-system-for-null-...
20
votes
0answers
502 views

Density of first-order definable sets in a directed union of finite groups

This is a generalization of the following question by John Wiltshire-Gordon. Consider an inductive family of finite groups: $$ G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_i \...
19
votes
0answers
831 views

Is Feferman's unlimited category theory dead?

In The prospects of unlimited category theory: doing what remains to be done, 2014 (The Review of Symbolic Logic, 8 (2015) pp 306-327, link), Ernst discusses Feferman's program, described in ...
19
votes
0answers
399 views

Can Gentzen-style proofs give omega-consistency and beyond?

In 1936, Gentzen famously showed that Primitive Recursive Arithmetic, plus the assumption that the ordinal $\epsilon_0$ is well-founded, is able to prove Con(PA). But of course, Con(PA) doesn't yet ...
18
votes
0answers
576 views

Is this Variation of the Continuum Hypothesis Inconsistent with ZFC or ZF?

It is a well-known fact that the Generalized Continuum Hypothesis is undecidable from ZFC. For similar sentences $\phi$, this is simply equivalent to ZFC having a model $M$ for which $M\models\phi$. ...
18
votes
0answers
523 views

Souslin trees on the first inaccessible cardinal

This may be well-known or simply deducible from the existing theorems, but I didn't find an answer in my set theory books: Is there a model of $ZFC$ in which there are no $\kappa$-Souslin trees where ...
18
votes
0answers
947 views

Hrushovski's Construction

Zilber expressed a conjecture for $\aleph_{1}$- categorical theories (In the 80s). Zilber's Conjecture: The geometry of any $\aleph_{1}$- categorical structure is one of the following: (a) Trivial (...
18
votes
0answers
642 views

Antichains of Cardinals in ZF Without Choice…

With the Axiom of Choice, the cardinals form a nice linearly ordered "set". In the absence of the Axiom of Choice, the cardinals form a partially ordered "set". Broadly, I am wondering what ...
17
votes
0answers
458 views

Rigid Non-archimedean Real Closed Fields

Question. Is there a countable rigid non-Archimedean real closed field? Background: As usual, a structure is said to be rigid if the only automorphism of the structure is the identity map. It is ...
17
votes
0answers
325 views

Is it consistent with ZF that $V\to V^{\ast \ast}$ is always surjective?

In a comment to a recent question, Jeremy Rickard asked whether it is consistent with ZF that the map $V \to V^{**}$ from a vector space to its double dual is always surjective. We know that "always ...
17
votes
0answers
320 views

Does the pointclass of universally Baire sets always have the uniformization property?

A set of reals, or binary relation on the reals, etc., is called universally Baire if and only if every continuous preimage of it in every topological space has the property of Baire. (There is also ...
17
votes
0answers
689 views

What is the Cantor-Bendixson rank of the space of first order theories?

Let $L$ be the language $\{R\}$ containing a single binary relation symbol. Consider the space $S_0(L)$ of complete, first-order $L$-theories. This is a seperable, compact Hausdorff space; what is its ...
17
votes
0answers
802 views

Souslin trees and weakly compact cardinals

In Souslin trees on the first inaccessible cardinal it is asked if it is consistent that there are no $\kappa-$Souslin trees at the least inaccessible cardinal $\kappa$. In this question I would like ...
17
votes
0answers
560 views

Are there lightweight foundations for arbitrarily extendable objects?

My experience with foundations is rather scant, but I've run into some types of objects that seem to resist the sort of set-theoretic encoding schemes via Kurowski tuples that are rather common for ...
16
votes
0answers
436 views

Gitik's work on Shelah's weak hypothesis

It seems that Moti Gitik has recently refuted some variants of Shelah's weak hypothesis. For this see the title and abstract of his talk at the Set Theory, Model Theory and Applications conference. I ...
16
votes
0answers
496 views

Ramsey's theorem for the first uncountable ordinal

Sierpiński proved that a version of Ramsey's theorem for colourings of pairs of countable ordinals fails miserably by comparing the ordering of $\omega_1$ with the linear ordering of (a subset of) the ...
16
votes
0answers
205 views

Gap two Sierpinski set?

Is it consistent to have a set of reals $X$ of size $\aleph_3$ such that for every $Y \subseteq X$, $Y$ has measure zero iff $|Y| \leq \aleph_1$?
16
votes
0answers
429 views

Do all countable $\omega$-standard models of ZF with an amorphous set have the same inclusion relation up to isomorphism?

In my recent paper with Makoto Kikuchi, J. D. Hamkins and M. Kikuchi, The inclusion relations of the countable models of set theory are all isomorphic. manuscript under review. (arχiv) we proved ...
16
votes
0answers
554 views

Decidability of $x^3+y^3+z^3 = c$

I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that $x^3+y^...
16
votes
0answers
612 views

Ideas behind Gitik's solution of PCF conjecture

Recently Moti Gitik has refuted Shelah's PCF conjecture (see Short extenders forcings II ) by proving the following theorem: Theorem. Assuming the consistency of infinitely many strong cardinals, one ...
15
votes
0answers
593 views

What is the smallest unsolved diophantine equation?

If $P=\sum_{\bf i} a_{\bf i}x^{\bf i}\in {\mathbb Z}[x_1,\dots,x_d]$, let $|P|=\sum_{\bf i}|a_{\bf i}|x^{\bf i}$ and $h(P)=|P|(2,\dots,2)$, so that there is only a finite number of $P$ with $h(P)\leq ...
15
votes
0answers
523 views

The axiom $I_0$ in the absence of $AC$

It is well-known that if $AC$ holds and if $j: L(V_{\lambda+1}) \to L(V_{\lambda+1})$ is a non-trivial elementary embedding with $crit(j) < \lambda,$ then $\lambda$ has countable cofinality (and in ...
15
votes
0answers
640 views

Minimal resources for Undecidability of First-Order Logic: the number of variables

It is well-known that First-Order Logic (FO) with a full vocabulary (i.e., a countable numbers of unary predicate symbols, a countable number of binary predicate symbols, etc.) is undecidable. And it ...
15
votes
0answers
487 views

To what extent does (co)homology of groups made discrete depend on set theory?

There's a well-known paper by Milnor, "On the homology of Lie groups made discrete," that discusses the relation between the homology of a Lie group $G$ and the underlying discrete group $G^\delta$. ...
14
votes
0answers
287 views

O-minimality and forcing

It is well-known that the structure $(\mathbb{R}, +, \cdot, <, 0, 1)$ is an o-minimal structure and hence the set of integers $\mathbb{Z}$ is not definable in it. In an ongoing project with Will ...
14
votes
0answers
272 views

The failure of GCH al $\aleph_\omega$ by nice forcing

There are several ways to force $GCH$ below $\aleph_\omega$ and $2^{\aleph_\omega}> \aleph_{\omega+1},$ say: 1) The Gitik-Magidor's extender based forcing, see Prikry type Forcings. 2) Woodin's ...
14
votes
0answers
207 views

Complexity classes for BSS machines

Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where Cells on the tape can hold arbitrary elements of $\mathcal{S}$. The ...
14
votes
0answers
356 views

Adding a saturated ideal

Is it consistent that there is no $\omega_2$-saturated ideal on $\omega_1$, but one is introduced by an $\omega_2$-closed forcing? Some motivation: If $\delta$ is a Woodin cardinal, then it remains ...
14
votes
0answers
715 views

Has anyone read/debunked Yessenin-Volpin–Hennix “Beware of the Gödel-Wette paradox”?

A student recently asked me about the status of a 2001 arXiv post, Beware of the Gödel-Wette paradox!, by Alexander Yessenin-Volpin (aka Esenin-Volpin and several other transliterations) and Catherine ...
14
votes
0answers
324 views

What is the simplest known arithmetic definition of exponentiation?

For $n$ a natural number, let $E_n$ denote the set of bounded arithmetic formulas consisting of n alternating blocks of bounded quantifiers starting with an existential quantifier, followed by a ...
13
votes
0answers
289 views

Cardinality vs. isomorphism type of vector spaces without choice

One of the classical uses of the existence of bases of vector spaces (which is equivalent to the axiom of choice) is the following theorem: If $V$ is an infinite vector space over a field $F$, and $...
13
votes
0answers
324 views

What is the logical complexity of the Hodge conjecture?

The Hodge conjecture seems to me the most mysterious among the Millennium problems (and many others). In particular, I am not sure about its logical complexity. It is not difficult to see that the ...
13
votes
0answers
270 views

Constructing a topos from a Heyting algebra

It is true that, given any topos $\mathcal{C}$ with a terminal object $1_\mathcal{C}$, $Sub(1_\mathcal{C})$ is a Heyting algebra. Now suppose that we start with a Heyting algebra $H$. Is it always ...
13
votes
0answers
639 views

Algebraic proofs of algebraic theorems about algebraically closed fields

It is well-known that the first order theory of algebraically closed fields admits quantifier elimination, whence the theory $ACF_p$ of algebraically closed fields of given characteristic $p$ is ...
13
votes
0answers
522 views

If $U,D$ are $\kappa$-complete nonprincipal ultrafilters on $\kappa$ and $j_U(U) = j_D(D)$, is $U=D$?

Here, $\, j_U, \, j_D$ are the canonical elementary embeddings induced by $U,D$ respectively. I note that it is consistent with the existence of a measurable that the answer be yes: it is true in the ...
13
votes
0answers
448 views

Is the universality of the surreal number line a weak global choice principle?

I'd like to consider the principle asserting that the surreal number line is universal for all class linear orders, or in other words, that every linear order (including proper-class-sized) linear ...
13
votes
0answers
468 views

The topos for forcing in computability theory

My understanding is that forcing (such as Cohen forcing) can be described via a topos. For example this nlab article on forcing describes forcing as a "the topos of sheaves on a suitable site." My ...
13
votes
0answers
378 views

How to measure the strength of Zermelo over bounded Zermelo?

Bounded Zermelo is Zermelo set theory with only bounded separation. It has the same strength as simple type theory or MacLane set theory or ETCS. It is a finitely axiomatized fragment of Zermelo, so ...
13
votes
0answers
724 views

Does Fermat hold in non-standard models?

Let $n \geq 3$ be a natural number and $PA$ denote Peano arithmetic. Do we have $PA \models \forall x,y,z \geq 1 : x^n + y^n \neq z^n$? In other words, does Fermat's Last Theorem hold also in non-...
12
votes
0answers
379 views

A question concerning model theory of groups

Several days ago, Professor Martin Bridson gave a very nice talk in my department. Some questions concerning his talk came into my brain Since I am neither a model theorist nor a algebraist, I am not ...
12
votes
0answers
252 views

Can you define a probability measure on the set of countable transitive models of ZFC?

It is well known that the set of hereditarily countable sets $H(\omega_1)$ —or, if you prefer, $H_{\omega_1}$— has cardinality $2^{\aleph_0}$, and I understand that every countable ...
12
votes
0answers
428 views

Large cardinals arising from alternate set theories

My question is whether there are model-theoretic large cardinal axioms associated with $NFU$ - or more generally, with set theories other than $ZFC$. Large cardinal properties generally come in one ...