When a Proof Comes Before the Idea -- How different minds navigate the landscape of mathematical understanding.

 Below are some of my reflections on the nature of proof in the age of proof abundance (due to LLMs). Those ruminations have been cleaned up, compiled, and stitched together with the aid of an LLM.

Imagine two mathematicians trying to prove the same theorem. The first works through 150 steps. None is mysterious; each follows correctly from what came before. Yet the argument, taken as a whole, is difficult to hold in mind. The second mathematician spots something else: the theorem is a special case of a much more general result. With that observation, the proof takes three lines.

Which proof is more insightful?

The tempting answer is the second. We admire proofs that replace calculation with insight, a thicket of details with a single clear idea. But this judgment may tell us as much about the minds doing the judging as about mathematics itself.

A mathematical proof must meet standards of validity. A mathematical explanation must also meet a reader. And different readers—and perhaps different kinds of intelligence—have very different capacities for finding, following, and organizing chains of reasoning.

To see why this matters, imagine an abstract space of mathematical facts. Across this space lie various enclosed regions, each associated with a particular mathematical idea. Some are large, others small. Some overlap considerably, while others appear isolated. Their shapes need not be regular. One region might represent mathematical induction, another the concept of an invariant, another a powerful theorem connecting two previously separate fields.

We can think of these regions as closed sets, representing the scope of mathematical consequences made readily accessible by particular ideas.

These are not simply sets of everything that follows logically from an idea. They are regions of *mathematical intelligibility*: results that a trained mathematician can recognize as natural consequences, without having to rebuild the argument from scratch. Near the conceptual centre of a region, the implications seem obvious. Toward its boundaries, they require ingenuity. And those boundaries are not entirely sharp, because familiarity, ingenuity, and background knowledge vary from person to person.

The same theorem might lie near the outer limit of one region and comfortably within another. What looks like a distant and difficult destination from one mathematical vantage point can be almost underfoot from another.

Now imagine the two mathematicians again. The second notices that the theorem belongs to the region illuminated by an established principle. Her achievement is not merely reaching the theorem; it is recognizing where the theorem belongs. She finds a place for it within a broader mathematical structure.

The first mathematician begins elsewhere. He crosses the spaces between familiar conceptual regions, moving from one justified inference to the next. He has found a path, but not necessarily a panoramic view of the terrain. His proof may be formidable, meticulous, and entirely correct without being easy to describe as one overarching idea.

These are two different forms of mathematical understanding. One reveals a theorem's place within a broader conceptual structure. The other establishes a route to it, perhaps from an altogether different mathematical starting point. Neither accomplishment necessarily entails the other.

This distinction offers an interesting perspective on the emerging role of artificial intelligence in mathematics.

Humans have limited working memory. We have learned to cope, in part, by turning complicated procedures into concepts we can carry around as single units: "use induction", "find an invariant", "pass to a quotient". What once demanded a page of reasoning can become one move on the mental chessboard.

AI systems can sometimes approach a problem differently. A language model working with search, external memory, or a proof assistant may explore and check long inferential routes that would be exhausting for a person to discover or survey. That does not make an LLM infallible, and a fluent sequence of claims is not automatically a valid proof. The point is subtler: systems with different cognitive and computational resources may find different routes through the same mathematical territory.

Nor does it follow that AI produces only sprawling arguments, or that humans produce only elegant insights. AI can suggest useful constructions and unexpected connections; mathematicians can labour through hundreds of technical steps. The contrast concerns possible cognitive advantages, not an absolute division between different kinds of intelligence.

Consider a historical thought experiment. Today, an AI system finds a valid but ungainly proof of a difficult theorem, using mathematical ideas that already exist. Twenty years later, an entirely new field has developed. Someone realizes that the old theorem is now an almost immediate consequence of two general principles.

The theorem has not changed. Its truth has not become truer. What has changed is the landscape: new regions of mathematical intelligibility have emerged, making accessible what previously required an arduous deductive journey.

This is why mathematical elegance has a historical dimension. A proof that is transparent to an expert in a mature field may be opaque to a student, and literally unimaginable to a mathematician working before that field existed. We might call this a relativity of *conceptual distance*, without confusing it with a relativity of mathematical truth.

Still, the shorter proof is not automatically the better one. Mathematicians often prize *elementary proofs*: arguments that avoid advanced theoretical machinery, even at the price of considerable length or ingenuity.

Fermat's Last Theorem, for example, was finally proved through deep connections involving elliptic curves and modular forms. No elementary proof is known. Yet one can imagine a different argument proceeding from comparatively elementary number theory, perhaps through hundreds of ingenious deductions. Such a proof could reveal something important that the established proof does not, even if it were considerably longer.

There is another possibility, however, and it changes our mathematical landscape yet again.

Suppose the original 150-step argument begins to recur. Other mathematicians notice that its moves can be adapted to new problems. They name the method, streamline its presentation, and teach it. What once looked like a cumbersome expedition becomes a standard route.

In modal logic, canonical-model constructions illustrate something like this transformation. Students first encounter a formidable apparatus: collections of formulas used to construct "possible worlds", carefully defined relations between those worlds, and an argument connecting the syntactic properties of formulas with truth in the resulting model.

Later, the same student may hear "use the canonical model" and recognize an entire strategy at once. A complicated construction has become a familiar tool. Its internal complexity has not disappeared, but the experienced logician can now handle it as a single recognizable method.

