Formal theories of arithmetic | Real algebraic geometry | Computational complexity theory

Existential theory of the reals

In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form where the variables are interpreted as having real number values, and where is a quantifier-free formula involving equalities and inequalities of real polynomials. A sentence of this form is true if it is possible to find values for all of the variables that, when substituted into formula , make it become true. The decision problem for the existential theory of the reals is the problem of finding an algorithm that decides, for each such sentence, whether it is true or false. Equivalently, it is the problem of testing whether a given semialgebraic set is non-empty. This decision problem is NP-hard and lies in PSPACE. Thus it has significantly lower complexity than Alfred Tarski's quantifier elimination procedure for deciding statements in the first-order theory of the reals without the restriction to existential quantifiers. However, in practice, general methods for the first-order theory remain the preferred choice for solving these problems. Many natural problems in geometric graph theory, especially problems of recognizing geometric intersection graphs and straightening the edges of graph drawings with crossings, may be solved by translating them into instances of the existential theory of the reals, and are complete for this theory. The complexity class , which lies between NP and PSPACE, has been defined to describe this class of problems. (Wikipedia).

Video thumbnail

Real Numbers

http://mathispower4u.wordpress.com/

From playlist Integers

Video thumbnail

Difficulties with real numbers as infinite decimals ( I) | Real numbers + limits Math Foundations 91

There are three quite different approaches to the idea of a real number as an infinite decimal. In this lecture we look carefully at the first and most popular idea: that an infinite decimal can be defined in terms of an infinite sequence of digits appearing to the right of a decimal point

From playlist Math Foundations

Video thumbnail

Imaginary Numbers, Functions of Complex Variables: 3D animations.

Visualization explaining imaginary numbers and functions of complex variables. Includes exponentials (Euler’s Formula) and the sine and cosine of complex numbers.

From playlist Physics

Video thumbnail

How real are the real numbers, really?

We usually say that infinity isn't real, but here we'll see how crucial it is to have one very big infinity for the real world; there is an infinite number of numbers. But why do we need real numbers at all? Aren't rational numbers enough? And what about hyperreal numbers? What we'll see

From playlist Some fun math videos about approximation

Video thumbnail

Imaginary Numbers Are Real [Part 1: Introduction]

For early access to new videos and other perks: https://www.patreon.com/welchlabs Want to learn more or teach this series? Check out the Imaginary Numbers are Real Workbook: http://www.welchlabs.com/resources. Imaginary numbers are not some wild invention, they are the deep and natural

From playlist Imaginary Numbers are Real

Video thumbnail

Introducing Infinity | Set Theory, Section 3.1

In this video we define inductive sets, the natural numbers, the axiom of infinity, and the standard order relation on the natural numbers. My Twitter: https://twitter.com/KristapsBalodi3 Intro (0:00) Defining Natural Numbers as Sets (1:19) Definition of Inductive Sets (5:07) The Axiom o

From playlist Axiomatic Set Theory

Video thumbnail

Foundations S2 - Seminar 3 - Skolemisation

A seminar series on the foundations of mathematics, by Will Troiani and Billy Snikkers. This season the focus is on the proof of the Ax-Grothendieck theorem: an injective polynomial function from affine space (over the complex numbers) to itself is surjective. This week Will started into t

From playlist Foundations seminar

Video thumbnail

Barbara Koenig: Fixpoint games

HYBRID EVENT Recorded during the meeting "19th International Conference on Relational and Algebraic Methods in Computer Science" the November 5, 2021 by the Centre International de Rencontres Mathématiques (Marseille, France) Filmmaker: Guillaume Hennenfent Find this video and other t

From playlist Logic and Foundations

Video thumbnail

Imaginary Numbers Are Real [Part 11: Wandering in 4 Dimensions]

More information and resources: http://www.welchlabs.com Supporting Code: https://github.com/stephencwelch/Imaginary-Numbers-Are-Real Imaginary numbers are not some wild invention, they are the deep and natural result of extending our number system. Imaginary numbers are all about the di

From playlist Imaginary Numbers are Real

Video thumbnail

Foundations S2 - Seminar 4 - Lower Lowenheim-Skolem

A seminar series on the foundations of mathematics, by Will Troiani and Billy Snikkers. In this lecture Will proves the lower Lowenheim-Skolem theorem. The webpage for this seminar is https://metauni.org/foundations/ You can join this seminar from anywhere, on any device, at https://www.

From playlist Foundations seminar

Video thumbnail

Abraham Robinson’s legacy in model theory and (...) - L. Van den Dries - Workshop 3 - CEB T1 2018

Lou Van den Dries (University of Illinois, Urbana) / 27.03.2018 Abraham Robinson’s legacy in model theory and its applications ---------------------------------- Vous pouvez nous rejoindre sur les réseaux sociaux pour suivre nos actualités. Facebook : https://www.facebook.com/InstitutHe

