MathMart

Karma: 64

MathMart 3 Sep 2026 18:48 UTC
1 point
0
on: Insights into Curry’s Paradox?
To get a better understanding of the details of self-reference in mathematical logic, if you know how to code, I’d recommend looking at quines, and programming one yourself in your favorite language.

When made rigorous, sentences like “this sentence is unprovable” essentially translate to the sentence S = “the sentence output by the program P is unprovable”, where P happens to be a quine which outputs S. So if you understand quines, then you already understand the basic idea behind self-referential statements in logic.

It will probably help at first to simply take for granted that peano arithmetic is capable of talking about computer programs and their outputs. The specific details of how peano arithmetic can do this will sometimes be important, but you can get pretty far without knowing them.

I also don’t think it’s actually important to learn godel numbering specifically. If you understand how sentences can be encoded as ASCII which can be encoded as numbers, then you already understand the important part. Nonetheless, I will still refer to numeric encoding of a sentence as its “godel number”, because that is the standard word for it.

A truth predicate for PA would be any sentence T(x) in PA with one free variable x which, when x is substituted for the godel number of some other sentence S, is true if and only if S is true. In other words, for any sentence S, if n is its godel number, then (T(n) <-> S).

The paradoxes of self-reference come from combining self-reference, negation, and truth predicates. Tarski’s proof of the undefinability of truth makes essential use of all three. But any two of these on their own are fine: self-reference with negation are combined just fine in PA, and self-reference with truth predicates (but without negation) can also be combined just fine in PA, using sigma_n or pi_n formulas in the arithmetical hierarchy (where n>0).

Going back to Curry’s paradox, let’s assume we have a truth predicate T. Then curry’s sentence is the sentence S = (T(p) → Santa), where p is a quine which outputs the godel number of S. Note that (T(p) → Santa) is the same as (~T(p) OR Santa), so we can see that Curry’s paradox combines self-reference, negation, and a truth predicate.

MathMart’s Shortform

MathMart3 Sep 2026 4:34 UTC

2 points

1 comment1 min readLW link

MathMart 3 Sep 2026 4:34 UTC
1 point
0
on: MathMart’s Shortform
The truthteller sentence is the sentence “this sentence is true”. The sigma_n and pi_n truthteller sentences are expressible in set theory (and PA) for n>0. For sigma_1, pi_2, sigma_3, and so on, the truthteller sentence is false. On the other hand, for pi_1, sigma_2, pi_3, and so on, the truthteller sentence is true.

What determines the truth is the last quantifier. If the last quantifier is an existential, then the truthteller sentence is false, otherwise it is true. Here is a quick sketch of the proof we came up with tonight, though I don’t really expect it to be intelligible to anyone else.

The form of the delta_0 part of the truthteller sentence depends on the last quantifier, because the delta_0 truth predicate is delta_1 and must be put in the form that starts with the same quantifier.

The first case is when the last quantifier is an existential. Rewrite it in form “there exists (w, a_0, …, a_m)”, where w is the witness given as parameter to the delta_0 truth predicate, and a_0 to a_m are the auxiliary sets needed by the delta_0 truth predicate and other machinery (such as the machinery that gets the godel number of the truthteller sentence).

Since the w is smaller than the tuple (w, a_0, …, a_m), the recursion eventually bottoms out when the delta_0 part of the formula is given invalid auxiliary sets. In that situation the formula is false, because the delta_0 part of the formula is in the form “the auxiliary sets have the correct shape AND something”.

In the second case, with foralls at the end, it’s similar, except that bottoming out at incorrect auxiliary sets results in truth, because the delta_0 part of the formula is in the form “the auxiliary sets are correct IMPLIES something”.

Note that this proof depends on the axiom of regularity, and might not hold if there are sets which aren’t well-founded.