In our conceptual landscape, we could represent this development by introducing a new enclosed region. Unlike a general theorem that places a result neatly within an existing theory, this region may encompass the *deductive route itself*. A lengthy procedure has become familiar enough to function as a mathematical idea in its own right. Its territory may overlap with several older regions, creating connections that were previously difficult to recognize.

Not every long proof undergoes that transformation. Some arguments remain isolated, useful chiefly because they establish the result they set out to prove. Others become standard tools through their versatility, their explanatory power, or their repeated adoption by the mathematical community.

Mathematical ideas, then, do not become familiar in only one way. Some offer immediate conceptual clarity. Others acquire their place in the mathematical toolkit through repeated application and gradual refinement. Familiarity can arise from understanding a general principle, but also from mastering a procedure.

And the regions of our mathematical landscape are not fixed. Their boundaries may shift with education, experience, and the historical development of mathematics. What lies near the limits of one person's mathematical intuition may lie at the very heart of another's.

The prospect of AI-assisted mathematics makes these distinctions more than philosophical curiosities.

We may increasingly encounter theorems for which a rigorous proof is available, but no particularly satisfying conceptual explanation has yet emerged. The work of mathematics would not end there. Researchers could still ask which steps matter most, what general principles lie hidden in the details, and whether the argument opens an entirely new region of mathematical thought.

Indeed, a complicated AI-generated proof might eventually become the basis for a new mathematical idea. Or a future mathematician might discover a completely different proof, rendering the original argument unnecessary for understanding the result. Neither outcome diminishes the original achievement.

The important distinction is between establishing a mathematical truth and finding a conceptual organization that makes it intelligible. These achievements often go hand in hand, but they need not.

And perhaps that is what the arrival of new kinds of mathematical intelligence will help us appreciate.

A proof tells us that a destination can be reached. An idea can show us why the destination belongs within a familiar region of mathematical understanding—or teach us a route worth travelling again.

Mathematics needs both.

Its truths may stay put, but the landscape of what different minds can readily see is always changing.

I've identified an interesting semi-group in Australian slang ;)

(G, * )

G  = {yeah, nah}

Closure
yeah nah = nah
nah yeah = yeah
nah nah = nah
yeah yeah = yeah

Associativity
(yeah nah) yeah = yeah
yeah (nah yeah) = yeah

(yeah yeah) nah = nah
yeah (yeah nah) = nah

(nah yeah) nah = nah
nah (yeah nah) = nah

(nah nah) yeah = yeah
nah (nah yeah) = yeah

The above structure can be extended to a monoid, if we add the empty word as the identity element.

Asortyment Nieskończoności

Jest to prezentacja Powerpoint, prelekcji której udzieliłem w Otwartej Kolonii (filii Wolskiego Centrum Kultury) 20 kwietnia. Ten wykład to krótka historia pojęcia niskończoności, oraz wstęp do arytmetyki liczb kardynalnych poprzez prezentację dowodów Cantora na równoliczność zbiorów nieskończonych. Poniższa prezentacja zawiera trochę definicji oraz pomocy ilustracyjnych, ale oczywiście brakuje jej niezbędnej narracji która wyjaśnia wszystkie pojęcia oraz ich relacje.

Asortyment Nieskończoności PDF by Mariusz Popieluch on Scribd

There are uncountably many binary sequences whose limiting relative frequency is x.

This is a proof of an elementary result in probability theory that I gave, prompted by a colleague's inquiry, and motivated by the fact that the question had initially stumped a University of Queensland professor of the relevant field of mathematics.

There are uncountably many binary sequences whose limiting relative frequency is x. by Mariusz Popieluch on Scribd

Link to PDF of proof.

Explicit solution (formula) to the "truth table" recurrence relation.

If anyone has done any introductory logic, or has been introduced to representing sets in terms of their characteristic function, then the following binary matrix will look familiar. Each row is a distinct combination of the elements of some set. This is the matrix for a three element set. Call it matrix A.

1 1 1 ...
0 1 1
1 0 1
0 0 1
1 1 0
0 1 0
1 0 0
0 0 0
:
:

Some of the most common applications/interpretations of this matrix are:

i) For any natural number N (of columns), the rows of the matrix (of which there is 2^N) represent the set of all functions N→{0,1}., were N is a finite subset of the Natural numbers.

ii) The rows of a table thus generated, exhaust all truth value assignments to a propositional variable appearing in a formula of Propositional Calculus.

iii) Equivalently each row can be interpreted as the image of the characteristic function of a power set of some set S (we don't need to assume the axiom of countable choice since here we're dealing with finite sets). In other words each row of the matrix corresponds to a distinct combination of the elements of S. In fact the map f : ℘(S)→ ROWS (of the matrix) is a bijection: f(X)=r iff r(i)=1 iff i∈X, where we identify the matrix column indecies with the wellordering of the elements of S.

So clearly this matrix is a big deal, and subsequently the result here is an important one, since it basically compresses the entire matrix to a simple function of its rows and columns.

