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,135
questions
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.
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 ...
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$, ...
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\}$$
...
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. ...
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
$...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}...
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 ...
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}...
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 ...
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 ...
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....
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 ...
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$ ...
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 ...
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. ...
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-...
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 ...
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 ...
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 ...
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, ...
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) ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 "...
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 \...
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 $\...
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 ...
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 ...
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)...
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 ...