Let's discuss Mathematics

I have a question about diagonalisation (to show that some sets with infinite members are not countable/of larger cardinality; eg R>N)

While I get the argument for 1 to 1 (from both sides), that for two infinite sets to be of the same cardinality there should be some way to form every member of the second set by altering the first (eg k -> 2k for comparing all naturals to just the even ones, or something like (k,-(k-1) for naturals -> integers), I am having considerable difficulty with the argument for showing that [0,1] is not countable, and by extent that the cardinality of all the Reals is the same as that of any of their parts (such as 0,1).

My problem in understanding rests on the following:

Let's say that (to avoid different numbers) the set of [0,1] was written in binary, and you'd get something like all possible variations of 0 and 1. Obviously for any finite bit of that (eg a bit which only had 8 positions, such as 01010101), the complete list of variations would be 2^8 (2 different choices in each position). And for an infinite string this would have been going on forever. Now, writing the supposed "first" of such strings thus:

1. 00101101001...
2. 01010100011...
...
The diagonalisation argument seems to be that any such grouping would already include added bits, and if (for example) you change the first digit of the first from 0 to 1, and the second of the second from 1 to 0, you already have a new string.
But I do not get how it stops mattering that, ultimately, if the list goes on, at some position you'd have this new element. I get that the alteration of x bit occurs in ALL the list; I just don't get how the list isn't supposed to already include it by virtue of being a list. Ie I don't see the clear tie to how this doesn't allow any numbering of such a list.

Help would be very welcome. It would certainly save me time!!!!

Edit: To be more precise: I do not get why this is proof by proving one counter-example (the diagonalisation) and also how the diagonilization itself is somehow apparently forced on something already by definition an infinite gathering of (all) possible variations. Maybe this is in reality about showing that no set function from A (naturals) to B (0,1 etc) can work, but currently I haven't been able to see how this is presented by the diagonalisation method.
 
Last edited:
My problem in understanding rests on the following:

The diagonalisation argument seems to be that any such grouping would already include added bits, and if (for example) you change the first digit of the first from 0 to 1, and the second of the second from 1 to 0, you already have a new string.

But I do not get how it stops mattering that, ultimately, if the list goes on, at some position you'd have this new element. I get that the alteration of x bit occurs in ALL the list; I just don't get how the list isn't supposed to already include it by virtue of being a list. Ie I don't see the clear tie to how this doesn't allow any numbering of such a list.
Concretely one can think of binary representations as a map from a:N -> {0,1} with a(i) being the i-th number in the coefficient and the number a is denoted by a = sum a(i)2^-i.

Now if a set S is countable, there exists a bijection between N -> A. Concretely, we can find an enumeration for elements in A say a0, a1, ..., aj, ... and it goes on.

What the diagonal argument achieves is cooking up an element, say call it x such that x = sum (1- a(i))2^-i.Now one can check that it is different from every element of A, which is a supposed list of all the elements (the idea is to look at x - ai for every i and one observes that the difference is non-zero, so x is different from every ai and we conclude that x is not in the enumeration since ai, which is a contradiction. However, to be absolutely pedantic, there are some subtleties that need to be resolved).
 
Concretely one can think of binary representations as a map from a:N -> {0,1} with a(i) being the i-th number in the coefficient and the number a is denoted by a = sum a(i)2^-i.

Now if a set S is countable, there exists a bijection between N -> A. Concretely, we can find an enumeration for elements in A say a0, a1, ..., aj, ... and it goes on.

What the diagonal argument achieves is cooking up an element, say call it x such that x = sum (1- a(i))2^-i.Now one can check that it is different from every element of A, which is a supposed list of all the elements (the idea is to look at x - ai for every i and one observes that the difference is non-zero, so x is different from every ai and we conclude that x is not in the enumeration since ai, which is a contradiction. However, to be absolutely pedantic, there are some subtleties that need to be resolved).

I need the subtleties too!
The goal is to understand how this works as it was conceived. That would be a good base. I cannot but suppose (naturally) that this has to work in the manner it was conceived, and at least in regards to cardinality of N < Cardinality of R :) (which I need, at any rate, for understanding the full Goedel theorems)
So any other relevant info you can think of, please post or link :D

Also (although I am not sure how good this is as a starting point...), maybe you can account for how equivalent tricks can be proven to not exist for comparing countable infinite sets? Eg why it is impossible to not cook up something similar/"similar" to mess up the counting of positives -> integers*. Maybe this would help me see it, by seeing how it is impossible elsewhere :)
(ultimately anything even more helpful would be great, thanks :D )