The way to generate the matrix in a way to ensure that all combinations are exhausted, is to follow the obvious pattern for column generation --- single iteration, double iteration, quadruple iteration, etc. In general, each column i has a 2^i-1  iteration of 1's and 0's (starting with 1's in each column).

Below is the proof for the explicit formula of such matrices recurrence relations, i.e. as a function of the matrix'  row and column number. That is, given only the row and column numbers, the formula gives the value that appears in the matrix on those 'coordinates'. That is, the formula takes the following functional form:

                                                                       θ : 2ⁿ×n → {0,1}

EXAMPLE: θ(k,i), where the row number is k = 7 and column number is i = 2, i.e. θ(7,2) = 0.

Now for the proof, which I have only given a sketch of in a previous post. Subsequently I lost the proof, and only had the formula, which bothered me, so I re-proved it last week. So here we go. Most of the pattern recognition which underlies the solution is obviously to be found in the matrix itself, and the diagram below intends to capture and make salient those patterns which may not be so obvious at first glance. The integer numbered columns, i.e. columns 1, 2, 3, 4,..., are the actual columns of the matrix A. 

To the right of each actual matrix column i, I list k(mod 2ⁱ), which is the first pattern that ought to be observed. Can you see how a single cycle of k(mod 2ⁱ) matches the length of the pair of iterated 1's and 0's, in column i? The next key observation, and perhaps the crucial one, is that the pattern of out actual matrix columns is basically a function of k(mod 2ⁱ). More precisely, note how each i'th actual column has the same pattern as k(mod 2ⁱ)−k(mod 2^i-1), with the exception of being slightly 'misaligned' and having some product of 2 in the place there 1's ought to be. I have indicated the k(mod 2ⁱ)−k(mod 2^i-1) rows with a yellow heading. Have a look for a while, and the pattern* should 'jump out'. Once you're convinced that it is so, all we need to do is (i) to rectify the 'misalignment', and (ii) the multiples of 2 integers instead of 1's. By noting that the 'misalignment' is also a function of column number, we see that adding 2^i-1−1 to k, does the trick. Finally divide all values in each i'th column by 2^i-1 and we're basically done. That is, our formula can be expressed as the function:

This formula is good enough and does the trick, but using the identity below, relating the mod and floor functions, it can make it more concise.

Giving the formula its final form. I guess it could be rendered even more concise and elegant with further algebraic fiddling, but I shall leave it there.

*Admittedly, a more rigorous proof is required than merely conjecturing that this pattern ought to hold in general. I may get around to it soon. But it does seem obvious that the proof is correct, since no surprises will arise in the relationship of the values of k(mod 2ⁱ) and k(mod 2^i-1) as both k and i increase.

If we switch the order of 1's and 0's in the table, i.e. if we let 0's precede 1's, like so (call this matrix B):

000...
100
010
110
001
101
011
111
:
:
Then the same reasoning yields a more elegant formula:

On the (nontrivial) non-uniqueness of the empty collection.

Consider a property P : "is green all over, and is not green all over".

Alice and Bob are friends. Bob reasons about the world, and accordingly conditions his understanding of what is or isn't logically possible to classical logic. In particular, not only there are no objects with property P, but there cannot be any such objects since P is a logically impossible property. Alice on the other hand, having travelled far and wide, and having seen curiosities such that no classically (as per classical logic) minded philosopher has even dreamed of, accepts paraconsistent logic as the correct way to reason about the world and its many wonders.

Alice and Bob agree that 'empty' (or 'the empty collection', denoted (e)) is an absence of any-thing, i.e. it is an absence of any object (or simply 'a set with no elements'). They also adopt a covention whereby saying that 'some-thing is contained by the empty collection' means the same as saying that 'that some-thing does not exist', e.g. 'four sided triangles are contained by the empty collection' is just another way of saying that 'four sided triangles don't exist'. This is the convention both Alice and Bob adopt, and agree on. Nota bene, impossibilia (impossible objects) are also contained by the empty collection, for since they can't exist, in particular they don't actually exist.

The duo however disagree about what counts as an object. Whereas Bob considers any object with property P as impossible, i.e. an object that cannot possibly exist, Alice doesn't. As a consequence, within their discussion about the world and its many wonders, the term 'empty collection' despite being correctly understood by both friends as having the same extension, is incorrectly assumed to have the same intension. The extension is the same since it is an absence of any object, but its intension is distinct, due to our protagonists' differences in reasoning about the world, which in turn bear on what counts as possible and what doesn't.

In particular, for Bob the empty collection has the property of containing all "objects" with property P, since that amounts to saying that such objects don't exist (since they can't exist!). Alice would disagree with Bob with regards to such a property --- she would negate it having such a property outright, by saying that it's not the case that the empty collection contains all objects with property P, since (after all) the existence of such objects is consistent with her view of the world. So if she were to accept that the empty collection had such a property, it would amount to saying that the empty collection is not empty after all. Instead, Alice asserts the negation, i.e. that there are some objects with property P that are not contained by the empty collection.

What does this mean? That Alice and Bob aren't talking about a unique empty collection, but rather two distinct ones. To eliminate confusion they decide to introduce yet another convention whereby they index those distinct empty collections by what makes them distinct --- in this case the distinction is conditioned on who is considering the empty collection, i.e. (e)-A, and (e)-B. But since the differences in the intension of those two terms are in virtue of the reasoning system (logic) adopted by either friend, we can conclude that the intension of "empty collection" is logic relative.

Unlike the act of conditioning the meaning of 'the empty collection' to contexts which deliver contingent distinctions, e.g. what a caveman, a poet, a chemist or a physicist would consider as 'empty', the difference in the meaning of "the empty collection" in the case of Alice and Bob arises out of how such concepts can be reasoned about in principle. As such it is a distinction in the meaning of 'the empty collection' in principle, i.e. in principle that concept has no unique meaning.

Also this is a nontrivial claim, since it's possible (conceivable) that Alice and Bob never met, and so never discovered the discrepancy in the meaning of 'the empty collection'. In other words, it's a nontrivial result since it's conceivable that there could be rational agents confined to a single reasoning system only, thereby not being capable (lacking the necessary epistemic condition, which is the act of abstracting away from the preferred reasoning system) of seeing the fundamental non-uniqueness of the notion of 'the empty collection'.