MathMart 2 Sep 2026 5:46 UTC
1 point
0
in reply to: MathMart’s comment on: Insights into Curry’s Paradox?
To explain what I mean with respect to Yablo’s paradox. Take a sentence defined so that (P <-> ~P). This is clearly a self-referential sentence. Suppose I instead defined a sentence (P <-> ~P’), where P’ is just P with a bunch of double negations randomly inserted into it. P doesn’t directly appear anywhere on the right-hand side in this case, but P is still contradictory, and it seems fair to say it is still self-referential.

In Yablo’s paradox, the only notable differences between each sentence in the sequence are the starting indices they use. However, the choice of indices in each sentence has no effect on its truth, and if we renumber all the sequences to start at 0, we are left with an equivalent set of sentences to the original. But renumbering them this way makes the self-reference very clear, because now each sentence in the sequence is identical!

Edited to add more, because I’m thinking too much about this:

I should maybe explicitly spell out the following argument. Whatever definition of self-reference we choose, it cannot rely on the sentence referring directly to its unmodified self, because that would rule out most practical cases of self-reference. For example, if n is the godel number of P, and (P <-> ~Provable_in_PA(n)), then P is the standard self-referential sentence from the incompleteness theorem, but it does not directly refer to itself (only indirectly using an encoding). Even if we accepted the encoded version as “the same” as the original, the proof of incompleteness would still work if n was modified to be the godel number of any other sentence P’, so long as P’ was provably (in PA) logically equivalent to P.

Given that, it seems to me that if we can show that the truth of a sentence depends on the falsity of another logically equivalent sentence, that should count as a self-referential paradox.

Finally, here is a perhaps a more rigorous approach to show the self-reference in Yablo’s paradox, since it’s not immediately clear that the renumbering to zero in my original argument is valid. Let S be Yablo’s sequence starting at 1, and Z be Yablo’s sequence starting at 2. There is a clear bijection between both of these sequences, simply by mapping S1 to Z1, S2 to Z2, etc. And by examining the logical structure of Yablo’s sequence, we can see that the choice of initial index has no effect on the truth of the first sentence in the sequence, so (S1 <-> Z1). But since Z1 is the same sentence as S2, we have (S1 <-> S2). We can apply this procedure to get that (S1 <-> Sn) for all n. Since (S1 <-> forall i>1 ~Si), we get (S1 <-> ~S1), which is a self-referential contradiction.

MathMart 2 Sep 2026 2:04 UTC
1 point
0
in reply to: cousin_it’s comment on: Insights into Curry’s Paradox?
I will second that it’s best to learn the actual underlying mathematics.

However, self-referential truth predicates can also be legitimate: the sigma_n/pi_n truth predicates are respectively sigma_n/pi_n definable, for example, and can refer to themselves. The sigma_n/pi_n truth predicates seem to avoid paradox by being unable to refer to their own negations.

I also want to say that I think what Yablo’s paradox shows is that it’s possible to “hide” the self-reference by having the sentence refer not directly to itself, but instead to a logically equivalent sentence which is encoded slightly differently.

Edited to add:

I think the general form of Tarski’s undefinability of truth gives a pretty good list of conditions. It seems to be the combination of self-reference, negation, and truth predicate which gives paradox. But any two on their own are fine.

MathMart 20 Jun 2026 14:37 UTC
2 points
0
in reply to: kbear’s comment on: Computational models of first-order theories
The choice to use E was deliberate, in order to keep a distinction between the relation being built and actual set elementhood. I don’t know if it was the right choice, but that was the reasoning.

Computational models of first-order theories

MathMart16 Jun 2026 23:02 UTC

5 points

2 comments11 min readLW link

MathMart 4 Oct 2025 17:13 UTC
1 point
0
in reply to: Aatu Koskensilta’s comment on: Why’s equality in logic less flexible than in category theory?
That’s also true in first-order logic with equality, since nothing except convention stops us from considering models where multiple objects are equal according to the equality predicate. The choice to exclude models which include duplicate objects is just a side-condition used to filter out inconvenient models when studying semantics. We can include such a side-condition when considering the semantics of set theory without equality, too, so it doesn’t seem fair to me to single it out as being uniquely incapable of defining equality.