(else I will have to stop being so lazy - but let's give it a last shot, it is hard for me to give up being lazy)

*I suspect this would be possible, but not possible in the specific system used. So again, I am trying to comprehend the system/how it was originally presented and accepted, so as to have this as a base.
 
Last edited:
I need the subtleties too!
The goal is to understand how this works as it was conceived. That would be a good base. I cannot but suppose (naturally) that this has to work in the manner it was conceived, and at least in regards to cardinality of N < Cardinality of R :) (which I need, at any rate, for understanding the full Goedel theorems)
So any other relevant info you can think of, please post or link :D

The subtlety here is that some two numbers in the interval can have different representations in binary (i.e. trailing 1s, exists n such that for all m> n we have m-th digit to be 1 or trailing 0s) , so first one needs to fix a representation for all elements in A e.g. choose trailing 1s over trailing 0s.

Next one also need to argue that x does not have trailing 1s or trailing 0s, in particular, this ensures that x-aj is non-zero for all j.
 
The subtlety here is that some two numbers in the interval can have different representations in binary (i.e. trailing 1s, exists n such that for all m> n we have m-th digit to be 1 or trailing 0s) , so first one needs to fix a representation for all elements in A e.g. choose trailing 1s over trailing 0s.

Next one also need to argue that x does not have trailing 1s or trailing 0s, in particular, this ensures that x-aj is non-zero for all j.

I will have a real look at your two posts. Just let me try again to get you to help me stay lazy by having a look at the revised version of the post you quoted, and see if anything of use can be provided for the new points :D
Otherwise: thank you!
 
I
Edit: To be more precise: I do not get why this is proof by proving one counter-example (the diagonalisation) and also how the diagonilization itself is somehow apparently forced on something already by definition an infinite gathering of (all) possible variations. Maybe this is in reality about showing that no set function from A (naturals) to B (0,1 etc) can work, but currently I haven't been able to see how this is presented by the diagonalisation method.
What the proof demonstrates is that given any enumeration of the interval, one can always produce an element that is different from all elements in the enumerations, and hence, there are no enumerations that exists.
 
I know what it is supposed to be demonstrating, I am just not seeing it currently. So I will have to examine it myself - which is fair enough; after all only the individual is aware of what they need.
Thank you :)

Edit: very luckily, the wiki page on this actually is closer to what makes an impression to me and can use to get into this:

9g6asXI.png


Shows a construction of a bijection from the diagonalisation example to R, and also an injection (trivial) to a subset of R.

In retrospect, not much of a surprise, assuming this is what Cantor used (or very similar) to present his original argument - since original arguments have to be very presentable if they are to survive.
 
Last edited:
I promise this will be the last question from me (at least for a while!)

But it is easy to answer with yes or no (if the answer is "yes", a link with the proof would be great :) )



Can the property of continuous fractions shown in (eg) 0.999..... = 1, be proven in a formal logic structure of Peano arithmetic?
 
what do you mean by a `formal logic structure of Peano arithmetic'? This is true under the usual construction of the reals, either by Dedekind cut of rational numbers, or (equivalence class of) Cauchy sequences of rational numbers.
 
what do you mean by a `formal logic structure of Peano arithmetic'? This is true under the usual construction of the reals, either by Dedekind cut of rational numbers, or (equivalence class of) Cauchy sequences of rational numbers.

I asked if you can prove it using formal logic. Ie if it is formable as a theorem in some formal logic system.
Obviously lots of things are provable, but a lot fewer using a formal logic system, cause it is more confined. Maybe an altered version of the successor function could be used in some way.
 
Last edited:
I do not really get it, but they have figured out a bit more of Anaxagoras of Clazomenae's problem about squaring the circle?

Around 450 BCE, Anaxagoras of Clazomenae had some time to think. The Greek mathematician was in prison for claiming the sun was not a god, but rather an incandescent rock as big as the Peloponnese peninsula. A philosopher who believed that “reason rules the world,” he used his incarceration to grapple with a now-famous math problem known as squaring the circle: Using a compass and a straightedge, can you produce a square of equal area to a given circle?

The exact question posed by Anaxagoras was answered in 1882, when the German mathematician Ferdinand von Lindemann proved that squaring the circle is impossible with classical tools. He showed that pi — the area of a circle with a radius of 1 — is a special kind of number classified as transcendental (a category that also includes Euler’s number, e). Because a previous result had demonstrated that it’s impossible to use a compass and a straightedge to construct a length equal to a transcendental number, it’s also impossible to square a circle that way.

Tarski's Circle Squaring Problem from 1925 asks whether it is possible to partition a disk in the plane into finitely many pieces and reassemble them via isometries to yield a partition of a square of the same area. It was finally resolved by Laczkovich in 1990 in the affirmative. Recently, several new proofs have emerged which achieve circle squaring with better structured pieces: namely, pieces which are Lebesgue measurable and have the property of Baire (Grabowski-Máthé-Pikhurko) or even are Borel (Marks-Unger).

