Articles of constructive mathematics

Is ¬¬(¬¬P → P) provable in intuitionistic logic?

I have a feeling it’s not, because ¬¬P → P is not provable. If it is, I’m not sure what kind of reductio I’d need to negate ¬(¬¬P → P). I believe a textbook somewhere said it was provable in intuitionistic logic, so am I missing something or is the textbook wrong?

Does the law of the excluded middle imply the existence of “intangibles”?

First off, I’m not sure if “intangible” is standard terminology, Wikipedia defines an intangible object to be: “objects that are proved to exist, but which cannot be explicitly constructed”. So if someone could point me towards better terminology, I’d appreciate it. The linked article from Wikipedia claims that the axiom of choice implies the existence […]

constructive canonical form of orthogonal matrix

For every orthogonal matrix $Q$ over the reals there is an orthogonal matrix $P$ and a block diagonal matrix $D$ such that $D=PQP^{t}$. Each block in D is either $(1)$, $(-1)$ or a two dimensional block of the form $\left( \begin{array}{cc} \cos(\alpha) & -\sin(\alpha) \\ \sin(\alpha) & \cos(\alpha) \\ \end{array} \right) $. Is there a […]

How can some statements be consistent with intuitionistic logic but not classical logic, when intuitionistic logic proves not not LEM?

I’ve heard that some axioms, such as “all functions are continuous” or “all functions are computable”, are compatible with intuitionistic type theories but not their classical equivalents. But if they aren’t compatible with LEM, shouldn’t that mean they prove not LEM? But not LEM means not (A or not A) which in particular implies not […]

Turning ZFC into a free typed algebra

The standard way of using ZFC to encode the rest of mathematics is sometimes criticized because it introduces unnecessary, strange properties such as, for example $1\in 2$ if we encode integers by ordinals. From a constructivist type theorist’s perspective, uples or functions or complex numbers should have nothing to do with the membership relation, we […]

An explicit construction for an everywhere discontinuous real function with $F((a+b)/2)\leq(F(a)+F(b))/2$?

I would like to know an explicit method on constructing an everywhere discontinuous real function $F$ with the property: $$F((a+b)/2)\leq(F(a)+F(b))/2.$$ There is a non-constructive example (with the inequality been trivial): Take a Hamel basis $S$ of the $\mathbb{Q}$-linear space $\mathbb{R}$, take in $S$ a countably-infinite subset $X=\{x_1, x_2, …\}$, then by multiplying a rational number […]

What exactly are those “two irrational numbers” $x$ and $y$ such that $x^y$ is rational?

This question already has an answer here: Can an irrational number raised to an irrational power be rational? 4 answers

Minimal difference between classical and intuitionistic sequent calculus

Consider propositional logic with primitive connectives $\{{\to},{\land},{\lor},{\bot}\}$. We view $\neg \varphi$ as an abbreviation of $\varphi\to\bot$ and $\varphi\leftrightarrow\psi$ as an abbreviation of $(\varphi\to\psi)\land(\psi\to\varphi)$, etc. The classical sequent calculus LK has rules such as $$\frac{\Gamma, \varphi\vdash \Pi \qquad \Sigma, \psi\vdash \Pi} {\Gamma, \Sigma, \varphi\lor\psi \vdash \Pi}{\lor}L \qquad \frac{\Gamma\vdash\varphi,\Delta}{\Gamma\vdash\varphi\lor\psi,\Delta}{\lor}R_1 \qquad \frac{\Gamma \vdash \psi, \Delta}{\Gamma\vdash\varphi\lor\psi,\Delta}{\lor}R_2 $$ $$ \frac{\Gamma\vdash\varphi,\Delta […]

What does it take to divide by $2$?

Theorem 1 [ZFC, classical logic]: If $A,B$ are sets such that $\textbf{2}\times A\cong \textbf{2}\times B$, then $A\cong B$. That’s because the axiom of choice allows for the definition of cardinality $|A|$ of any set $A$, and for $|A|\geq\aleph_0$ we have $|\textbf{2}\times A|=|A|$. Theorem 2: Theorem 1 still holds in ZF with classical logic. This is […]

How do we construct the coslice category $C / \bf{C}$ given $\textbf{C}/C$ and prove that the two are equal?

The coslice category $C/\bf{C}$ under an object $C \in \bf{C}$ has as objects arrows $f$ in $\bf{C}$ such that $\textbf{dom}(f) = C$ and as arrows, arrows $a: f \to g$ which are arrows $a$ in $ \bf{C}$ such that $af = g$. So I want to construct this coslice category from the slice category $\textbf{C}/C$ […]