To sum up: Alice's notion of 'the empty collection' is not the same as Bob's notion of it is. Concisely speaking (e)-A is not identical to (e)-B, which yields the truth of the claim '(e)-LP is not identical to (e)-classical'.

But let's assume per impossible that (e)-LP is identical to (e)-classical; hence x is in (e)-LP iff x is in (e)-classical. Also pick the object a (such that Pa) as an LP-possible object (a is an LP possibilia). This is a fair assumption since not all contradictory properties need be impossible in LP, thus allowing objects with such properties to be legitimate possibilia. Hence a is not in (e)-LP, according to the convention adopted by Alice and Bob. But according to the same convention, all x such that Px are elements of (e)-classical, i.e. all x such that Px are classically impossible (are classical impossibilia). In particular a is in (e)-classical, but that means that a is in (e)-LP given the hypothesis (identity assumption), but we assumed that a is not in (e)-LP, which yields a contradiction.

Therefore, adopting classical logic as the one governing this proof (the metalogic here), and reductio ad absurdum as a valid proof method, it follows that (e)-LP is not identical to (e)-classical, as required.

The key idea of the above discussion can be compressed to saying that although the extension of classically impossible objects can be expressed as the extension of the set (CI) of objects that satisfy some inconsistent property, since those two are necessarily coextensive in classical logic, but the extension of paraconsistently impossible objects cannot be expressed as the extension of CI. Hence, the intension of 'no possible objects' is logic relative (obviously?).

Note: 'element of' and 'belongs to' and 'is in' are terms expressing binary relations that I tentatively use to denote some kind of association of an impossibilia with the empty collection, or the empty set (or empty sets, since I'm arguing that they're needn't be unique across distinct theories). Note also that for each single theory the empty set still remains a unique object/element, as theories are usually based on a single logic. (This assumpton needn't be correct.)

One may rightfully object, and some have, that there's a fundamental problem with asserting that anything is an element of the empty collection. But suppose I claimed that the objects it 'contains' are non-existent, but by doing so were I to wish to retain the meaningfulness of such 'objects' I would be committing to some kind of non-eistic ontology, which posits non-existent objects. But those non-existent objects are objects of some kind after all, and thus cannot be said to be elements of the empty collection, which contains no objects whatsoever. So suppose I reject non-eism, and say that when I say 'a is an element of the empty collection', in no way do I wish to commit to a's existence --- not even as a non-existent object --- i.e. there is no a. But then what is it that I am talking about when I refer to a? I'm not refering to anything apparently, by definition.

I choose the second route, i.e. the one that doesn't commit to an non-eistic ontology. 

(To be continued.)

How empty is { }? Different orders of the Empty Set. Coursera Forum discussion.

Here is a raw cut-and-paste of the exchange on this topic from a Coursera forum.

I'd like to thank those who provided constructive criticism, or just picked at the idea with an unbiased razor of skepticism. Apparently most of the interlocutors were inspired, and some have even admitted to having been led to think in a new way --- to a philosopher, there's no greater reward :)

It's this sort of exchange that allows the idea to mature, and hopefully catch on :)
------------------------------
------------------------------

Mariusz Popieluch· 2 months ago
Let me introduce the discussion with a little humor.

The Poet, the Chemist, and the Physicist.
The trio met one day over some wine and discussed matters of rhyme, thyme and time. Soon the conversation turned to the notions of nothingness and emptiness - what is empty? The poet finished his glass, and pointed to it -- as far as I am concerned this glass is empty, as it is devoid of wine - the sparkling grape, the drink of gods. Hold on a minute! -- exclaimed the chemist -- surely it's not empty as it contains air - we'd have to pump all the air out of the glass, creating a vacuum in it, and then and only then would it be empty. It wouldn't make any difference to me -- replied the poet, shrugging his shoulders. Please let me interject at this juncture dear fellows -- interjected the physicist -- and let me put an end to your obvious confusion. Vacuum, as you describe it doesn't cut it at all, since we know that even empty space is a breeding ground for virtual particles whose immediate annihilation results in what we observe and call vacuum energy. The poet looked at the physicist with a frown of suspicion -- I know nothing when I see it good man, and I won't let anyone tell me otherwise - let the bartender settle this matter - haloo, good fellow! Another round please!

-------

The above humorous scenario pertains to natural language and some theories of varying degree of conceptual refinement, but the idea extends nicely (I believe) to formal languages, theories and logics too, thus generalizing the idea of emptiness. In particular it intends to do to the notion of emptiness and it's various formalizations such as the set theoretic ∅, what Cantor has done with the notion of infinity - show that there is structure within it, and varying orders of it.
I know this is a radical idea, but rest assured that the idea of varying orders of infinity wasn't initially taken lightly either - even today many still think it's preposterous. But interestingly enough, there seems to be a demand for such a hierarchy - hinted at in the literature - but I'm not aware of a formal theory of various orders of the empty set being developed.
The general claim is that what counts as empty is dependent on the strength of a logic underlying the theory in which it is defined and the expressibility (richness) of the language of the theory. That is, in some theories there are more objects that fail to be members of the empty set (e.g. to the physicist there is more to the contents of the glass than wine and air), thus rendering the empty set somehow emptier (to put it simply).
Or to put it another way - we could just define the order of the empty set by the cardinality of all the impossible objects in a given language/logic/theory. Those impossible objects are not actually members of the empty set, but rather are assigned to it in some sense - by saying that some object (this includes linguistic objects) is an element of the empty set (in a given theory), is just another way of saying that this object is impossible (in that theory).
Example.
Consider classical logic CL and some paraconsistent logic, say LP. In LP contradictions are not considered as impossible. Now define a property G: of being green all over, and not being green all over. Now, in CL any object with that property is considered as an impossible object, take the object a, so in CL we obviously have Ga ∈∅, but in LP we have Ga ∉∅. Hence the suggestion to index ∅ by logics - this may become crucial when talking of various theories in some metalanguage/meta theory.