In this paper, we show that circle squaring is possible with Borel pieces of positive Lebesgue measure whose boundaries have upper Minkowski dimension less than 2 (in particular, each piece is Jordan measurable). We also improve the Borel complexity of the pieces: namely, we show that each piece can be taken to be a Boolean combination of Fσ sets. This is a consequence of our more general result that applies to any two bounded subsets of Rk, k≥1, of equal positive measure whose boundaries have upper Minkowski dimension smaller than k.​

ezgif-5-ac00275e15.gif


Writeup Paper
 
Last edited:
I do not really get it, but they have figured out a bit more of Anaxagoras of Clazomenae's problem about squaring the circle?

Around 450 BCE, Anaxagoras of Clazomenae had some time to think. The Greek mathematician was in prison for claiming the sun was not a god, but rather an incandescent rock as big as the Peloponnese peninsula. A philosopher who believed that “reason rules the world,” he used his incarceration to grapple with a now-famous math problem known as squaring the circle: Using a compass and a straightedge, can you produce a square of equal area to a given circle?

The exact question posed by Anaxagoras was answered in 1882, when the German mathematician Ferdinand von Lindemann proved that squaring the circle is impossible with classical tools. He showed that pi — the area of a circle with a radius of 1 — is a special kind of number classified as transcendental (a category that also includes Euler’s number, e). Because a previous result had demonstrated that it’s impossible to use a compass and a straightedge to construct a length equal to a transcendental number, it’s also impossible to square a circle that way.

Tarski's Circle Squaring Problem from 1925 asks whether it is possible to partition a disk in the plane into finitely many pieces and reassemble them via isometries to yield a partition of a square of the same area. It was finally resolved by Laczkovich in 1990 in the affirmative. Recently, several new proofs have emerged which achieve circle squaring with better structured pieces: namely, pieces which are Lebesgue measurable and have the property of Baire (Grabowski-Máthé-Pikhurko) or even are Borel (Marks-Unger).

In this paper, we show that circle squaring is possible with Borel pieces of positive Lebesgue measure whose boundaries have upper Minkowski dimension less than 2 (in particular, each piece is Jordan measurable). We also improve the Borel complexity of the pieces: namely, we show that each piece can be taken to be a Boolean combination of Fσ sets. This is a consequence of our more general result that applies to any two bounded subsets of Rk, k≥1, of equal positive measure whose boundaries have upper Minkowski dimension smaller than k.​

ezgif-5-ac00275e15.gif


Writeup Paper

They are answering a different question here. The classical question of squaring the circle (which means to construct a square with same area of circle via compass and straight-edge construction) is resolved and is deemed impossible. The question stated in the paper asks if you can cut a disk into finitely many pieces and reassemble them by rotation and translation to get a square of the same area. But cutting up a disk into pieces in mathematics can mean absolutely ridiculous things and not just a naive slicing and dicing. This does not contradict the classical question of squaring a circle since they are fundementally asking about different things.
 
Can someone explain this question from the ChatGPT does an MBA paper?

QUESTION 5

The Pennsylvania Department of State is implementing a new electronic voting system. Voters will now use a very simple self-service computer kiosk for casting their ballots. If that kiosk is busy, voters will patiently queue up and wait until it is there turn.

It is expected that voters will spend on average 5 minutes at the kiosk. This time will vary across voters with a standard deviation of 5 minutes. Voters are expected to arrive at a demand rate of 10 voters per hour. These arrivals will be randomly spread out over the hour (you can assume that the number of voters arriving in any time period follows a Poisson distribution).

What is the average amount of time that a voter will have to wait before casting their vote?

Answer

To find the right answer, one must look at a standard equation from queuing theory. The equation for the average waiting time states that:

Average Waiting Time = Average Processing Time x Utilization / (1-Utilization). Plugging in an average processing time of 5 minutes and an average utilization of 5/6, we get:

Average Waiting Time = 5 x (5/6) / (1 - 5/6) = 25 minutes.

So, the correct answer is 25 minutes waiting in line. If we add the 5 minutes at the kiosk, we obtain a total of 30 minutes.

Sniff Test

If you can process 12 an hour and expect 10 an hour I would intuitively expect the mean wait time will be closer to zero than five people in front of you in the queue.

The wait for the first person will always be zero. At a rate of 10/hour surely the time the poll is open will be significant to the overall mean waiting time?

However this is an apparently reputable paper that is ited all over in the discussion about AI and stuff, so one would expect me to be wrong rather than them.
 
Asked in another part of the forum, copied here.
This seems to give all the needed info, from a first glance:

It says you manually use prompts to define the set (eg in the example, from b2 to b14) and have the program divide the values into quartiles. Following that, it establishes outliers according to a specific ratio to the interquartile range 1,3.
In the end of the article, it also gives a function which is built-in to give the mean average while allowing you to define the percentage you want to identify as outlier.
 
