User hurkyl - MathOverflow

Infinite mathematics as non-standard finite mathematics?

2012-03-03T18:11:09Z

I have in mind something like the following:

Start with some suitable version of "finite" mathematics. Some possibilities might be maybe ZFC with a suitable anti-infinity axiom, the topos $\mathbf{FinSet}$, Peano arithmetic, Turing machines... something whose objects are suitably "finite".

Then, posit the existence of both a standard and a non-standard model.

Now, in this setting, where we have access both to a standard model and a non-standard extension, use the non-standard objects as proxies for infinite objects (e.g. maybe some sort of set theory that has a set of natural numbers), and develop ordinary mathematics this way.

Has anybody worked on such a thing? Does anyone know of references of it being done? Or suggestions that it can't work out?

(P.S. I wasn't sure how to tag this....)

Edit: After more thought and reviewing the answers thus far, I think I can state an example of the sort of thing i was imagining. Define a first-order theory with two types $T_1$ and $T_2$, two binary relation symbols $\in_1, \in_2$ (one for each sort), and a map $\tau : T_1 \to T_2$ satisfying:

$(T_1, \in_1)$ satisfies the axioms of finite set theory
$(T_2, \in_2)$ satisfies the axioms of finite set theory
$\tau$ is injective
$\tau$ is not surjective
$\tau$ satisfies an axiom schema that says it's an elementary embedding

and the question is to what extent we can develop infinite set theory in this theory.

Answer by Hurkyl for Fastest way to factor integers < 2^60

2012-11-21T19:17:44Z

If your numbers are generated in a regular pattern, you could use a sieve to find lots of medium sized factors fairly quickly.

Free CCC or topos on a cartesian category

2012-06-10T08:01:28Z

$\def\sC{\mathcal{C}}\def\sD{\mathcal{D}}\def\Set{\mathbf{\mathrm{Set}}}\DeclareMathOperator{\Sub}{Sub}\def\op{\circ}$I have a Cartesian category $\sC$. I would like to embed $\sC$ into a cartesian closed category (or better, a topos) $\sD$. However, $\Set^{\sC^\op}$ is bigger than I want -- in particular, I would like my embedding to preserve subobject lattices: $\Sub_\sC(x) \cong \Sub_\sD(x)$ for each object $x$ of $\sC$. I think I would also like it to preserve whatever limits already exist in $\sC$ and be a full embedding.

If $\sC$ already has a subobject classifier, can I hope for it to still be so in a topos $\sD$?

Is there a standard construction to construct a CCC or a Topos $\sD$ out of a Cartesian category $\sC$? What properties can I expect out of such constructions? Is there any hope that it could satisfy the properties I ask for?

If it matters, I'm particularly interested in the case where $\sC$ is the category of semi-algebraic varieties. That is, the category of definable objects in the first-order theory of real closed fields.

Answer by Hurkyl for Reasonable implementation of finding Gröbner bases over non-field coefficient rings

2012-05-20T10:55:01Z

magma can compute Gröbner bases over a number of different types of coefficient rings; see the magma handbook.

As a general principle, if $A = R / J$ for some nice $R$, then it is often fruitful to try and answer questions about $A[T]$ by transplanting them to questions about $R[T]$. e.g. to find the irreducible components of $\mathop{Spec} A[T]/I$, it suffices to find a suitable decomposition of the ideal $\bar{I} \subseteq R[T]$, where $\bar{I}$ is the preimage of $I$ under the map $R[T] \to A[T]$.

Answer by Hurkyl for Examples of interesting false proofs

2012-04-23T06:44:54Z

Theorem: All people have the same eye color.

Proof by induction: we prove the statement "All members of any set of people have the same eye color". This is clearly true for any singleton set.

Now, assume we have a set $S$ of people, and the inductive hypothesis is true for all smaller sets. Choose an ordering on the set, and let $S_1$ be the set formed by removing the first person, and $S_2$ be the set formed by removing the last person.

All members of $S_1$ have the same eye color, and also for $S_2$. However, $S_1 \cap S_2$ has members from both sets, so all members of $S$ have the same eyecolor. $\square$

Answer by Hurkyl for Why do we ignore non-standard finite sets in ordinary mathematics?

2012-03-18T22:47:18Z

I'm used to formal logic being formulated internally. The theory of groups is not an external notion to whatever mathematical universe you're working in -- instead, it is an (internal) set of strings in a set-theoretic universe, or a finite-limit sketch in a category-theoretic universe. Models are then merely set functions or functors with appropriate properties. And proof theory and model theory are all defined internally to the universe.

In particular, for any internal natural number $n$, there are perfectly good formulas $\varphi(g_1, g_2, \cdots, g_n)$.

If you had an external notion of natural number (and a corresponding external notion of formal logic), then the internally constructed version could very well be infinitary when viewed from the external perspective. But only when viewed from the external perspective: it is still finitary when viewed internally to the model.

Answer by Hurkyl for Can ZFC prove "false theorems", and still be consistent? (was "Junk Theorems" follow up)

2012-03-13T00:13:56Z

Does Skolem's paradox fit the kind of thing you were thinking? Of course, this is also a type error; it's just a lot easier to miss.

Answer by Hurkyl for Set theories without "junk" theorems?

2012-03-10T19:07:33Z

What you are describing is the idea of "breaking" an abstraction. That there is an abstraction to be broken is pretty much intrinsic to the very notion of "model theory", where we interpret the concepts in one theory in terms of objects and operations in another one (typically set theory).

It may help to see a programming analogy of what you're doing:

uint32_t x = 0x12345678;
unsigned char *ptr = (unsigned char *) x;
assert( ptr[0] == 0x12 || ptr[0] == 0x78 );  // Junk!

const char text[] = "This is a string of text.";
assert( text[0] == 84 );  // Junk!

// Using the GMP library.
mpz_t big_number;
mpz_init_ui(big_number, 1234);
assert(big_number[0]._mp_d[0] == 1234); // Junk!

All of these are examples of the very same thing you are complaining about in the mathematical setting: when you are presented with some sort of 'type', and operations for working on that type, but it is actually implemented in terms of some other underlying notions. In the above:

I've broken the abstraction of a uint32_t representing a number modulo $2^{32}$, by peeking into its byte representation and extracting a byte.
I've broken the abstraction of a string being made out of characters, by using knowledge that the character 'T' and the ASCII value 84 are the same thing
In the third, I've broken the abstraction that big_number is an object of type integer, and peeked into the internals of how the GMP library stores such things.

In order to avoid "junk", I think you are going to have to do one of two things:

Abandon the notion of model entirely
Realize that you were actually lying in your theorems: it's not that $2 \in 3$ for natural numbers $2$ and $3$, but $i(2) \in i(3)$ for a particular interpretation $i$ of Peano arithmetic. Maybe making the interpretation explicit would let you be more comfortable?

(Or, depending on exactly what you mean by the notation, the symbols $2$ and $3$ aren't expressing constants in the theory of natural numbers, but are instead expressing constants in set theory)

Answer by Hurkyl for two real closed fields- algebraic elements

2011-12-12T15:28:41Z

What do you mean by "algebraic elements of $R_2$"? Do you mean those elements that are algebraic over $R_1$? Then the answer is yes. There is a straightforward proof: the only algebraic extension of $R_1$ is $R_1[i]$, and $i \notin R_2$. (where $i^2 = -1$)

What is the analog of a topos in quantum logic?

2011-09-07T04:06:13Z

If I'm studying classical mechanics, we might start by viewing propositions as true/false valued questions on points of phase space.

Then, if I'm interested in a proposition-oriented view of things, I might flip things around and ask what points of phase space correspond to propositions, and observe a Boolean algebra of subsets of phase space. Then I might think about things that aren't propositions (like "x-coordinate of the 7th particle") which are clearly functions on phase space and I start turning the mathematical crank, and eventually decide that I ought to interpret classical mechanics in terms of the topos of sheaves on phase space. (with the discrete topology -- or maybe I consider the usual topology with interesting consequences)

If I want to carry out this procedure quantum physics, I somewhat get the idea that I should associate propositions with projection operators in a C*-algebra -- but where to go from here is unclear. I've only managed to find material talking about the very special case where we consider working with orthogonal projections -- and nothing on what higher structure should be built on top of this.

Just because it sounds natural, I imagine the answer to my question ought to be something like "The category of Hilbert-space representations of the C*-algebra", but I'm having difficulty seeing how one would go about interpreting quantum mechanics in this category.

Can anyone elaborate on how the interpretation would go or point me at references or give the right answer to my question?

(I hope this is the right place -- I'm asking here since physics.stackexchange.com didn't appear to have people knowledgeable about category theory)

Answer by Hurkyl for Symbolic powers in regular local rings

2011-05-18T07:02:15Z

The short answer to what you're missing is that you ignored the dimension criterion. $R/\mathfrak{m}$ is zero-dimensional, so the only prime ideal $\mathfrak{p}$ to which the the theorem would apply is $\mathfrak{p} = (0)$.

Answer by Hurkyl for Natural transformations as categorical homotopies

2011-05-09T10:34:09Z

Once you learn a subject, you can think about things in whatever way is most pleasing or helpful for solving a problem. Fixing a fact as a definition is pedagogy -- something to help those learning the subject.

I can't really speak for how others learn, but I'm not sure recognizing natural transformations as being described by functors $\mathcal{C} \times 2 \to \mathcal{D}$ would be very useful before one starts seriously thinking in terms of the 2-category of categories.

I confess I would almost turn your question on its head -- I far more frequently want to think of a homotopy between functions $f,g:X \to Y$ as being a function from $X$ to paths in $Y$, or sometimes as a function from $[0,1]$ to $Y^X$, and feel the usual definition as a function $X \times [0,1] \to Y$ more as being a much simpler way to state the technical details. I saw the analogy with homotopy early in learning about categories, and I don't think seeing natural transformations defined as functors $\mathcal{C} \times 2 \to \mathcal{D}$ would have helped me make the analogy. (But, for the record, I am very much not an algebraic topologist)

Answer by Hurkyl for How much larger is the powerset of a transfinite set?

2011-05-09T05:36:21Z

I think if you really try to wrap your head around the fact there is no surjection $S \to \mathcal{P}(S)$, you will see that it already does imply that the cardinality of $\mathcal{P}(S)$ must be, in some sense, "vastly larger". You shown any particular alleged surjection must be missing one element. But it's easy enough to find a new alleged surjection whose image contains the new element in addition to all of the previous ones' -- and that still isn't surjective. And so forth.

You can rearrange your argument to turn it into a diagonal argument. One can identify subsets of $S$ with their characteristic functions $S \to 2 = \{ 0,1 \}$. For any function $f : S \to 2^S$, the function $g(s) := 1 - f(s)(s)$ is not contained in the image. Proof: if $f(t)=g$, then $ f(t)(t) = g(t) = 1 - f(t)(t)$.

Note that any permutation $\pi$ of $S$ gives another element $g_\pi(s) := 1 - f(\pi(s))(s)$ which is also not in the image of $f$.

If you use the axiom of choice, then there is a bijection $2^S \to 3^S$. If you replace $2^S$ with $3^S$, then you can do the same thing you wanted to do with Cantor's argument showing the naturals are bigger than the reals, by making many choices of how to change the diagonal.

Answer by Hurkyl for What does it mean geometrically that an element in a domain is irreducible?

2011-05-05T22:14:08Z

In the dictionary in my head, I think of elements or $R$ as functions on $\mathop{\mathrm{Spec}} R$ -- i.e. as being analogous to scalar fields on manifolds. In my mind, this lessens the expectation that their properties should be directly interpretable in terms of subschemes of $\mathop{\mathrm{Spec}} R$.

That said, there is still correlation between the reducilibty of an element of $R$ and the reducibility of its zero set; the game just becomes cataloging the differences.

One of them is that we should be looking at the subscheme, not the subspace. For example, in the plane with coordinate ring $k[x,y]$, the origin $V(x,y)$ and the scheme $V(y, y-x^2)$ are different; the latter is the "double point" over $k$. The geometry remembers the difference between primary and prime ideals, even though the topology forgets.

That said, the real missing ingredient is the Picard group -- your reducibility criterion is not merely splitting $\mathop{\mathrm{Div}}(f)$ into a sum of nonzero effective divisors, but those divisors must also vanish into the Picard group.

Anyways, your analog of algebraic number theory for the circle is to consider the norm from $\mathbb{R}(x,y)$ down to $\mathbb{R}(x)$. If $(x,1-y)$ was principal with generator $f(x) + g(x) y$, then for some nonzero $a \in \mathbb{R}$: $$ a x = N(f(x) + g(x) y) = \frac{ (x^2 - 1) g(x)^2 + f(x)^2 }{g(x)^2} $$ From which you argue $g(x) = 1$, and $f(x)$ must be linear with leading coefficient $\mathbb{i}$, an impossibility.

Aside: I feel like there should be some sort of Galois descent argument to compare $\mathbb{C}[x,y]$ with $\mathbb{R}[x,y]$, but it's beyond my expertise to see how it should go.

Answer by Hurkyl for Cayley's Theorem and the Yoneda Lemma

2011-05-02T02:09:52Z

One can define the notion of a right category action on a set. This involves assigning a domain (an object of the category) to each element of the set, and a partial multiplication of elements by arrows defined whenever the domain of an element is the codomain of an arrow. The prototypical example is a category acting by composition on its set of arrows.

The category of right $\mathbf{C}$-sets winds up being equivalent to the category of functors $\mathbf{C} \to \mathbf{Set}$. The reverse equivalence applied to Yoneda of an object $A$ is essentially the set of arrows with codomain $A$, with $\mathbf{C}$ acting by composition.

I believe there is also an equivalence of left-right $\mathbf{C}$-sets to the category of functors $\mathbf{C}^\circ \times \mathbf{C} \to \mathbf{Set}$. The action of $\mathbf{C}$ on itself corresponds to $\text{Hom}_{\mathbf{C}}(-,-)$, which in turn is the adjoint transpose of the Yoneda embedding.

Answer by Hurkyl for Kuratowski's definition of ordered pairs

2011-04-24T01:49:32Z

How one models ordered pairs is not particularly important; what matters is the existence of a pairing function $(-,-)$ along with functions $\text{first}(-)$ and $\text{second}(-)$ satisfying the requisite properties.

Which definition you use only matters for a brief period between the definition and the point where its properties have been proven, at which point you promptly forget the details of the definition -- so the only real point of deliberating definitions is to make this period as painless as possible for others.

I haven't thought through all of the possibilities, but I will offer an example that $\text{first}(-)$ is tricky to define for your definition 1. The 'obvious' choice seems to be $$ z = \text{first}(P) \equiv z \in P \wedge \exists a: z \in a \in P $$ which turns out to depend on the axiom of foundation to be well-defined! (consider a $y$ satisfying $y = \{ x, y \}$) I, personally, would have more confidence in being correct if I was trying to develop the properties of ordered pairs from definitions 2 or 4, rather than from 1 or 3.

Answer by Hurkyl for Definition of Initial&Terminal Objects in an ``Object-Free'' Category

2011-04-07T01:56:41Z

As the others have said, the object-free definition can always define objects later and do everything normally. One might ask if there was a different-than-normal definition that was more arrow-like. For example:

A morphism $f$ is "terminating" if, for every morphism $g$, there exists a unique morphism $h$ such that $h \circ g$ and $f$ have the same target.

So, the target of $f$ is a terminal object, and $f$ itself is the unique projection from its source. But this seems like a superficial change to me. Maybe someone else knows something better?

Answer by Hurkyl for Why don't ideals and quotients work well for categories?

2011-03-31T23:48:45Z

An operation that insists on making certain objects equal breaks the spirit of category theory -- we should only insist that they be equal... up to isomorphism. To me, it seems more natural to add more morphisms to accomplish this effect, rather than trying modding objects out by an equivalence relation.

There are operations that can do this. Localization, for example, formally inverts a class of morphisms, making the corresponding objects isomorphic. I once saw a construction that formally added isomorphisms to create a natural isomorphism from the identity functor to a given endofunctor.

But, even modding out by an equivalence relation can have this effect. If the composites $A \xrightarrow{f} B \xrightarrow{g} A$ and $B \xrightarrow{g} A \xrightarrow{f} B$ are congruent to the corresponding identity morphisms, then $A \cong B$ in the quotient category.

Answer by Hurkyl for Why is the exterior differentiation operator sometimes visualized as the "boundary"?

2011-03-31T04:30:24Z

Whether a visualization is good really is a subjective thing. This visualization of $d$ works for the author, but it doesn't work for me. If you still find it perplexing after mulling it over, you're probably better off investing your energies into trying to understand $d$ directly rather than into trying to wrap your head around the visualization.

If you still seek visualizations, you could look to other properties of differential geometry to base them on instead of the idea of contour lines for a function.

One such property is that you can integrate an $n$-form over an $n$-dimensional region, so you can try and imagine $n$-forms as a way to measure things. If you can wrap your head around that, then, as in Steve's comment, you can try using Stokes' theorem visualize how $d$ must look.

Answer by Hurkyl for Understanding the countable ordinals up to $\epsilon_{0}$

2011-02-20T17:09:37Z

The lack of an infinite descending sequence is because every ordinal is well-ordered; such a thing simultaneously must and cannot contain a minimum element.

Comment by Hurkyl

2012-11-21T19:19:13Z

While SQUFOF is good, I confess that I would have expect a good ECM implementation to become better before the $2^{60}$ cutoff.

Comment by Hurkyl

2012-06-10T12:08:13Z

@Michal: Unless I'm misunderstanding, you cannot expect subobject lattices to be CHA's in general: I know I'm not interested in Grothendieck toposes, and a quick look at references only state HA in the general case. I believe that in my particular case of interest -- and any syntactic site -- the subobject lattices are Heyting, so the possibility of a topos is still open.

Comment by Hurkyl

2012-05-02T07:34:25Z

It's definitely not $\mathbb{C}[x,y,x',y']_{(x,y,x',y')}$. If anything simple, it is probably the localization of $\mathbb{C}[x,y,x',y']$ formed by inverting polynomials of the form $f(x,y)$ or $f(x',y')$ where $f(0,0) \neq 0$.

Comment by Hurkyl

2012-04-09T17:33:40Z

For completeness, if you replace the condition $x \in [1, \sqrt{p})$ with $|x| \in [1, \sqrt{p})$, you do cover everything.

Comment by Hurkyl

2012-03-18T22:38:37Z

@David: Not in this case. In non-standard analysis, the non-standard model is chosen to be elementary equivalent to the standard one. Any (standard) predicate is satisfied by the standard model if and only if it is satisfied by the non-standard model. In particular, if the predicate P(n) = "n is a contradiction in ZFC" is standard, then $\forall n \in \mathbb{N}: P(n) \Leftrightarrow \forall n \in {}^\star\mathbb{N}: P(n)$.

Comment by Hurkyl

2012-03-15T01:52:37Z

... and conversely, if your $(\mathbb{N}, 0, +, \cdot, \leq)$ was meant to be an external construction, then you have no guarantee that every element of $\omega$ corresponds to an element of $\mathbb{N}$.

Comment by Hurkyl

2012-03-15T01:51:37Z

@Michael: The construction of $(\mathbb{N}, 0, +, \cdot, \leq)$ you refer to: if you are doing that by invoking a theorem of model theory as formulated internally to your model of ZFC, then everything you've said is correct... internally to your model of ZFC. However, if you have some external notion of the natural numbers, you have no guarantee that every element of $\mathbb{N}$ corresponds to an external natural number.

Comment by Hurkyl

2012-03-15T00:42:02Z

@Michael: With what model of the natural numbers are you measuring well-foundedness of $V_\omega$ in your model of ZFC? The specific $\omega$ from your model of ZFC, right?

Comment by Hurkyl

2012-03-14T11:37:46Z

In ZFC+~GC, there is a finite counterexample.

Comment by Hurkyl

2012-03-14T03:35:02Z

In fact, isn't it true that ZFC+~GC can prove ~GC provable by PA?

Comment by Hurkyl

2012-03-14T03:28:32Z

@Steven: To give an example of a differing opinion, I would consider that argument a type-error. If GC is unprovable in ZFC, that means GC is true in certain models of PA (as constructed in certain models of ZFC) -- to say GC is true in an absolute sense goes too far.

Comment by Hurkyl

2012-03-12T21:15:04Z

Maybe I'm being a bit unfair, I've generally found that such sentiment belies a profound misunderstanding of mathematics -- e.g. the idea that mathematicians are incapable of considering the notion of approximation.

Comment by Hurkyl

2012-03-10T19:35:54Z

Here's a question to ponder: does making a model of peano arithmetic out of the real numbers count as being in the same 'universe'? If so, is $\sqrt{11 - 6 \sqrt{2}} + \sqrt{11 + 6 \sqrt{2}} = 6$ a junk theorem?

Comment by Hurkyl

2012-03-04T18:42:59Z

I wasn't entirely sure what my system was either. But now I think I have a better idea of what I was trying to conceive, and have edited my post to reflect it.

Comment by Hurkyl

2012-03-04T16:43:31Z

+1 for being an answer to the implied question "... or tell me something similar that I'd be interested in". However, I'm a little skeptical of how to "find" the copy of infinitary set theory -- specifically, I'm skeptical that you can find just from first-order logic, the two models, and the transfer principle. Wouldn't you need to step out into the ambient set theory to find the model and prove things about it?