Philosophically speaking "{ }" is an object with a fixed extension across theories (it has no elements), yet varying intension. What the above aims to show is that the varying intension can be accompanied with a varying quasi-extension, i.e. rarity as opposed to cardinality.

Mariusz Popieluch· 2 months ago

Consider two urns in a marble shop. The shopkeeper labelled them in the following way - urn 1 holds only (and can only hold) white marbles, whereas urn 2 can hold both white and black marbles.

Now consider a new assistant that has just been offered an apprenticeship in the shop of his dreams (he loves playing marbles), and is not as yet familiar with the arcana of the labeling system, i.e. he hasn't as yet been told by the shopkeeper what the restrictions on the contents of the urns are.

Now consider the statements 'urn 1 contains no white marbles' and 'urn 2 contains no white marbles' - they entail different things, depending who is exposed to that information - the shopkeeper or the assistant. In particular, to the shopkeeper it means that 'urn 1 is empty'.

On a more technical side, we can substitute the terms 'has no white marbles' and 'is empty' interchangeably salva veritate in the context of urn 1 (charity permitted, for naturally one could generate oddly sounding sentences). This cannot however be done in the context of urn 2.

David M. Kaziska· 2 months ago
In your first post the set, {wine in the glass}, is empty after the wine is consumed (neglecting any residual wine).  For the poet's own purposes it is empty but we may his or her statement that it is empty as colloquial in light of the chemist's and physicist's later statements.  I'm not seeing mathematical consequences which would require redefining the notion empty sets.  {wine in the glass} may be an empty set but {air in the glass} may be nonempty.  

In your later post, the shopkeeper reasons as follows.  (P1)  All marbles in Urn 1 are white, (P2)  There are no white marbles in Urn 1, therefore (C)  Urn 1 is empty.  The assistant has (P2) but not (P1) and cannot draw the conclusion.  Urn 1 is still empty, though, it's not a matter which is relative to the observer.

Mariusz Popieluch· 2 months ago
Thank you for your reply David. I'll do my best to address your observations, and further clarify the idea. :)

The later post intends to illustrate the idea that in some theory T based on some logic L1 some formula F may express an impossibility (which we can express as that formula being "an element" of, or assigned to, the empty set), whereas the exactly same formula in an analogue to T based on a logic L2 which is stronger than L1 may not come out as impossible, and as such cannot be expressed as "belonging"/being assigned to the empty set.