Last edited:
They have invented a new shape

1200.jpg


Called ‘the hat’, the 13-sided shape can be arranged in a tile formation such that it never forms a repeating grid

One of mathematics’ most intriguing visual mysteries has finally been solved – thanks to a hobbyist in England.

The conundrum: is there a shape that can be arranged in a tile formation, interlocking with itself ad infinitum, without the resulting pattern repeating over and over again?

In nature and on our bathroom walls, we typically see tile patterns that repeat in “a very predictable, regular way”, says Dr Craig Kaplan, an associate professor of computer science at the University of Waterloo in Ontario. What mathematicians were interested in were shapes that “guaranteed non-periodicity” – in other words, there was no way to tile them so that the overall pattern created a repeating grid.

Such a shape would be known as an aperiodic monotile, or “einstein” shape, meaning, in roughly translated German, “one shape” (and conveniently echoing the name of a certain theoretical physicist).

Now, mathematicians appear to have found what they were looking for: a 13-sided shape they call “the hat”. The discovery was largely the work of David Smith of the East Riding of Yorkshire, who had a longstanding interest in the question and investigated the problem using an online geometry platform. Once he’d found an intriguing shape, he told the New York Times, he would cut it out of cardstock and see how he could fit the first 32 pieces together.

Spoiler A video, but I do not understand it :
 
(massive edit)
Hm, I'd like to read Penrose's reaction to this!
Up to now I (falsely) thought he had actually proven that you need at least two tiles for aperiodic tiling.
 
Last edited:
I have to admit I do not know what is different between this story and the one above. The tile is different though.

This infinite tiling pattern could end a 60-year mathematical quest

After 60 years of searching, mathematicians might have finally found a true single ‘aperiodic’ tile — a shape that can cover an infinite plane, but never make a repeating pattern.

Periodic tilings have translational symmetry: a honeycomb pattern, for example, can be repeated forever and looks identical after being shifted in any of six directions by any number of cells. But in aperiodic tilings any such shift is impossible.

In March, a team announced an important breakthrough in the search for an aperiodic tile. David Smith, a hobbyist mathematician based in Bridlington, UK, discovered a shape that he suspected could be an aperiodic tile and, together with three professional mathematicians, Smith wrote up a proof that his tile — together with its mirror, or flipped, image — could be used to build infinite aperiodic tilings of the plane. (The proof has not yet been peer reviewed, although mathematicians have reportedly said that it seems to be rigorous.)

Smith’s shape was not a single aperiodic tile, because it and its mirror image are effectively two separate tiles — and both versions were required for tiling the entire plane. But now the same group of mathematicians has reported a modified version of their original tile that can build aperiodic tilings without being flipped2.This proof was posted on the preprint server arXiv and has not yet been peer reviewed.

The first aperiodic tilings were discovered in the 1960s, and they involved 20,426 tile types. After various improvements, Roger Penrose, a mathematician at the University of Oxford, UK — who won a Nobel Prize in Physics in 2020 for his foundational work on the theory of black holes — discovered the first aperiodic tiling made of only two tile types that were not merely mirror images of each other. Penrose’s tilings now adorn the patio of Oxford’s mathematics department.

Spoiler Images :

d41586-023-01801-8_25428058.jpg


d41586-023-01801-8_25428054.jpg

Writeup Single tile paper Mirror image tile paper
 
My FB feed gave part of a video featuring a prisoner math problem - and this forum appears to be full of mathematicians!

100 Prisoners, numbers 1 to 100.
Each prisoner searches 50 (of 100) cells to find his number.
If all 100 prisoners find their number, they win.
If one fails to find his number, they lose.

I am told there is a strategy to improve the probability of success from negligible to 31%. I stopped the video (I think it is from Veritasium) to avoid seeing the solution, but the FB algorithm will make the video disappear. I will take a few days and give this one a go. :D

EDIT 1: I will add information as I think of it...
I believe Prisoners 1 through 100 operate sequentially as opposed to independently. This might not matter because we can run a strategy based on the assumption that the previous prisoner succeeded. So if Prisoner 1 searched Cells 1 through 50 and found his number, then that provides additional information for Prisoner 2.

ADDED 2:
100 factorial is the number of permutations. That might become relevant later.
We can reduce the probability of success to 0. We can have all prisoners choose cells 1-50 and this guarantees that half of them do not find their number.

ADDED 3:
I would do better to reduce the value of N from 100 to a more manageable number such as 2, then 4, then 6, then 10. Whatever the solution is, it will extend to larger numbers.
Also I would do well to watch the first part of the video again to determine if I missed a key piece of information.
 
Last edited:
Back
Top Bottom