From playlist 2018 - T1 - Model Theory, Combinatorics and Valued fields

Video thumbnail

Model Theory of Fields with Virtually Free Group Action - Ö. Beyarslan - Workshop 3 - CEB T1 2018

Özlem Beyarslan (Boğaziçi University) / 29.03.2018 Model Theory of Fields with Virtually Free Group Action This is joint work with Piotr Kowalski. A G-field is a field, together with an acion of a group G by field automorphisms. If an axiomatization for the class of existentially closed

From playlist 2018 - T1 - Model Theory, Combinatorics and Valued fields

Video thumbnail

Multi-valued algebraically closed fields are NTP₂ - W. Johnson - Workshop 2 - CEB T1 2018

Will Johnson (Niantic) / 05.03.2018 Multi-valued algebraically closed fields are NTP₂. Consider the expansion of an algebraically closed field K by 𝑛 arbitrary valuation rings (encoded as unary predicates). We show that the resulting structure does not have the second tree property, and

From playlist 2018 - T1 - Model Theory, Combinatorics and Valued fields

Video thumbnail

Touching Infinity: It's Not Out of Reach

The conventional way to represent the Real Number system is to think of the numbers as corresponding to points along an infinite straight line. The problem is that in this representation there is no place for "infinity". Infinity is not a real number. This video shows an alternate visua

From playlist Lessons of Interest on Assorted Topics

Video thumbnail

Existential physics: answering life's biggest questions - with Sabine Hossenfelder

Join theoretical physicist Sabine Hossenfelder as she draws on the latest research in quantum mechanics, black holes, string theory and particle physics to explore what modern physics can tell us about the big questions. Watch the Q&A here: https://youtu.be/QiE6P3EcKRk Sabine's book "Exis

From playlist Ri Talks

Video thumbnail

Imaginary Numbers Are Real [Part 12: Riemann's Solution]

Want to experiment with Riemann's idea yourself? You can download your very own copy of of the final w-planes to experiment with here: http://www.welchlabs.com/blog/2016/6/30/imaginary-numbers-are-real-part-12-riemanns-solution Supporting Code: https://github.com/stephencwelch/Imaginary-N

From playlist Imaginary Numbers are Real

Video thumbnail

Martin Rees on the Future of Cosmology | Closer To Truth Live

Given the remarkable advances in precision cosmology over the past few decades, can we forecast what we might discover in 10 or 20 years or even 30 years at mid-century? What are the categories of human destruction and what are the odds of each? What is the far far future of life and senti

From playlist Closer To Truth Chats

Video thumbnail

Alexandra SHLAPENTOKH - Defining Valuation Rings and Other Definability Problems in Number Theory

We discuss questions concerning first-order and existential definability over number fields and function fields in the language of rings and its extensions. In particular, we consider the problem of defining valuations rings over finite and infinite algebraic extensions

From playlist Mathematics is a long conversation: a celebration of Barry Mazur

Video thumbnail

Difficulties with real numbers as infinite decimals (II) | Real numbers + limits Math Foundations 92

This lecture introduces some painful realities which cast a long shadow over the foundations of modern analysis. We study the problem of trying to define real numbers via infinite decimals from an algorithmic/constructive/computational point of view. There are many advantages of trying

From playlist Math Foundations

Video thumbnail

The Social Context of Philosophy - Ernest Gellner & Bryan Magee (1978)

In this program, Ernest Gellner discusses the social context of modern philosophy with Bryan Magee. This is from a 1978 series on Modern Philosophy called Men of Ideas. #Philosophy #BryanMagee

From playlist Bryan Magee Interviews - Modern Philosophy: Men of Ideas (1977-1978)

Related pages

Real closed field | Quantifier elimination | Graph (discrete mathematics) | Elementary function | Intersection graph | Quantum logic | Undecidable problem | Homeomorphism | Planar graph | Visibility graph | Decision problem | Art gallery problem | Complete (complexity) | Lattice (order) | Inequality of arithmetic and geometric means | Polynomial | Polynomial-time reduction | Dimension (graph theory) | Asymptotic computational complexity | PSPACE | Slope number | Theory (mathematical logic) | Axiom schema | Unit distance graph | Formal language | Golden ratio | Alfred Tarski | Convex polytope | Cylindrical algebraic decomposition | Double exponential function | Line segment | Sentence (mathematical logic) | Integer | Real number | Matrix completion | Steinitz's theorem | Semialgebraic set | Geometric graph theory | Cross product | NP (complexity) | Hilbert's tenth problem | Diophantine set | List of first-order theories | Nash equilibrium | Time complexity | Diophantine equation | Fáry's theorem | Mathematical logic | Logical connective | Computational complexity theory | Unit disk graph | Arrangement of lines | Algorithm | Crossing number (graph theory) | Complexity class