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
31 votes
6 answers
3k views

A Model where Dedekind Reals and Cauchy Reals are Different

Is there a model where Dedekind reals and Cauchy reals are different? I'd appreciate if someone can refer me to any related work in case such a model exists.
Jean Joseph's user avatar
31 votes
4 answers
4k views

Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable?

One might say, "a random subset of $\mathbb{R}$ is not Lebesgue measurable" without really thinking about it. But if we unpack the standard definitions of all those terms (and work in ZFC), it's not ...
Gene S. Kopp's user avatar
  • 2,190
31 votes
3 answers
3k views

Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?

Question. Given a Turing-machine program $e$, which is guaranteed to run in polynomial time, can we computably find such a polynomial? In other words, is there a computable function $e\mapsto p_e$, ...
Joel David Hamkins's user avatar
31 votes
2 answers
2k views

Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?

There are many interpretations of arithmetic in set theory. The Zermelo interpretation, for example, begins with the empty set and applies the singleton operator as successor: $$0=\{\ \}$$ $$1=\{0\}$$ ...
Joel David Hamkins's user avatar
31 votes
2 answers
3k views

Do we expect that sufficiently large computable ordinals settle every question of arithmetic?

I came across a post by Ron Maimon on physics.SE that makes what seems to me to be a very interesting conjecture I've never seen before about what it would take to settle every question of arithmetic. ...
Qiaochu Yuan's user avatar
31 votes
3 answers
3k views

Can there be an embedding j:V → L, from the set-theoretic universe V to the constructible universe L, when V ≠ L?

Main Question. Can there be an embedding $j:V\to L$ of the set-theoretic universe $V$ to the constructible universe $L$, if $V\neq L$? By embedding here, I mean merely a proper class isomorphism from $...
Joel David Hamkins's user avatar
31 votes
2 answers
4k views

Hahn's Embedding Theorem and the oldest open question in set theory

