Let's discuss Mathematics

[monikernemo]

I am interested in there possibly being some method different enough so that it may reveal more about the subsets and their relations to the original set.

Not really, after all sets have very little to no structure.

 

[Kyriakos]

Not really, after all sets have very little to no structure.

I don't agree with this (but it's not the point, and certainly not the scope).

The question is just if there is any different method at all - forget about the reasons why it could be of interest.

I have a question, about a property of powersets. Namely:
Can you prove that any element of a set will exist in half of the set's powerset, without using the method in the proof that the number of subsets is always 2^(number of elements in the original set)?
Cause obviously it is trivial to just go "you change one of the 2s to a 1, so you have half".

Basically the question is if there is some non-identical method to go about proving this, cause if there was then it could be used in synergy to the other method to show other stuff for tied subjects (and that's what interests me).

 

[monikernemo]

I don't agree with this (but it's not the point).

The question is just if there is any different method at all - forget about the reasons why it could be of interest.

Sets are a blank canvas, and I don't think there is anything more one can derive from structure of sets.

A method could be: Let A be subsets containing an element x and B be subsets not containing the element x. So there is an obvious bijection from A to B by f: A -> B with f(S) = S\{x} and g: B -> A with g(S) = S U {x}. In particular if X finite one has |A| +|B| = |P(X)| with |A| = |B| by the earlier bijection.

 

[Kyriakos]

Sets are a blank canvas, and I don't think there is anything more one can derive from structure of sets.

A method could be: Let A be subsets containing an element x and B be subsets not containing the element x. So there is an obvious bijection from A to B by f: A -> B with f(S) = S\{x} and g: B -> A with g(S) = S U {x}. In particular if X finite one has |A| +|B| = |P(X)| with |A| = |B| by the earlier bijection.

Let me translate this to english:

There is a 1 to 1 correspondence between A and B (from both sides). A contain x, B do not. One goes from a subset A to a B by just excluding x, and from B to A by containing it. The cardinality of the (finite) sets A,B is equal to the poweset only including those with element x cardinality.
(erased here something dumb I had written ^_^ ) But far more importantly I did not get how in your proof it is an "obvious" bijection (the question itself is to show that x exists in half of the subsets; you seem to start your proof by using that as true).

In other words: intuitively anyone can say "obviously any element of the original set will exist the same number of times in the powerset as any other" - what I asked is for a proof which is not using crucially stuff from the proof 2^n
Presented in a different way: what's intuitive for you is not for a machine.

 

[monikernemo]

you didn't account for subsets that have neither x or x (the empty set) nor for those that have both (the tautology of the original set). But far more importantly I did not get how in your proof it is an "obvious" bijection (the question itself is to show that x exists in half of the subsets; you seem to start your proof by using that as true).

(1) we assume law of excluded middle, so sets either contain or do not contain x.

(2) we also assume standard ZFC axioms, so in particular, A is well-formed formula:

A = {S in P(X): a in S} and B= {S in P(X): a not in S}
And it's left as an exercise to figure out why A U B = P(X) and A, B are disjoint.

(3): finally, it is an exercise (for you) to show that the maps are indeed a bijection

(4) I did not assume that half of the subsets already contain x, I merely asserted the existence A and B, which are well-formed if one assumes ZFC.

 

[Kyriakos]

I will examine your post, but it is a bit disappointing*
That obviously doesn't mean it is of no use to me.
I do question, however, if what you presented is really non-tautological with the 2^n proof. Recall that I have no use for any proof which is essentially the same. So while I will for the time being take your word this isn't the same, I do really doubt it is so ^_^

*perhaps only due to the different pacing, cause I am not yet into generalizations using the ZFC and assorted types.

 

[monikernemo]

I will examine your post, but it is a bit disappointing
That obviously doesn't mean it is of no use to me.
I do question, however, if what you presented is really non-tautological with the 2^n proof. Recall that I have no use for any proof which is essentially the same. So while I will for the time being take your word this isn't the same, I do really doubt it is so ^_^

Maybe if you can qualify what is a non-equivalent proof, and the original proof you had in mind?

I find it disappointing as well that the asker is unwilling to fill in the logical gaps, after all maths is not a spectator sport.

 

[Kyriakos]

Maybe if you can qualify what is a non-equivalent proof, and the original proof you had in mind?

I find it disappointing as well that the asker is unwilling to fill in the logical gaps, after all maths is not a spectator sport.

You are somewhat right, but not re the proof. I mentioned (ok, technically I alluded to...) a very specific proof
Here it is:
Given that the number of subsets (including empty and tautology to the original) of any original set with x number of elements is 2^x (this is true because there are only two cases for element x1 to be in the subsets or not, and this gets multiplied by the co-existence or lack of the x2,x3...xn, so it is 2(2)(2)... n times = 2^n
And since if you take one element out, this leads to one of those 2s being transformed to a 1 (cause there is only one way to not be there), it follows the sets which contain (or do not contain) any specific element are 2^n divided by 2.

Also, do excuse my tone - it's just me and I am generally playful and megalomanic. That said, in light of the above proof, do you still think that your own suggestion is not crucially the same?

Edit: Lastly, I think the equivalent question would be: can you show (without using the proof in this post as your proof or part of it) that any element of the original set will be in the powerset as many times as any of the other elements.

 

[Kyriakos]

On a different forum I read an idea which while still isn't that different, can be of use:
Someone suggested that to prove all elements of the original set appear in equal number in the powerset (which you can do formally using P(X)=2^x proof and the tied to it proof that each is in half of the subsets), you could just rename x1 to x2 etc, given obviously the position does not matter (thus you get a decently different proof of the second sentence, about all elements of X being equally in P(X)).
I like this idea, not just due to it being stealthy, but because it allows you to (for other things) tie this to probability where position does matter.
So something good came out of my questions ^_^ (here too! Thanks for your replies, @monikernemo )

 

[Kyriakos]

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.

 

[monikernemo]

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).

 

[Kyriakos]

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

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 )

(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.

 

[monikernemo]

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

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.

 

[Kyriakos]

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
Otherwise: thank you!

 

[monikernemo]

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.

 

[Kyriakos]

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:



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.

 

[Kyriakos]

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?

 

[monikernemo]

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.

 

[Kyriakos]

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.

 

[Samson]

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.​

Writeup Paper