(In fact, I’d argue that this also applies to second-order logic. Second-order logic can be given Henkin semantics, which have all the same idiosyncracies as first-order semantics. Using these semantics, we can get models of second-order logic with duplicate objects, just like first-order logic. I’d argue that standard second-order semantics are more or less just using a side-condition to filter out models which have missing subsets. But if we wanted to we could include similar side-conditions when considering models of first-order set theory, too, so it doesn’t seem fair to me to to say second-order logic can define equality while first-order logic can’t.)

MathMart 2 Oct 2025 21:28 UTC
1 point
0
on: Why’s equality in logic less flexible than in category theory?
Since multiple answers here mention equality being undefinable in first-order logic, I want to say that that’s only true if there are an infinite number of constants/functions/predicates in the language. Since set theory can be formalized using only a single predicate, it is possible to define equality this way:

$x = y \equiv \forall z ((x \in z \leftrightarrow y \in z) \land (z \in x \leftrightarrow z \in y))$

(Where x and y can be the same variable, but z must be a different variable from them both)

By simply replacing every instance of the formula “x=y” with this definition, set theory can be formalized in first-order logic without equality.

MathMart 13 Dec 2023 0:53 UTC
1 point
0
in reply to: Logan Zoellner’s comment on: A Philosophical Tautology

So what part of a mathematical universe do you find distasteful?

the idea that “2” exists as an abstract idea apart from any physical model

It’s this one.

Okay, but if actual infinities are allowed, then what defines small in the “made up of small parts”? Like, would tiny ghosts be okay because they’re “small”?

Given that you’re asking this question, I still haven’t been clear enough. I’ll try to explain it one last time. This time I’ll talk about Conway’s Game of Life and AI. The argument will carry over straightforwardly to physics and humans. (I know that Conway’s Game of life is made up of discrete cells, but I won’t be using that fact in the following argument.)

Suppose there is a Game of Life board which has an initial state which will simulate an AI. Hopefully it is inarguable that the AI’s behavior is entirely determined by the cell states and GoL rules.

Now suppose that as the game board evolves, the AI discovers Peano Arithmetic, derives “2 + 2 = 4”, and observes that this corresponds to what happens when it puts 2 apples in a bag that already contains 2 apples (there are apple-like things in the AI’s simulation). The fact that the AI derives “2 + 2 = 4″, and the fact that it observes a correspondence between this and the apples, has to be entirely determined by the rules of the Game of Life and the initial state.

In case this seems too simple and obvious so far and you’re wondering if you’re missing something, you’re probably not missing anything, this is meant to be simple and obvious.

If the AI notices how deep and intricate math is, how its many branches seem to be greatly interconnected with each other, and postulates that math is unreasonably effective. This also has to be caused entirely by the initial state and rules of the Game of Life. And if the Game of Life board is made up of sets embedded inside some model of set theory, or if it’s not embedded in anything and is just the only thing in all of existence, in either case nothing changes about the AI’s observations or actions and nothing ought to change about its predictions!

And if the existence or non-existence of something changes nothing about what it will observe, then using its existence to “explain” any of its observations is a contradiction in terms. This means that even its observation of the unreasonable effectiveness of math cannot be explained by the existence of a mathematical universe outside of the Game of Life board.

Connecting this back to what I was saying before, the “small parts” here are the cells of the Game of Life. You’ll note that it doesn’t matter if we replace the Game of Life by some other similar game where the board is a continuum. It also doesn’t even matter if the act of translating statements about the AI into statements about the board is uncomputable. All that matters is that the AI’s behavior is entirely determined by the “small parts”.

You might have noticed a loophole in this argument, in that even though the existence of math cannot change anything past the initial board state, if the board was embedded inside a model of set theory, then it would be that model which determined the initial state and rules. However, since the existence of math is compatible with every consistent set of rules and literally every initial board state, knowing this would also give no predictive power to the AI.