Hans Hahn is often credited with creating the modern theory of ordered algebraic systems with the publication of his paper Über die nichtarchimedischen Grössensysteme (Sitzungsberichte der ...
Philip Ehrlich's user avatar
31 votes
5 answers
3k views

What is the status of the Hilbert 6th problem?

As you know, the Hilbert sixth problem was to axiomatize physics. According to the Wikipedia article, there is some partial succes in this field. For example, Classical mechanics, I believe, can be ...
Sergei Akbarov's user avatar
31 votes
1 answer
2k views

Can ZFC → NBG be iterated?

von Neumann-Bernays-Gödel set theory (NBG) is a conservative extension of ZFC which contains "classes" (such as the class of all sets) as basic objects. "Conservative" means that anything provable in ...
Mike Shulman's user avatar
31 votes
2 answers
3k views

Mathematical Evidence Backing $|\mathbb{R}|=\aleph_2$

The "true" size of the real line, $\mathbb{R}$, has been the subject of Hilbert's first problem. Due to the Goedel and Cohen's work on the inner and outer models of $\text{ZFC}$, it turned ...
Morteza Azad's user avatar
31 votes
2 answers
2k views

The logic of convex sets

Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so ...
darij grinberg's user avatar
30 votes
11 answers
6k views

Physics and Church–Turing Thesis

Is there constructed some set of physical laws from which we can logically obtain that any function that can be implemented in some device is Turing computable? EDIT I believe that if we restrict ...
Dan's user avatar
  • 1,288
30 votes
8 answers
3k views

On independence and large cardinal strength of physical statements

The present post is intended to tackle the possible interactions of two bizarre realms of extremely large and extremely small creatures, namely large cardinals and quantum physics. Maybe after all ...
Morteza Azad's user avatar
30 votes
4 answers
4k views

Is "all categorical reasoning formally contradictory"?

In the December 2009 issue of the newsletter of the European Mathematical Society there is a very interesting interview with Pierre Cartier. In page 33, to the question What was the ontological ...
José Figueroa-O'Farrill's user avatar
30 votes
2 answers
1k views

Define $\mathbb{N}$ in the ring $\mathbb{Z}$ without Lagrange's theorem

It is well-known that the set of nonnegative integers $\mathbb{N}$ is definable in the ring of integers $\mathbb{Z}$. Indeed, by Lagrange's four squares theorem we have $\mathbb{N} = \{n \in \mathbb{Z}...
user avatar
30 votes
5 answers
4k views

How many of the true sentences are provable?

Is there a natural measure on the set of statements which are true in the usual model (i.e. $\mathbb{N}$) of Peano arithmetic which enables one to enquire if 'most' true sentences are provable or ...
pinaki's user avatar
  • 5,064
30 votes
1 answer
2k views

Do the algebraic integers form a free abelian group?

It is a well-known fact, proved in every introductory textbook on algebraic number theory, that if $K$ is an algebraic number field, i.e. a finite extension of $\mathbb{Q}$, then its ring $\mathcal{O}...
Robert Kucharczyk's user avatar
30 votes
8 answers
3k views

Unique existence and the axiom of choice

The axiom of choice states that arbitrary products of nonempty sets are nonempty. Clearly, we only need the axiom of choice to show the non-emptiness of the product if there are infinitely many ...
Michael Greinecker's user avatar
29 votes
6 answers
5k views

In set theories where Continuum Hypothesis is false, what are the new sets?

So, say we are working with non-CH mathematics. This means, AFAIK, that there is at least one set $S$ in our non-CH mathematics, whose cardinality is intermediate between $|\mathbb{N}|$ (card. of ...
tony's user avatar
  • 293
29 votes
8 answers
4k views

When is something too big to be a set?

Hello, recently, I've been reading some algebra and sometimes I stumble up on the concept of something "being too big" to be a set. An example, is given in (http://www.dpmms.cam.ac.uk/~wtg10/tensors3....
Dedalus's user avatar
  • 1,071
29 votes
10 answers
4k views

Defining the standard model of PA so that a space alien could understand

First, some context. In one of the comments to an answer to the recent question Why not adopt the constructibility axiom V=L? I was directed to some papers of Nik Weaver at this link, on ...
Pace Nielsen's user avatar
29 votes
3 answers
3k views

Is the theory of categories decidable?

There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led me to consider the ...
29 votes
4 answers
6k views

Why do people say Gödel's sentence is true when it is true in some models but false in others?

I am a beginner, so this question may be naive. Suppose we have a (sufficiently strong) consistent first order logic system. Gödel's first incompleteness theorem says there exists a Gödel sentence $g$ ...
CouldntLoginToMyPreviousAcc's user avatar
29 votes
7 answers
3k views

What is a logic?

I am not interested in the philosophical part of this question :-) When I look at mathematics, I see that lots of different logics are used : classical, intuitionistic, linear, modal ones and weirder ...
alpheccar's user avatar
  • 435
29 votes
6 answers
4k views

Concrete example of $\infty$-categories

I've seen many different notions of $\infty$-categories: actually I've seen the operadic-globular ones of Batanin and Leinster, and the opetopic, and eventually I'll see the simplicial ones too. ...
Giorgio Mossa's user avatar
29 votes
6 answers
37k views

Reading materials for mathematical logic [closed]

Hi everyone, the summer break is coming and I am thinking of reading something about mathematical logic. Could anyone please give me some reading materials on this subject?
29 votes
4 answers
4k views

How dangerous are set-size assumptions?

Many students' first introduction to the difference between classes and sets is in category theory, where we learn that some categories (such as the category of all sets) are class-sized but not set-...
Pace Nielsen's user avatar
29 votes
2 answers
767 views

Does $\mathrm{SO}(3)$ act faithfully on a countable set?

Let $\mathrm{SO}(3)$ be the group of rotations of $\mathbb{R}^3$ and let $S_\infty$ be the group of all permutations of $\mathbb{N}$. Is $\mathrm{SO}(3)$ isomorphic to a subgroup of $S_\infty$? This ...
Erik Walsberg's user avatar
29 votes
3 answers
3k views

Is it decidable whether or not a collection of integer matrices generates a free group?

Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
John Pardon's user avatar
  • 18.3k
29 votes
2 answers
2k views

On the probability of the truth of the continuum hypothesis

First note that there exists a natural measure $\mu$ on $P(\omega \times \omega)$, inherited from the Lebesgue measure on the reals (by identifying the reals with $P(\omega)$ and $\omega$ with $\omega ...
Mohammad Golshani's user avatar
29 votes
2 answers
1k views

Applications of Categorical Logic to Logic

This is definitely a very open ended question. I have been studying Categorical Logic for a while now --- I've read Sheaves in Geometry and Logic, Adámek & Rosický's Presentable Categories, ...
DeadRingerAmbassador's user avatar
29 votes
2 answers
3k views

Does Taranovsky's system of ordinal notations make sense?

Dmytro Taranovsky has a Web page on which he claims to define a system of ordinal notations strong enough to provide an ordinal analysis of full second-order arithmetic. I think (perhaps unjustly) ...
Gro-Tsen's user avatar
  • 29.9k
29 votes
0 answers
2k views

Did Grothendieck overestimate topoi?

I was reading the Russian translation of Recoltes et Semailles and in the footnote where Grothendieck lists his 12 contributions (including schemes) we find the following lines: Из этих тем ...
28 votes
5 answers
3k views

How do we construct the Gödel’s sentence in Martin-Löf type theory?

In Martin-Löf dependent type theory (MLTT), under the proposition-as-types correspondence, we sometimes say that a proposition $A$ is true if the type $A$ is inhabited. However, there is no doubt that ...
StudentType's user avatar
28 votes
3 answers
3k views

Does $\operatorname{Con}\sf(ZF)$ imply $\operatorname{Con}\sf(ZF + \operatorname{Aut}{\bf C = Z/\mathrm 2Z})$?

How many field automorphisms does $\mathbf{C}$ have? If you assume the axiom of choice, there are tons of them -- $2^{2^{\aleph_0}}$, I believe. And what if you don't -- how essential is the axiom ...
Jared Weinstein's user avatar
28 votes
2 answers
3k views

Who introduced direct limits?

The general notion of a direct limit of a commuting system of embeddings, indexed by pairs in a directed set, has seen heavy use in set theory. It is the same notion as in category theory. I was ...
Monroe Eskew's user avatar
  • 18.1k
28 votes
1 answer
6k views

What is the cofinality of the co-infinite subsets of ${\bf N}$?

Let ${\mathcal A}$ be the family of subsets $A$ of the natural numbers ${\mathbf N}$ which are co-infinite (i.e., their complement is infinite). We partially order this family by set inclusion. A ...
Terry Tao's user avatar
  • 108k
28 votes
2 answers
2k views

What do coherent topoi have to do with completeness?

There is a theorem of Deligne in SGA4 that a "coherent" topos (e.g. one on a site where all objects are quasi-compact and quasi-separated) has enough points (i.e. isomorphisms can be detected via ...
Akhil Mathew's user avatar
  • 25.3k
28 votes
2 answers
5k views

What is the manner of inconsistency of Girard's paradox in Martin Lof type theory

I am aware that assigning the type of Type to be Type (rather than stratifying to a hierarchy of types) leads to an inconsistency. But does this inconsistency allow the construction of a well-typed ...
luqui's user avatar
  • 585
28 votes
1 answer
2k views

Why isn't this a computable description of the ordinal of ZF?

In a previous MO question, I was told by several commenters that (a) it's known that there exists a computable ordinal $\alpha_{ZF}$ that "encodes the strength of ZF set theory" (i.e., a least ...
Scott Aaronson's user avatar
28 votes
1 answer
2k views

How hard is it to destroy a diamond? (with a real)

If we start with $V\models\lozenge$, it is not hard to force the failure of diamond. You can blow up the continuum, or destroy all the Suslin trees. You can blow up the continuum of $\aleph_1$, and ...
Asaf Karagila's user avatar
  • 38.1k
28 votes
0 answers
2k views

Is Feferman's unlimited category theory dead?

In 2013 Solomon Feferman in Foundations of unlimited category theory: what remains to be done (The Review of Symbolic Logic, 6 (2013) pp 6-15, link) laid out three desirable axioms for "...
ziggurism's user avatar
  • 1,436
28 votes
0 answers
809 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 \...
François G. Dorais's user avatar
28 votes
0 answers
2k 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 $\...
Noah Schweber's user avatar
27 votes
13 answers
3k views

Are there any good nonconstructive "existential metatheorems"?

Are there any good examples of theorems in reasonably expressive theories (like Peano arithmetic) for which it is substantially easier to prove (in a metatheory) that a proof exists than it is ...
27 votes
4 answers
9k views

Finite axiom of choice: how do you prove it from just ZF?

The axiom of choice asserts the existence of a choice function for any family of sets F. Suppose, however, that F is finite, or even that F just has one set. Then how do we prove the existence of a ...
user7758's user avatar
  • 287
27 votes
5 answers
4k views

Why aren't functions used predominantly as a model for mathematics instead of set theory etc.? [closed]

If definitions themselves are informally just maps from words to collections of other words. Then in order for one to define anything, they must inherently already have a notion of a function. I mean ...
Ethan Splaver's user avatar
27 votes
4 answers
7k views

Are $\mathbb{C}$ and $\overline{\mathbb{Q}}_p$ isomorphic?

There is a famous passage on the third page of Deligne's second paper on the Weil conjectures where he expresses his dislike of the axiom of choice, as manifested in the isomorphism between $\mathbb{C}...
27 votes
8 answers
4k views

Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough to express all functions, Ackermann function being probably the best known example. Now, in the logic courses (that I have had look at)...
user avatar
27 votes
4 answers
2k views

Does every set of reals contain a measure-zero set of the same cardinality? Does it contain a meager set of the same cardinality?

This question arises from an issue in my post on Ashutosh's excellent question on Restrictions of the null/meager ideal. Question 1. Does every set of reals contain a measure-zero subset of the same ...
Joel David Hamkins's user avatar

1
3 4
5
6 7
103