Note: "element of" and "belonging" are terms I tentatively use to denote some kind of assignment of F to the empty set (or empty sets, since I'm arguing that they're needn't be unique across analogous theories based on distinct logics). Note also that for each single theory the empty set still remains a unique object/element, as theories are usually based on a single logic.

The epistemic states of the protagonists of the marble shop illustration (informal context) correspond to the assumptions/axioms/conditions/semantics of theories based on distinct logics in the formal context.

Some logics distinguish semantically the propositions "p & ~p" and "p & q". In particular they consider the first proposition to take a fixed value for all valuations (contradictions are always false, and only false in classical logic). Some other logics do not make that distinction.

Likewise the shopkeeper distinguishes the two propositions concerning the urn contents, whereas the assistant doesn't. Try to think of the urn labelling system and the protagonists' distinct epistemic states as an analogy for the distinct meta-linguistic propoerties of analogous theories based on distinct logics, and the propositions concerning the urn content as object language entities, i.e. formulae.

But if the informal analogies muddle, rather than clarify the idea, I'll be happy to talk more formally about it. :)


Louise Craven· 2 months ago
Every set is a subset of the relevant domain of discourse. Thus if we are only talking of natural numbers, the empty set is the set containing no natural numbers. The poet was thinking of drinks when he said his glass was empty, so it truly was. The chemist and physicist tried to confuse him by exploiting the fact that he had not explicitly stated the domain of discourse, and they were also right about the nature of the empty set within their individual domains of discourse.  In the marble example, the difference between the shopkeeper and the assistant is not in the 'size' of the empty set, but in the inferences they can draw from the fact of emptiness, which depends on other information.

I am, however, intrigued by your suggestion and it may be that in some applications of mathematics to real-world problems, the size of the empty set in the model may need to vary according to the significance of 'nothing' in the area modelled. For instance, complete extinction of a species is of much greater significance than the remaining existence of a number of breeding pairs much smaller than the population at a previous time.

I shall go now and give it more thought....

Mariusz Popieluch· 2 months ago
Hi Louise - thank you for taking the time to read the OP.

The informal anecdotes are mere illustrations of the general idea.

In the first scenario I intended to show, via the relevant domains of discourse illustration,that given the same language (in this case natural language), but distinct theories, identical propositions (formulae, i.e. linguistic objects) entail different things - in particular, where in one theory "no wine in glass" does entail "glass is empty", in other theories it doesn't. I stress again, that this is merely an illustration of meta theoretic properties, rather than a discussion concerning restricted quantification to relevant domains of discourse per se.

Think of the Poet, the Chemist and the Physicist as analogues of theories of "The stuff on the table, at the local restaurant.", albeit based on dictinct logics. In the poet's logic "there's no wine in the glass" can be associated with the empty set - this however isn't true in the chemist's or physicist's logics. Likewise in the chemist's logic "there is no liquid and no gas in the glass" can be associated with the empty set - but again, this isn't true on the physicist's logic.

As for the second scenario, please see my above reply to David. And please do not shy away from addressing the formal content of the OP.

Andrew Kelley· 2 months ago
First let me say that I enjoyed reading this post. It made me think in a way I hadn't thought before.

I think you may be on to something with recognizing different orders of the empty set. However I am as of yet unable to think of any examples where the knowledge of such different orders is relevant to solving a problem. Are you?

Mariusz Popieluch· 2 months ago
It may serve as the ontological foundation for a theory of comparative impossibility.

Francisco Vasconcelos· 2 months ago
I think that the analogy between empty set and infinite set is not the most correct one. The evident oppositions would be between empty and complete set, and infinite and infinitesimal amounts.

So on the empty/complete side, I'm not aware that there are different orders of completeness. Both these terms are usually used as binary categories applied to other sets, both finite and infinite. Yes, their meaning varies with language context, but so do everything else, such as the number "2", the operator "+", or the word "number".

On the other hand, I think it's easier to make the claim that there are different orders of infinitesimal quantities. For example, think about the probability of picking the number "5" at random from the set of all natural numbers. Since the set is infinite, the probability is 0. However, it seems that this "0" is still bigger than the "0" probability of random sampling the number "5" from the set of all real numbers, since the pooling set is infinite to a higher degree than the previous one.

Andrew Kelley· 2 months ago
I'm not buying that you can say that one 0 is bigger than another 0. Zero is zero. Can you prove it?

Mariusz Popieluch· 2 months ago
Francisco, thank you for your reply -- you're right that it's not the most correct analogy, as it's not intended to be a directanalogy, i.e. a dual of sorts. It's a weak kind of analogy, in the sense that in both cases of infinity and nothingness/emptiness we're dealing with concept which apparently don't admit to degrees. Whereas Cantor developed the idea of bijection as the criterion for equinumerosity, I'm using it in developing the notion of the rarity of some empty set, which is currently tentatively defined to be the cardinality of the set of all formulae which express an impossibility (aka impossibilia) in a given logic L, thus yielding an indexed empty set ∅_L.

As I said before, in the above response to Louise, the contexts of relevant discourse analogy is again merely an illustrationof the more precise idea. See the above reply.

The observation you expressed in your last paragraph puts you in good company. In the context of probability theory the idea of different orders of “zero” has been hinted at by Andrey Kolmogorov and Bruno de Finetti as a possible candidate to solving some probability theory paradoxes – “Like Kolmogorov, de Finetti is occupied mostly with probabilities defined directly on arbitrary uncountable sets; but he views additivity differently, and is led to such anomalies as an unlimited sequence of layers, like an onion, or different orders of zero probabilities that add up to one, etc. ” (E.T. James: Probability Theory, the Logic of Science, 2011, p.656).

Francisco Vasconcelos· 2 months ago
Andrew, try not to read my "0" as the integer number 0, but as an infinitesimal quantity that is infinitely close to zero, something like the result of limx→∞1x. As infinity can have different sizes, the result of this limit quotient should be able to have different sizes too.

Mariusz, thanks for the info

" different orders of zero probabilities that add up to one"

this is definitely interesting and worth checking out.

Regarding your emptiness orders:

"I'm using it in developing the notion of the rarity of some empty set, which is currently tentatively defined to be the cardinality of the set of all formulae which express an impossibility (aka impossibilia) in a given logic L, thus yielding an indexed empty set ∅_L."

I get it now. So I guess you're trying to say that in different theories the empty set can be connected to a set of propositions that can have a different finite or infinite size.
Another question: hypothetically speaking, do you think that within a single theory L (maybe with number references), it is possible to represent empty sets with different sizes in this sense?

Andrew Kelley· 2 months ago
We can mathematically prove that infinity can have different sizes by using bijections. But we cannot mathematically prove that limit of 1/x as x approaches infinity is not equal to the integer zero. In fact, we *can* prove that, for example, 0.999999 repeating is exactly equal to 1. Not a number which has an infinitesimally small difference than 1. 1.

Francisco Vasconcelos· 2 months ago
Andrew I'm still trying to figure out what different kind of "0" can mean, it seems that this concept raises some issues in probability theory, but lets forget that for a moment and define the following:

For any functions f(x) and g(y), assume that
limx→∞f(x)=0
limy→∞g(y)=0

Now suppose the following hypothesis:
For any arbitrary ϵ, there is NOT a bijection between all possible values of g(y) and f(x), for x,y≥ϵ

If this proposition is true, then the limit of g(y) and f(x) being "0" might have different meanings, since we know that for any given ϵ, one of the sets will always be larger than the other.


Mariusz Popieluch· 2 months ago
@Francisco: "Another question: hypothetically speaking, do you think that within a single theory L (maybe with number references), it is possible to represent empty sets with different sizes in this sense?"

Well, personally I'm not entirely on-board with that idea, for the reasons I stated in my reply to David above: "Note also that for each single theory, the empty set still remains a unique object/element, as theories are usually based on a single logic."

My position is such, due to what I mean by "different orders of emptiness". But this is not to say that I'm not open to the variation of this idea, which you and the company of famous thinkers suggest. :)

Andrew Kelley· 2 months ago
Francisco, thank you for this example. I think you may be right but I am finding it extremely hard to wrap my brain around it.

Hayden VanIderstine· 2 months ago
Francisco, in order for the hypothesis that there exists no bijection between all possible values of g(y) and f(x) when x,y>ϵ, then it is necessary that the cardinality of the set of all possible g(y) with y>ϵ be different from the set of all possible f(x) with x>ϵ. For this to be the case, then both sets cannot both be of any of the following cardinalities:

Finite
Countably infinite (set of naturals)
Uncountably infinite 1 (set of reals)
Uncountable infinite 2 (set of all functions defined from the set of reals to the set of reals)

What I am wondering, is what is the domain and range of f and g, because if they both have a range being a subset of the real numbers (or the entire set of real numbers), then there necessarily exists a bijection between them.

Francisco Vasconcelos· 2 months ago
Hayden,

I'm not sure I follow you. The way I see it, for there to be no bijection it is only required that the domain of f(x),x>ϵ has a different cardinality of g(y),y>ϵ. So, for example if the domain of f(x) is a subset of the rational numbers, and the domain of g(y) is an interval of the real numbers, then there is no bijection.


Hayden VanIderstine· 2 months ago
In my opinion, excellent post Mariusz. I am thinking in a new way now thanks to you.

What we consider as empty is dependent on what we acknowledge exists.

{n∈N | 1 < n < 2} =  ∅
Exactly  |N| elements fail to be in the set {n∈N | 1 < n < 2}

But exactly |R| elements fail to be in the set {x∈R | 1 < x < 2}.

According to your definition of the rarity of some empty set, would the rarity of the empty set in a logic which isn't strong enough to construct the reals, but is strong enough to construct the naturals, be |N|, because there are only a countably infinite number of sentences like 1 < n < 2 which could be made which are impossible?

(btw, I'm not well versed in formal logic, nor am I sure that there exists a logic which is strong enough for the naturals, but not enough for the reals).

Mariusz Popieluch· 2 months ago
Hayden - thank you for your insightful reply and interpretation of the ideas in this thread. Your observations, and question also made me think more carefully about what I'm proposing.

The natural numbers, or Peano arithmetic, is a first order theory, whereas the it is not possible to characterize the reals with first-order logic alone since the supremum axiom of the reals quantifies over subsets of the naturals, and is therefore a second-order logical statement. See the list of axioms here: https://en.wikipedia.org/wiki/Real_number#Axiomatic_approach

The stronger logic in which the axioms of R are expressed is second order logic, which is stronger than first order. So to answer your question directly - first order logic is the logic "which is strong enough for the naturals, but not enough for the reals", for the reasons given above.

(Note on the terminology: Logic B is stronger than logic A iff all theorems of A are B therorems, and there exists some B theorem that's not an A theorem. Or equivalently B is a stronger logic than A iff the set of A theorems is a proper subset of B theorems.)

Mariusz Popieluch· 2 months ago
Also, to clarify - "What we consider as empty is dependent on what we acknowledge exists." is not entirely correct.

Rather "What we consider as empty is dependent on what we acknowledge can exist.".

Pedro Forquesato· 2 months ago
Hello Mariusz,

Nice post! It brought a good discussion, and that is the purpose of this forum. I think your stories are good examples of the importance of clear and rigorous (for example mathematical) sentences in philosophy (and other studies), and the danger of "spoke communication".

Let's try to solve it by translating to "mathematical language" what they are saying. In the case of the urns, for example, when the apprentice says "the urn is empty", he means (lets define U as urn and W as the set of white marbles):
U = { }
While when the master says "the urn is empty", rigorously he means:
U intersection W = { }

So while in English what they say is the same, actually they are saying different logical propositions, and thus it is not paradoxical that the second might be true while the first is not. It is not the empty sets that are different, it is the translation from English to logic that differs. (Naturally the same argument is valid for the poet's glass).

Mariusz Popieluch· 2 months ago
Thank you for your reply Pedro - if you're interested in a mathematical treatment of the idea, don't look at the intuitive illustrations of the marble shop, and the trio drinking wine. Instead focus on the content of the OP that follows the phrase "The general claim is...". :)

-------------------------------
-------------------------------

To be continued...

Tangibility of the transcendental 2 - updated.

I'm re-posting this blog entry with a crucial correction to the λ function, which previously wasn't properly defined. 


"I was doing a bit of reading about transcendental numbers today, and had an idea of constructing my own well defined transcendental. I was inspired by the Liouville constant. Anyway, my idea was to construct a number which is a base 10 concatonation of the digits of consecutive prime numbers:

m_p =  0.2357911131719232931...
or the natural numbers:
m_N = 0.12345678910111213...
The construction proceeded as follows. First we define the function λ:→. Intuituively λ(n) gives the number of digits in n, i.e. the "length" of n in base 10.

Now we can express the numbers as infinite sums:

Where p_n is the n'th prime.

Initially I thought this to be an exercise in creative procrastination, since firstly the idea is dead simple, and secondly who would be silly enough in going to the trouble of formulating such numbers. Surely only a fresh graduate with too much time on his hands.

To my surprise the idea behind those numbers has been already formulated by not one, but a few mathematicians. My m_N is in fact a constant previously formulated by D. G. Champernowne. And it turns out that m_p is already known as the Copeland-Erdos constant:

Notice the striking similarity in the formulation - I have formulated m_p completly oblivious to the Copeland-Edros formulation. The similarity lies in the fact that my λ function acts a lot like the floor of base 10 logarithm of y. In fact the relation is the following:

Which makes the sums in the exponents of the definitions of m_p and the Copeland-Edros constant equal, since for each i we subtract 1 i.e. we subtract 1, k times, so we need to add k back to the sum. And consequently,

Well, I guess I feel better knowing that I'm in good company deeming quite obscure and prima facie pointless ideas valuable. I knew that both m_N and m_p are irrational, but now I also know that m_N is in fact transcendental (mission accomplished!), and hence don't have to provide a proof, which I suspect would be a herculean task."

My independent discovery of the sequence A007526

I came across a rather surprising property of the above recurrence relation which I defined when counting the number of models of conditional logics with Lewis-Stanlaker type semantics, i.e. similarity spheres. Because the structure of nested sphere assignments happens to correspond in its form to permutations of non-empty subsets of some set, the formula, known to combinatorialists since Bernoulli, had emerged.

Below is an example taken from The Encyclopedia of Integer Sequences: sequence A007526 entry.

I say those properties were surprising given the context, for in and of themselves they’re not surprising at all. I simply didn’t expect such interesting properties to be inherent in the structure of the systems I was studying.

The sequence s is related to the number of models, given certain parameters (more precisely, the parameter is the size of the filter which is the set of all subformulae of a formula whose satisfiability is being tested - hence the requirement to generate all and only those models which are sufficient and necessary for that task), and given by the following recursive definition:

And this is the "curious" result, which links the above recursively defined function with Euler's Constant e:

It's easy to show that the explicit solution to the above recursive definition of s is given by the formula:

And considering the well known Taylor series, it's easy to show that the result stated above follows.

It turns out that this is a known sequence A007526., whose earliest references are Izquierdo (1659), Caramuel de Lobkowitz (1670), Prestet (1675) and Bernoulli (1713). So it appears that I've discovered/defined this sequence independently of those great mathematicians.

Combinations, permutation matrices, and a solution to n-valued valuations (truth value assignments for many-valued logics).

This result can be interpreted as a solution to n-valued valuations (truth value assignments for many-valued logics). A detailed proof is given in a later post.

First we define and construct the extensional valuation function , (intuitively, it can be thought of as the generating function for the classical truth table). The valuation function θ will have dimensions (k = 2ⁱ rows by i columns), and the value of each binary entry is given by the following formula, as can easily be checked.

Example θ(7,2), represented on a truth table exhausting all valuations (truth value assignments) for 3 propositional variables (atomic formulae). CORRECTION --- the formula works for the table generated such that zeros come before ones, i.e. with the ones and zeros inverted, so the table below is generated incorrectly for this formula, as we should start with zeros first. (Consequently all the m-valued generalizations should be generated analogously --- starting with the smallest value.)

This map, i.e. θ can be generalized to m-ary truth values. The explicit formula is given below:

I've skipped examples here, naturally since the truth matrices get very large, very quick.

Those explicit solutions to the recursive definitions (truth tables) make computation significantly more efficient. They also turn out to be handy (they're both elegant and compact) when writing algorithms for k combinations on n sets, or k partitions on n sets. They should prove useful to anyone working in writing algorithms for systems based on multiple value assignments.

Proof (sketch) --- a detailed proof is given in a later post.
First we express the truth tables as recurrence relations of congruences modulo the number of truth values in that given logic, then solve them by iteration, i.e. see the pattern. Finally give the solutions an elegant form (ceiling notation) using some useful number theoretic identities. QED

Constructing a set disjoint from, and equinumerous with any other set.

A while ago I needed (a lemma in a larger proof) to construct for any arbitrary set A, another set that is disjoint from A and of the same cardinality as A (without the use of higher machinery of ordinals). The task is harder than it may seem. One may choose to attempt a proof by contradiction. One of my friends has in fact proceeded that way. I came up with the following construction which I’m quite fond of.

First, let me state a theorem (which is a direct consequence of Russell’s paradox) that I helped myself to.

Theorem. For each set S, the set

Is not a member of S.

For if we assume otherwise, an immediate contradiction ensues, for

Now for the construction. Let’s take some set A, and construct a set B that is disjoint from it, and equinumerous with it. Consider the set

Theorem: For any set A the following set B is disjoint from A and equinumerous with it:

Less formally

It is clear that B has the same cardinality as A. (post-Clarification: just to be pedantic, it's not just the triple x, y, z that is in A, but rather I should have written "for x, y, z,... in A". I forgot the ellipsis.)

It is also clear that,

since,

which is impossible by construction of R_A . Hence B is equinumerous to, and disjoint from A. QED

Number Theory 4: The value of Euler's phi function for a product of Fibonacci sequence terms

There’s a corollary to the result fom the previous post. Each two consecutive terms of the Fibonacci sequence are relatively prime. Hence the following follows immediately, for the n product of Fibonacci terms.

Substituting into the formula, yields 

Number Theory 3: A formula for calculating Euler's phi function

Below is a proof for calculating phi (Euler’s function) for any natural number. Phi(m) is defined to be the number of all natural numbers n less than m that are relatively prime to it i.e. each such n<m satisfies gcd(n,m)=1.

The p’s in the above formula denote primes. The proof will be relatively simple, as it will use the following fundamental results, where p denotes a prime and m and n are relatively prime.:

 By the Fundamental Theorem of Arithmetic we express m in terms of its unique prime factorization,

 Re writing the expression and, by associative law, multiplying the first two terms we have the following,

and substituting m’s prime factorization yields,

Further algebraic manipulation gives,

Now, by repeated use of associative law, factoring out each consecutive prime in m’s factorization and multiplying it by the term from the original formula where that prime appears,

leaves us with the product rearranged to the following form,

Finally we resort to (*), and (**) to get