Questions tagged [constructive-mathematics]

Constructive mathematics in the style of Bishop, including its semantics using realizabilty or topological methods.

Filter by
Sorted by
Tagged with
3
votes
0answers
123 views

Constructive proof of the approximate Brouwer's Fixed Point Theorem for $\Delta^n$

The approximate Brouwer Fixed Point Theorem (aBFPT) for the standard $n$-simplex is: Let $f$ be a uniformly continuous function from $\Delta^n$ into itself. Then for each $\varepsilon>0$ there ...
0
votes
0answers
105 views

Is there difference in notion of measurability in classical versus constructive?

Are there notions of measure and examples of sets measurable in that measure in classical logic but not in constructive logic (I think there cannot be counterexamples in other direction)? Are there ...
10
votes
0answers
363 views

Does Merkurjev's argument help Voevodsky's program?

In the talk Unimath - its present and its future, July 10, 2017. Video and slides of a talk, Isaac Newton Institute for Mathematical Sciences, Cambridge. (abstract) Voevodsky mentioned that he was ...
3
votes
0answers
50 views

Embedding abelian categories into abelian sheaves

The Yoneda functor from an abelian category into sheaves of abelian groups is shown to be exact in The Stacks Project, Lemma 19.9.2. I like this proof because it is constructive and it doesn't use ...
11
votes
0answers
309 views

Isomorphic free groups have bijective generating sets

Let $F(X)$ be the free group on a set $X$. Classically, we can prove the statement: $F(X) \cong F(Y)$ if and only if $|X|=|Y|$. The proofs (that I have seen) consist of turning the group ...
2
votes
2answers
480 views

Monotonic and bounded sequences throughout mathematics [closed]

When I refer to the Monotone Convergence Theorem below, I refer to the very simple claim that if a non-decreasing sequence has an upper bound then it converges. I don't refer to the claim from Measure ...
3
votes
1answer
280 views

From a constructive perspective, what are the ordinal numbers?

From a constructive and computational perspective, what are the ordinal numbers? On the one hand, it seems you can represent ordinal numbers symbolically using something like Cantor Normal Form ...
13
votes
1answer
351 views

History of well founded relations

I have changed the title in the hope of attracting the attention of someone who knows about the history of set theory as well as intuitionistic logic: Who was the first to state the definition of ...
11
votes
3answers
578 views

The constancy principle in choiceless constructive foundations

Prove, without any Choice principles or Excluded Middle, that if a pointwise differentiable function has derivative $0$ everywhere, then it is constant. The function in this case maps $\mathbb R$ to $\...
9
votes
1answer
430 views

Toposes in which countable choice is true but dependent choice isn't

I'd like examples of toposes in which Countable Choice is true but Dependent Choice isn't. I'd prefer examples without Excluded Middle. It's hard to find a natural example.
13
votes
2answers
804 views

Contrasting theorems in classical logic and constructivism

Is it possible there are examples of where classical logic proves a theorem that provably is false within constructivism? Is so what are some examples? What are some examples of most contrasting ...
1
vote
1answer
104 views

Markov's principle from constant domain logic

I am looking for a proof of and/or a reference for the result that Markov's principle can be proved in the framework of constant domain logic. By constant domain logic, I mean intuitionistic logic ...
7
votes
1answer
201 views

Birkhoff's completeness theorem put into practice

Birkhoff's completeness theorem (see here, Theorem 14.19) states that an equation which is true in all models of an algebraic theory can be proven in equational logic. Question. Does the proof of ...
5
votes
1answer
217 views

Every complex number has a square root via LLPO without weak countable choice

