Patrick Speissegger
This post provides the details for the Divisibility lesson. Let $F$ be a field and $f,g \in F[X]$. Definition 1 $f$ divides $g$, written $f|g$, if $g = hf$ for some $h ∈ F[X]$. We also say that $g$ is a multiple of $f$. If $\deg(f) \ge 1$, we say that $f$ is prime or…
Can the 0 gate be built as a circuit using only reversible gates? in other words, is there a classical circuit $C$ of width $n$ (unkown), built entirely from reversible gates, such that its first wire produces output 0 no matter what the input is? The answer is no! To see why, let’s look at…
To wrap up the notes on o-minimal structures, let’s consider two questions that were still open at the end of the last millennium: Questions Does every o-minimal expansion of the real field admit analytic cell decomposition? Is there a unique maximal o-minimal expansion of the real field? The answer to both questions is “no”, and…
Let $\Delta_n$ be a collection of subsets of $\RR^n$, for $n \in \NN$, and set $\Delta = (\Delta_n)_{n \in \NN}$. As usual, we refer to the elements of the various $\Delta_n$ as $\Delta$-sets, and we call $\Delta$-sets that are manifolds $\Delta$-manifolds. We assume the following axioms for $\Delta$-sets: $(\Delta 1)$ every semialgebraic set is a…
Finally, we get to Step 3 of the proof of this theorem: establishing a theorem of the complement for the “right” collection of existentially definable sets. We start with a few exercises. Exercises Let $\tau_n:\RR^n \into (-1,1)^n$ be the semialgebraic diffeomorphism defined here. Show that, for every semialgebraic set $A \subseteq \RR^n$, the set $\tau_n(A)$…