At best the AI could try to argue that being embedded inside a mathematical universe explains why the Game of Life rules are consistent. But then it would still be a mystery why the mathematical universe itself follows consistent rules, so in the end the AI would be left with just as many questions as it started with.

MathMart 12 Dec 2023 11:24 UTC
1 point
0
in reply to: Logan Zoellner’s comment on: A Philosophical Tautology
My view is compatible with the existence of actual infinities within the physical universe. One potential source of infinity is, as you say, the possibility of infinite subdivision of spacetime. Another is the possibility that spacetime is unboundedly large. I don’t have strong opinions one way or another on if these possibilities are true or not.

MathMart 11 Dec 2023 5:16 UTC
1 point
0
in reply to: Logan Zoellner’s comment on: A Philosophical Tautology
The assumption is that everything is made up of small physical parts. I do not assume or believe that it’s easy to predict the large physical systems from those small physical parts. But I do assume that the behavior of the large physical systems is determined solely from their smaller parts.

The tautology is that any explanation about large-scale behavior that invokes the existence of things other than the small physical parts must be wrong, because those other things cannot have any effect on what happens. Note that this does not mean that we need to describe everything in terms of quantum physics. But it does mean that a proper explanation must only invoke abstractions that we in principle would be able to break down into statements about physics, if we had arbitrary time and memory to work out the reduction. (Now I’ve used the word reduction again, because I can’t think of a better word, but hopefully what I mean is clear.)

This rules out many common beliefs, including the platonic existence of math separately from physics, since the platonic existence of math cannot have any effect on why math works in the physical world. It does not rule out using math, since every known instance of math, being encoded in human brains / computers, must in principle be convertible into a statement about the physical world.

MathMart 10 Dec 2023 16:15 UTC
1 point
0
in reply to: Vladimir_Nesov’s comment on: A Philosophical Tautology
I completely agree that reasoning about worlds that do not exist reaches meaningful conclusions, though my view classifies that as a physical fact (since we produce a description of that nonexistent world inside our brains, and this description is itself physical).

it becomes apparent that if our physical world wasn’t real in a similar sense, literally nothing about anything would change as a result.

It seems to me like if every possible world is equally not real, then expecting a pink elephant to appear next to me after I submit this post seems just as justified as any other expectation, because there are possible worlds where it happens, and ones where it doesn’t. But I have high confidence that no pink elephant will appear, and this is not because I care more about worlds where pink elephants don’t appear, but because nothing like that has ever happened before, so my priors that it will happen are low.

For this reason I don’t think I agree that nothing would change if the physical world wasn’t real in a similar sense as hypothetical ones.

MathMart 10 Dec 2023 15:58 UTC
1 point
0
in reply to: Logan Zoellner’s comment on: A Philosophical Tautology
I will refer to this other comment of mine to explain this miscommunication.

MathMart 10 Dec 2023 14:27 UTC
1 point
0
in reply to: Vladimir_Nesov’s comment on: A Philosophical Tautology

Reasoning being real and the thing it reasons about being real are different things.

I do agree with this, but I am very confused about what your position is. In your sibling comment you said this:

Possibly the fact that I perceive the argument about reality of physics as both irrelevant and incorrect (the latter being a point I didn’t bring up) caused this mistake in misperceiving something relevant to it as not relevant to anything.

The existence of physics is a premise in my reasoning, which I justify (but cannot prove) by using the observation that humanity has used this knowledge to accomplish incredible things. But you seem to base your reasoning on very different starting premises, and I don’t understand what they are, so it’s hard to get at the heart of the disagreement.

Edit: I understand that using observation of the physical world to justify that it exists is a bit circular. However, I think that premises based on things that everyone has to at least act like they believe is the weakest possible sort of premise one can have. I assume you also must at least act like the physical world is real, otherwise you would not be alive to talk to me.

