1. We have added a Gift Upgrades feature that allows you to gift an account upgrade to another member, just in time for the holiday season. You can see the gift option when going to the Account Upgrades screen, or on any user profile screen.
    Dismiss Notice

Let's discuss Mathematics

Discussion in 'Science & Technology' started by ParadigmShifter, Mar 16, 2009.

  1. monikernemo

    monikernemo Warlord

    Joined:
    May 9, 2020
    Messages:
    240
    Gender:
    Male
    Not really, after all sets have very little to no structure.
     
  2. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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.

    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).
     
    Last edited: Dec 1, 2020
  3. monikernemo

    monikernemo Warlord

    Joined:
    May 9, 2020
    Messages:
    240
    Gender:
    Male
    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.
     
  4. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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.
     
    Last edited: Dec 1, 2020
  5. monikernemo

    monikernemo Warlord

    Joined:
    May 9, 2020
    Messages:
    240
    Gender:
    Male
    (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 likes this.
  6. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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.
     
    Last edited: Dec 1, 2020
  7. monikernemo

    monikernemo Warlord

    Joined:
    May 9, 2020
    Messages:
    240
    Gender:
    Male
    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. :p
     
    Kyriakos likes this.
  8. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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.
     
    Last edited: Dec 1, 2020
  9. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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 )
     
    Last edited: Dec 1, 2020
  10. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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: Dec 6, 2020
  11. monikernemo

    monikernemo Warlord

    Joined:
    May 9, 2020
    Messages:
    240
    Gender:
    Male
    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 likes this.
  12. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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: Dec 6, 2020
  13. monikernemo

    monikernemo Warlord

    Joined:
    May 9, 2020
    Messages:
    240
    Gender:
    Male
    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 likes this.
  14. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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!
     
  15. monikernemo

    monikernemo Warlord

    Joined:
    May 9, 2020
    Messages:
    240
    Gender:
    Male
    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.
     
  16. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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.
     
    Last edited: Dec 6, 2020
  17. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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?
     
  18. monikernemo

    monikernemo Warlord

    Joined:
    May 9, 2020
    Messages:
    240
    Gender:
    Male
    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.
     
  19. Kyriakos

    Kyriakos Alien spiral maker

    Joined:
    Oct 15, 2003
    Messages:
    59,954
    Location:
    Thessalonike, The Byzantine Empire
    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: Dec 15, 2020

Share This Page