Is it possible to prove that every complex number has a square root using analytic LLPO, but avoiding Weak Countable Choice or Excluded Middle? Unique Choice is allowed. (Analytic LLPO is the ...
6
votes
1answer
173 views

Tight apartness relations in toposes

A tight apartness relation on a set is a binary relation $\#$ such that the following conditions hold: $x = y$ if and only if $\neg (x \# y)$. If $x \# y$, then $y \# x$. If $x \# z$, then either $x \...
4
votes
0answers
165 views

Constructive contents of “the support of a sheaf is closed” or “the flat locus is open”

Out of curiosity I started to go through an introductory course on schemes and to convince myself that I could prove every result (after an appropriate reformulation if necessary) constructively, i.e. ...
5
votes
2answers
492 views

Uncountability of the real numbers from LLPO without countable choice

Does there exist a proof of the uncountability of the real numbers that uses analytic LLPO (the statement that any real number $x$ satisfies either $x \leq 0$ or $x \geq 0$) but avoids Excluded Middle ...
0
votes
1answer
454 views

On provability of false statements in constructive mathematics [closed]

Lagarias "elementary" reformulation of Robin's theorem is that $$\mathrm{RH}\iff\sigma(n)\leq H_n+e^{H_n}\log(H_n)$$ holds for every $n\geq 1$, where $\sigma(n)$ is the sum of divisors function and $...
4
votes
1answer
167 views

Does a map over subsingletons determine a subsingleton over maps?

I hope this question isn't too obfuscated (or easy)! Given a set $S$, let $S_\perp$ denote $\{X \in \mathcal P(S) \mid \forall x, y \in X.\, x=y\}$, the elements of which are subsingletons. In the ...
6
votes
3answers
375 views

How much of the Cantor-Schröder-Bernstein theorem is constructively recoverable if the injections have retractions and decidable images?

This is cross-posted from MSE at the suggestion of a comment after receiving no answers over a few weeks. Suppose we have $f : A \to B$ and $g : B \to A$, as well as left inverses $f_r : B \to A$ of $...
4
votes
0answers
174 views

An axiom that shows that the real numbers are weakly countable?

Is there a model of Intuitionistic Higher-Order Logic in which the following axiom is true? Covering Axiom: Any true statement of the form $\forall x \in A, \exists y \in B, \phi(x,y)$ gives rise to ...
5
votes
1answer
362 views

BISH: If a function is pointwise positive, is its infimum positive?

Let $f:[0,1] \to \mathbb R$ be a uniformly continuous function such that each value of $f(x)$ is greater than zero. Is its infimum greater than zero in BISH? I believe that it is indeed the case if ...
1
vote
1answer
136 views

Partial computability results on integrals over open intervals

It's well known in Type 2 Effectivity that integration over a compact interval is computable. So what about integration over an open interval? What rigorous computability results exist? My thoughts ...
3
votes
0answers
135 views

Is there a constructive proof of Baer's Criterion?

Baer's Criterion states than one can check injectivity of an $R$-module on inclusions of ideals. The proof, however, strikes me as very nonconstructive: it employs both Zorn's Lemma and LEM. Does ...
20
votes
2answers
2k views

Is it possible to constructively prove that every quaternion has a square root?

Is it possible to constructively prove that every $q \in \mathbb H$ has some $r$ such that $r^2 = q$? The difficulty here is that $q$ might be a negative scalar, in which case there might be "too many"...
18
votes
2answers
613 views

Constructive proof of existence of free algebras for infinitary equational theories

Is it constructively true that all (not necessarily finitary) equational theories $T = (\Sigma, E)$ have an initial model? The usual proof for finitary equational theories I know constructs first ...
7
votes
1answer
352 views

Differentiability of the distance function from a (variable) point to a (fixed) set

The distance of from a point $x$ to a set $A$ is defined by $$ d(x,S) = \inf\{d(x,a)\mid a\in A\}, $$ where you may choose the setting to be $\mathbb R^n$, a Banach space or a complete metric space. ...
12
votes
1answer
240 views

Does this “mixable” property have a standard name in constructive mathematics?

While thinking about constructive mathematics, I stumbled on the following notion, and I would like to know if it has a standard name, a simpler equivalent, or has appeared in the literature: Say ...
9
votes
2answers
489 views

Constructivist defininition of linear subspaces of $\mathbb{Q}^n$?

Let me preface this by saying I'm not someone who has every studied mathematical logic or philosophy of math, so I may be mangling terminology here (and the title is a little tongue in cheek). I (and ...
11
votes
0answers
199 views

Ordinal-valued sheaves as internal ordinals

Let $X$ be a topological space (feel free to add some separation axioms like “completely regular” if they help in answering the questions). Let $\alpha$ be an ordinal, identified as usual with $\{\...
8
votes
1answer
259 views

Kleene realizability in Peano arithmetic

For completeness of MathOverflow and for clarity of the question, I will first recall a few things, including the the definition of Kleene realizability: experts can jump directly to the question ...
7
votes
5answers
2k views

Is there any physical or computational justification for non-constructive axioms such as AC or excluded middle?

I became interested in mathematics after studying physics because I wanted to better understand the mathematical foundations of various physical theories I had studied such as quantum mechanics, ...
7
votes
1answer
633 views

Explaining the consistency of PRA and ZF from predicative foundations

Recently I got interested in predicative foundations, mostly because of Laura Crosilla's work and because Agda employs a predicative type theory. From the point of view of a predicative foundation to ...
13
votes
1answer
356 views

Is there a constructive proof that in four dimensions, the PL and the smooth category are equivalent?

Summary Famously, the categories of 4-dimensional smooth manifolds and 4-dimensional piecewise linear manifolds are equivalent. Is there a constructive proof for this theorem or does it depend on the ...
9
votes
0answers
274 views

Reflection principle for intuitionistic Zermelo–Fraenkel?

The well-known reflection principle for classical Zermelo–Fraenkel states: For any formula $\varphi(x_1,\ldots,x_n)$ of the language of ZFC with free variables $x_1,\ldots,x_n$, ZFC proves $$ \...
3
votes
1answer
521 views

Going beyond the strength of Peano arithmetic “without sets”

First-order arithmetic is fairly weak, as measured for example by its consistency strength. When a stronger theory is desired, it is common to work with (fragments of) second-order arithmetic or set ...
9
votes
2answers
721 views

What did the Intuitionists want to do with applied mathematics?

Oversimplification: Newton & Leibnitz &c build the calculus and other methods that solve a vast number of practical problems. Weierstrass, Dedekind, Cantor &c build a foundation under it ...
12
votes
5answers
732 views

Locales as spaces of ideal/imaginary points

I posted this question on MSE a few days ago, but got no response (despite a bounty). I hope it will get more answers here, but I'm afraid it might not be appropriate as I'm not sure it's actually ...
3
votes
1answer
157 views

Partitions of unity in constructive mathematics

Can someone point me to any substitutes for the partition of unity in Bishop's constructive mathematics? In particular, under what circumstances can we construct a partition of unity subordinate to ...
8
votes
1answer
316 views

Is every set smaller than a regular cardinal, constructively?

Constructively, my only interest in regular cardinals is in terms of the "$\Sigma$-universes" they generate. By a $\Sigma$-universe, I mean a collection of triples $(X,Y,f: X \to Y)$ closed under base ...
19
votes
4answers
1k views

Constructively, is the unit of the “free abelian group” monad on sets injective?

Classically, we can explicitly construct the free Abelian group $\newcommand{\Z}{\mathbb{Z}}\Z[X]$ on a set $X$ as the set of finitely-supported functions $X \to \Z$, and so easily see that the unit ...
20
votes
4answers
1k views

Mathematics without the principle of unique choice

The principle of unique choice (PUC), also called the principle of function comprehension, says that if $R$ is a relation between two sets $A,B$, and for every $x\in A$ there exists a unique $y\in B$ ...
16
votes
1answer
792 views

New articles by Errett Bishop on constructive type theory?

Recently two formerly unknown articles by Errett Bishop (1928-1983) were posted online by Martín Escardó. One is entitled "A general language", deals with constructive type theory, and ...
3
votes
1answer
237 views

Unorthodox constructive reasoning: The Kleene Getaway

KG (the Kleene Getaway) is the name I improvised (in my answer to a question on MO on constructive Perron-Frobenius) for a constructive principle which enables the direct constructive use of a ...
15
votes
2answers
824 views

Constructive proof of a rational version of Perron-Frobenius?

In the following, we work with vectors and matrices whose entries are rational numbers. Inequalities between such vectors are understood to be coordinatewise: e.g., two vectors $a = \left(a_1,a_2,\...
3
votes
0answers
89 views

What's a completely computational/syntactical model for handle decompositions of manifolds?

Simplicial sets, CW complexes Simplicial sets can be described completely algebraically, by specifying a family of sets, and maps between them satisfying certain relations. This description can be ...
5
votes
1answer
383 views

Infinite-time Turing machines and the formal Church's thesis

Infinite-time Turing machines are known to either halt or loop in countable time. In the spirit of double-negation translation, is there a statement which is: classically equivalent to this; ...
18
votes
1answer
840 views

In what ways is ZF (without Choice) “somewhat constructive”

Let me summarize what I think I understand about constructivism: "Constructive mathematics" is generally understood to mean a variety of theories formulated in intuitionist logic (i.e., not assuming ...
11
votes
2answers
831 views

Is the existence of double complement of a set provable in Intuitionistic ZF?

In Powell's article [1] he introduces the axiom of double complement, which says a double complement $\{x : \lnot\lnot(x\in A)\}$ is a set for any set $A$. I can't find similar axiom from other ...
3
votes
1answer
170 views

Fixed-point property and $T_0$ separation property

Each topological space $A$ with fixed-point property is $T_0$ space. Proof: suppose, two different points $a_1$ and $a_2$ belong to the same open subsets of $A$. Then the function $$f(a)= \begin{cases}...