Dynamical methods were designed to eliminate the ideal objects abstract algebra abounds with. Typically granted by an incarnation of Zorn's Lemma, those ideal objects often serve for proving the semantic conservation of additional non-deterministic sequents, that is, with finite but not necessarily singleton succedents. Eliminating ideal objects dynamically was possible also because (finitary) coherent or geometric logic predominates in that area: the use of a non-deterministic axiom can be captured by a finite branching of the proof tree.

Abstract The semantics in ordered abelian groups Scott proposed for Łukasiewicz’s many-valued logic fails to be sound for one direction of one of the rules Scott gave for implication. We show this by a counterexample Urquhart has used to justify that in his own semantics, every formula has to have a least point at which it is valid. While this condition would make Scott’s semantics sound, it would cause a problem with its completeness. The question arises whether one can still amend Scott’s semantics so as to make it both sound and complete or better stick to Urquhart’s semantics anyway.

This special issue contains selected papers from the International Workshop on Proof, Structure, and Computation (PSC) held in Vienna on 17–18 July 2014, within the Vienna Summer of Logic (VSL). PSC was a CSL–LICS-affiliated workshop on the extraction of computational content from proofs. The focus is on the computational aspects of proofs and the specification of the structures involved; the topics of interest are proof theory, program extraction, constructive mathematics, topology and computation, realizability semantics, coalgebra and computation, categorical models and domain theory. The extraction of computational content from proofs has a long tradition in logic, but usually depends on a concrete encoding that allows us to turn proofs into algorithms. A recent trend in this field is the departure from such encoding, which not only makes it simpler to represent the mathematical content, but also makes the extracted computational content encoding independent. This shift in focus allows us to focus on what is relevant: the computational aspects of proofs and the specification (not representation) of the structures involved. We now have growing evidence that this move from representations (e.g. the signed-digit representation of the reals) to axioms (e.g. of the real numbers) is possible. This development largely parallels the step from assembler to high-level languages in programming. As a by-product, this move has already opened up the possibility to gain computational information from axiomatic proofs in more abstract and genuinely structural areas of mathematics such as algebra and topology.

We give a constructive proof showing that every finitely generated polynomial ideal has a Gröbner basis, provided the ring of coefficients is Noetherian in the sense of Richman and Seidenberg. That is, we give a constructive termination proof for a variant of the well-known algorithm for computing the Gröbner basis. In combination with a purely order-theoretic result we have proved in a separate paper, this yields a unified constructive proof of the Hilbert basis theorem for all Noether classes: if a ring belongs to a Noether class, then so does the polynomial ring. Our proof can be seen as a constructive reworking of one of the classical proofs, in the spirit of the partial realisation of Hilbert's programme in algebra put forward by Coquand and Lombardi. The rings under consideration need not be commutative, but are assumed to be coherent and strongly discrete: that is, they admit a membership test for every finitely generated ideal. As a complement to the proof, we provide a prime decomposition for commutative rings possessing the finite-depth property.

Many a concrete theorem of abstract algebra admits a short and elegant proof by contradiction but with Zorn's Lemma (ZL). A few of these theorems have recently turned out to follow in a direct and elementary way from the Principle of Open Induction distinguished by Raoult. The ideal objects characteristic of any invocation of ZL are eliminated, and it is made possible to pass from classical to intuitionistic logic. If the theorem has finite input data, then a finite partial order carries the required instance of induction, which thus is constructively provable. A typical example is the well-known theorem "every nonconstant coefficient of an invertible polynomial is nilpotent".

Noether classes of posets arise in a natural way from the constructively meaningful variants of the notion of a Noetherian ring. Using an axiomatic characterisation of a Noether class, we prove that if a poset belongs to a Noether class, then so does the poset of the finite descending chains. When applied to the poset of finitely generated ideals of a ring, this helps towards a unified constructive proof of the Hilbert basis theorem for all Noether classes.

Abstract We deal with a restricted form WC-N′ of the weak continuity principle, a version BT′ of Baire's theorem, and a boundedness principle BD-N. We show, in the spirit of constructive reverse mathematics, that WC-N′, BT′ + ¬LPO and BD-N + ¬LPO are equivalent in a constructive system, where LPO is the limited principle of omniscience.

Abstract The existence and uniqueness of a maximum point for a continuous real–valued function on a metric space are investigated constructively. In particular, it is shown, in the spirit of reverse mathematics, that a natural unique existence theorem is equivalent to the fan theorem.

Abstract The Dedekind cuts in an ordered set form a set in the sense of constructive Zermelo–Fraenkel set theory. We deduce this statement from the principle of refinement, which we distill before from the axiom of fullness. Together with exponentiation, refinement is equivalent to fullness. None of the defining properties of an ordering is needed, and only refinement for two–element coverings is used. In particular, the Dedekind reals form a set: whence we have also refined an earlier result by Aczel and Rathjen, who invoked the full form of fullness. To further generalise this, we look at Richman's method to complete an arbitrary metric space without sequences, which he designed to avoid countable choice. The completion of a separable metric space turns out to be a set even if the original space is a proper class: in particular, every complete separable metric space automatically is a set.