MathMart 10 Dec 2023 13:47 UTC
1 point
0
in reply to: Vladimir_Nesov’s comment on: A Philosophical Tautology
Okay, let’s forget the stuff about the “I”, you’re right that it’s not relevant here.

For existence in the sense that physics exists, I don’t see how it’s relevant for reasoning, but I do see how it’s relevant to decision making

Okay, I think my view actually has some interesting things to say about this. Since reasoning takes place in a physical brain, reasoning about things that don’t exist can be seen as a form of physical experiment, where your brain builds a description which has properties which we assume the thing that doesn’t exist would have if it existed. I will reuse my example from my previous post to explain what I mean by this:

To be more clear about what I mean by mathematical descriptions “sharing properties” with the thing it describes, we can take as example the real numbers again. The real numbers have a property called the least upper bound property, which says that every nonempty collection of real numbers which is bounded above has a least upper bound. In mathematics, if I assume that a variable x is assigned to a nonempty set of real numbers which is bounded above, I can assume a variable y which points to its least upper bound. That I can do this is a very useful property that my description of the reals shares with the real numbers, but not with the rational numbers or the computable real numbers.

So my view would say that reasoning is not fundamentally different from running experiments. Experiments seem to me to be in a gray area with respect to this reasoning/decision-making dichotomy, since you have to make decisions to perform experiments.

MathMart 10 Dec 2023 13:06 UTC
1 point
0
in reply to: Logan Zoellner’s comment on: A Philosophical Tautology
I don’t say in this post that everything can be deduced from bottom up reasoning.

MathMart 10 Dec 2023 0:13 UTC
1 point
0
in reply to: Vladimir_Nesov’s comment on: A Philosophical Tautology
The fact that I live in a physical world is just a fact that I’ve observed, it’s not a part of my values. If I lived in a different world where the evidence pointed in a different direction, I would reason about the different direction instead. And regardless of my values, if I stopped reasoning about the physical world, I would die, and this seems to me to be an important difference between the physical world and other worlds I could be thinking about.

Of course this is predicated on the concept of “I” being meaningful. But I think that this is better supported by my observations than the idea that every possible world exists and the idea that probability just represents a statement about my values.

MathMart 9 Dec 2023 20:25 UTC
1 point
0
in reply to: TAG’s comment on: A Philosophical Tautology

clearly physical brains can think about non physical things.

Yes, but this is not evidence for the existence of those things.

But it’s not conclusive in every case, because the simplest adequate explanation need not be a physical explanation.

There is one notion of simplicity where it is conclusive in every case: every explanation has to include physics, and then we can just cut out the extra stuff from the explanation to get one that postulates strictly less things and has equally good predictions.

But you’re right, there are other notions of simple for which this might not hold. For example if we define simple as “shortest description of the world which contains all our observations”. Though I think this definition has its own issues, since it probably depends on the choice of language.

Still, this is the most interesting point that has been brought up so far, thank you.

Edit: I was too quick with this reply and am actually wrong that my notion of simplicity is conclusive in every case. I still think this applies in every case that we know of, however.

Edit 2: I think the only case where it is not conclusive is the case where we have some explanation of the initial conditions of the universe which we find has predictive power but which requires postulating more things.

MathMart 9 Dec 2023 20:03 UTC
1 point
0
in reply to: TAG’s comment on: A Philosophical Tautology

Whatever “built on top of” means.

In ZFC, the Axiom of Infinity can be written entirely in terms of ∈, ∧, ¬, and ∀. Since all of math can be encoded in ZFC (plus large cardinal axioms as necessary), all our knowledge about infinity can be described with ∀ as our only source of infinity.

Only for the subset of maths that’s also physical. You can’t resolve the Axiom of Choice problem that way.

You can’t resolve the Axiom of Choice problem in any way. Both it and its negation are consistent.

MathMart

MathMart’s Shortform

Com­pu­ta­tional mod­els of first-or­der theories

Computational models of first-order theories