Questions tagged [constructive-mathematics]
Constructive mathematics in the style of Bishop, including its semantics using realizabilty or topological methods.
300 questions
5
votes
0
answers
163
views
Does this weak omniscience principle have a name?
In constructive analysis, I'm looking at principles which follow both when there exists at least one discontinuous function from $\mathbb{R}$ to $\mathbb{R}$ (equivalent to WLPO i.e. $x > 0$ or $x \...
- 1,947
6
votes
2
answers
568
views
Can the real numbers be constructed as/from a Hom-object in a topos?
I've been reading through Greenblatt's Topoi and while I'm still definitely over my head I'm starting to get a feel for some of the concepts at play there. I see the definitions of $\mathbb{R}_c$ and $...
- 1,951
8
votes
1
answer
228
views
Examples of anti-classical theories in iFOL
An anti-classical axiom $\phi$ is one which is inconsistent with LEM
Are there any sources for good examples of anti-classical theories in intuitionstic first-order logic? There are many examples of ...
- 183
5
votes
1
answer
256
views
Does a special property hold if the Archimedean property for reals doesn't hold?
Suppose $\mathbb{R}^e=A \cup B$ in which $A \cap B=\varnothing$ and there exist real numbers $a_0$ and $b_0$ such that $a_0 \in A$ and $b_0 \in B$. My question is, can we construct $a \in A$ and $b \...
3
votes
0
answers
287
views
What did Mirimanoff say about Intuitionism?
Dmitry Mirimanoff, "L'intuitionisme", Alma Mater n° 6, Geneva, 1945.
Most of Mirimanoff's work was in number theory, but he wrote three papers about set theory that were way ahead of their ...
- 8,481
5
votes
2
answers
372
views
Weak Archimedean property instead of Archimedean property
We say that a sequence $(z_n)$ of real numbers is a modulated Cauchy sequence, whenever there exists a function $\alpha:\mathbb{N} \rightarrow \mathbb{N}$ such that:
$$
|z_i-z_j| \le \frac{1}{k} \quad ...
7
votes
1
answer
224
views
Does the decomposability of $\mathbb{R}$ imply analytic LLPO?
By "BISH" I mean constructive mathematics without axiom of countable choice.
By $\mathbb{R}^f$ I mean real numbers as fundamental sequences of rational numbers and by $\mathbb{R}^d$ I mean ...
4
votes
0
answers
260
views
Läuchli's "intermediate thing"
On page 230 of An abstract notion of realizability ..., Läuchli writes the following:
If we drop the restrictions put on $\Theta$, then we get classical logic in one case and an intermediate thing in ...
- 21.1k
13
votes
1
answer
932
views
Consistency strength of HoTT
What is the consistency strength of Homotopy type theory (HoTT) relative to various set theories (e.g., are there any known set theories that it can interpret)? Does this question even make sense?
- 4,985
8
votes
0
answers
157
views
How to define Dedekind reals and Eudoxus reals such that they are equivalent to unmodulated Cauchy reals
In constructive mathematics without choice, we have three different versions of the real numbers (each embedding into the next).
Regular Cauchy reals (functions $f : \mathbb N \to \mathbb Q$ such ...
- 6,353
6
votes
1
answer
387
views
Decimal expansion definition of real numbers, constructively
The two most common definitions of $\mathbb{R}$ are as Dedekind cuts or Cauchy sequences of rational numbers.
A real analysis student of mine is working out of the book Real Analysis and Applications ...
- 10.1k
6
votes
0
answers
145
views
Constructive mathematics with different computational models
I am interested in understanding how the capabilities of constructive mathematics evolve when different computational models are considered. Specifically, if constructive mathematics traditionally ...
- 441
9
votes
2
answers
380
views
How big can function spaces get without extensionality?
In what follows we work in the usual formulation of Martin-Löf Type Theory including Axiom K [1]. Boldface numbers $\mathbf{n}$ denote the usual finite type with $n$ elements.
Motivation
Postulating ...
- 756
7
votes
1
answer
290
views
Equivalence of omniscience principles for natural numbers and analytic omniscience principles for Cauchy real numbers
In constructive mathematics, a proposition $P$ is decidable if $P \vee \neg P$, and a proposition is stable if $\neg \neg P \implies P$. We have the following principles of omniscience for the natural ...
- 2,624
2
votes
0
answers
143
views
Constructively, when do functions that agree on $[a, b] \cup [b, c]$ also agree on $[a,c]$?
Let $a, b, c \in \mathbb R$ such that $a \le b \le c$. Let $S$ be some set and $f, g : [a, c] \to S$ be functions. As a follow up to When can a function defined on $[a, b] \cup [b, c]$ be ...
- 6,353
3
votes
0
answers
168
views
Is the Tarski–Seidenberg theorem constructively provable?
The Tarski–Seidenberg theorem asserts that the projection of a semialgebraic set is also a semialgebraic set. My question is whether this is provable in constructive mathematics.
First, let me ...
- 6,353
10
votes
0
answers
158
views
Closed sets versus closed sublocales in general topology in constructive math
This question is set in constructive mathematics (without Choice), such as in the internal logic of a topos with natural numbers object, or in IZF.
Short version of the question: if $X$ is a sober ...
- 32.4k
8
votes
2
answers
508
views
Condition to guarantee that an inhabited and bounded set of reals has a supremum
This question is about constructive mathematics (without Choice), such as in the internal logic of a topos with natural numbers object, or in IZF. The “reals” (and the symbol $\mathbb{R}$) refer to ...
- 32.4k
15
votes
3
answers
2k
views
Exponentials of truth values
I noticed that the exponentiation identity
$$\exp(r + s) = \exp(r) \cdot \exp(s)~,$$
which is of course completely standard for real or complex numbers also holds in a Boolean setting.
That is, when I ...
- 351
8
votes
0
answers
386
views
Can the p-adic be countable?
Recently arxiv submitted a new paper (Andrej Bauer, James E. Hanson, The Countable Reals) claiming an incredible theorem that Dedekind reals are not sequence-avoiding, and furthermore obtaining a ...
- 695
9
votes
1
answer
259
views
Does there exist a geometric morphism between the effective and topological topoi? Does one arise from synthetic topology?
I'm presenting in final projects for my computability and computational topology courses on the connections between computability, continuity, and logic. As a mathematician/unmentored baby logician ...
- 433
7
votes
0
answers
306
views
The constructive Eudoxus reals
Recently arxiv submitted a new paper (Andrej Bauer, James E. Hanson, The Countable Reals) claiming an incredible theorem that Dedekind reals are not sequence-avoiding, and furthermore obtaining a ...
- 695
7
votes
0
answers
255
views
Is it decidable whether a statement about reals (in the language of ordered rings) is constructively provable?
The language of ordered rings is a first-order language with operators for $+$, $-$, and $\cdot$, constants for $0$ and $1$, and relations for $<$, $=$ and $>$.
To decide whether such a ...
- 6,353
18
votes
3
answers
3k
views
What's the earliest result (outside of logic) that cannot be proven constructively?
Although mathematicians usually do not work in constructive mathematics per se, their results often are constructively valid (even if the original proof isn't).
An obvious counter-example is the law ...
- 6,353
5
votes
0
answers
230
views
Are there Dedekind-infinite amorphous sets?
An amorphous set is an infinite set (i.e. cannot be put into bijection with any finite set $\{ 1, \dots, n \}$ for any $n$) that cannot be partitioned into two mutually disjoint infinite subsets. ...
- 51
9
votes
1
answer
255
views
What are these generalizations of the principles of omniscience called?
I will give some principles that are slightly stronger versions of the principles of omniscience. Despite being about the natural numbers, they imply their analytic versions! Under countable choice (...
- 6,353
9
votes
2
answers
2k
views
Truth in a different universe of sets?
I understand that provability and truth as different concepts.
Provability is syntactic, it only concerns whether the given
sentence can be derived by reiterating the inference rules over a
collection ...
- 5,230
11
votes
6
answers
1k
views
When can a function defined on $[a, b] \cup [b, c]$ be constructively extended to a function defined on $[a, c]$?
Let $a, b, c \in \mathbb R$ such that $a \le b \le c$. Let $S$ be some set and $f : [a, b] \cup [b, c] \to S$ be a function. When can we find a function $g : [a, c] \to S$ that meets the following ...
- 6,353
3
votes
0
answers
95
views
What does the computation of irrationality and transcendentality via a fancy implementation of analytic Markov's property look like?
Proofs that various real numbers are not rational or not algebraic tend to be constructively valid as is. Examples include the proofs that $\sqrt 2$ and $\log_2(3)$ are not rational and that $e$ is ...
- 6,353
3
votes
1
answer
205
views
Are the multi-valued Eudoxus reals constructively equivalent to the Dedekind reals?
Without LEM or the axiom of choice, we can prove that the Eudoxus reals are equivalent to the Cauchy reals but can't prove either of those equivalent to the Dedekind reals.
However, we can prove that ...
- 6,353
6
votes
0
answers
108
views
Archimedean ordered field in which every function is smooth
In constructive mathematics, it is consistent that every function $\mathbb{R} \to \mathbb{R}$ on the Dedekind real numbers is continuous. However, it is not consistent that every function $\mathbb{R} \...
- 2,624
6
votes
1
answer
289
views
Archimedean ordered fields without maxima and minima in constructive mathematics
In constructive mathematics, let us define an ordered (Heyting) field $F$ to be a commutative ring with a binary relation $<$ which is
irreflexive, where for all $x$, $\neg (x < x)$
asymmetric, ...
- 2,624
14
votes
1
answer
520
views
Is there a theory between HA and PA that doesn't have Markov's rule?
A theory $T$ admits Markov's rule when
For every formula $\phi(n)$, if $$T \vdash \forall n \in \mathbb N. \phi(n) \lor \lnot \phi(n)$$ and $$T \vdash \lnot \lnot \exists n \in \mathbb N. \phi(n)$$ ...
- 6,353
4
votes
1
answer
222
views
Is every compact, sober, second-countable space the image of $2^\omega$?
As a bonus, is every compact, $T_0$, second-countable space the image of $2^\omega \times \omega$?
As a further bonus, can we strengthen "image" to "quotient"?
My motivation for ...
- 3,612
4
votes
1
answer
257
views
What is the theory of statements with a provably *bounded* realizer (according to PA)?
$\let\T\mathrm\def\kr{\mathrel{\mathbf r}}$This is a follow up to Kleene realizability in Peano arithmetic.
We can summarize the results from Emil Jeřábek's answer as follows:
\begin{gather*}
T_1 = \{ ...
- 6,353
5
votes
3
answers
1k
views
Understanding $\forall p \, q .\, \sqrt{2} \neq p/q$ constructively
"By contradiction" or "of negation" is an old chestnut of constructive dispute.
But taking apartness as primitive instead of equality yields a definition of irrationality without ...
- 8,481
3
votes
0
answers
186
views
In constructive set theory, is it consistent for there to be a ring that models smooth infinitesimal analysis?
In a constructive set theory such as CZF, it is consistent to assume that every function $f : \mathbb R \to \mathbb R$ is continuous. However, it is not consistent to assume that every such function ...
- 6,353
5
votes
1
answer
300
views
Does weak countable choice imply that the Cauchy reals are Dedekind complete?
Assuming the axiom of weak countable choice, is the set of modulated Cauchy reals Dedekind complete?
The second theorem on this ncatlab page claims something equivalent, but it doesn't contain a proof ...
- 6,353
6
votes
0
answers
297
views
What are these non-classical versions of ZFC defined by realizability?
See Kleene realizability in Peano arithmetic for a similar question, but about PA instead of ZFC. (In particular, an answer as specific as Emil Jeřábek's answer would be great!)
In the context of ...
- 6,353
6
votes
1
answer
293
views
Need help in trying to understand an argument by V. A. Yankov on the nonrealizability of Scott's axiom
(This is really long because I give a lot of context, but you can skip right to the end where the excerpt I'm trying to make sense of is copied and translated.)
Background: I'm trying to understand ...
- 32.4k
3
votes
0
answers
234
views
Uses of excluded middle on a conjecture that can be rewritten constructively with this trick
An interesting proof technique is to use the law of excluded middle on a conjecture. There are proofs using LEM on the Riemann hypothesis for example.
Constructively this is disallowed (if you can ...
- 6,353
7
votes
0
answers
198
views
Strengthening Determinacy in constructive set theory?
Recall how games work. Let $X$ be a set (the "game space") and $\alpha$ an ordinal (the "game clock"). Alice and Bob take turns naming elements of $X$. We write them down in order ...
- 63.9k
1
vote
1
answer
74
views
Constructing set-truncations of types from universes
This is a follow-up question from my previous question titled Constructing coproduct types and boolean types from universes, where I showed how every basic operation in set theory/topos theory could ...
- 2,624
4
votes
1
answer
169
views
Constructing coproduct types and boolean types from universes
Suppose we have a dependent type theory which has dependent product types, dependent sum types, identity types, function extensionality, an empty type, and a universe $U$ which is closed under the ...
- 2,624
9
votes
0
answers
287
views
The approximate mean value theorem / Rolle's theorem in pure constructive mathematics
In the replies of this very similar question, there is a fascinating answer that is beautiful in its simplicity. In particular, it seems to use perhaps the most minimal assumptions one can possibly ...
- 191
8
votes
1
answer
258
views
Sequential colimit of iterated quotients of Cauchy sequences
We work in constructive mathematics.
The sets and functions in the foundations form a Grothendieck topos, which means that all colimits exist, and in particular, that all sequential colimits exist. ...
- 2,624
12
votes
0
answers
541
views
Does Wedderburn's Little Theorem hold constructively?
Wedderburn's Little Theorem states that every finite division ring is commutative. Perhaps even more surprising, this implies that every finite reduced ring is commutative.
The proofs that I am aware ...
- 63.1k
6
votes
1
answer
263
views
Existence property for second-order propositional logic
Consider the intuitionistic second-order propositional calculus (SOL) formulated in the full $\wedge,\vee,\rightarrow,\bot,\top,\forall,\exists$ language.
Question: Assume that $\Gamma$ and $\Psi$ are ...
- 756
6
votes
2
answers
723
views
In the constructive theory of direct categories, is it decidable whether an arbitrary morphism is an identity or not?
I'm wondering what the legit definition of direct categories should be in constructive mathematics. I must admit I don't even know in what literature I should look for the definition. I would ...
- 366
14
votes
0
answers
185
views
Limits in free cocompletion, constructively
Classically, if a locally small category $C$ has all limits of shape $K$ (for some small diagram $K$), then its free co-completion also has $K$-shapped limits.
But all proof I know of that result ...
- 42.4k