Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member genius
    Wayward Soul
    25 Mar '07 15:18 / 8 edits
    Sets A and B have the same cardinality if there is a bijection* f : A to B. In this case, write |A| = |B|.
    The cardinality of A is less than or equal to the cardinality of B if there is an injection** f : A to B. (Write |A| (less than or equal to sign) |B|.)

    for instance, |{1,2,3}|=|{2,4,6}| using f(x)=2x. indeed, for finite sets cardinality is meerly the number of elements in a set. |{1,2,3}|=|{2,8,3}| using a rather artificial bijection.

    for infinite sets this definition still holds, although it now becomes rather counter-intuitive. We can see that there exists a bijection between N, the natural numbers***, and 2N, the even numbers, which is meerly f(x)=2x. Therefore, |N|=|2N|.

    1: easy warm-up question: does N have the same cardinality as Z, the set of integers****?

    2: hard question (hints can be given if needed): does N have the same cardinality as Q, the set of rational numbers*****?

    3: equally hard question: does N have the same cardinality as R, the set of real numbers******?

    4: Impossible To Answer question: If the answer to any of the above is no then does there exist a set A such that |N| (strictly less than) |A| (strictly less than) |S|, where S is the set where the answer was no...

    * a function f is a bijection if there exists both an injection (see below) and a surjection between the sets x and f(x). a function f is said to be surjective if its values span its whole codomain (that is, for every y in the codomain, there is at least one x in the domain such that f(x) = y)
    ** a function f is injective if f(a) = f(b) implies a = b (or a (does not equal) b implies f(a) (does not equal) f(b)), for any a, b in the domain.
    ***N=Natural numbers={0,1,2...} or {1,2,3...} depending on the definition. for our purposes here we can use either one arbitrarily.
    ****Z=the Integers={...-2,-1,0,1,2...}
    *****Q=the Rational Numbers={a/b, a,b, contained in Z, b does not equal 0}
    ******R=the Rational Numbers=Q U {any number that cannot be written as a/b. for instance, Pi, e or sqrt(2)}
  2. Standard member genius
    Wayward Soul
    25 Mar '07 15:21 / 1 edit
    sorry-had a problem with less than signs so attempted to post the rest of the post here, discovered the problem, amended it so deleted this post...
  3. 25 Mar '07 15:43
    Originally posted by genius
    Q=the Rational Numbers={a/b, a,b, contained in Z}
    If a/b, where b=0 is a member of Q, then I don't know what part of the world you're from, that can make this kind of math possible.
    Doesn't take a genius to understand that this definition is not 100% correct.

    By the way, is this a poser or is it a puzzle? From what university math book is this puzzle/poser taken from?
  4. Standard member genius
    Wayward Soul
    25 Mar '07 15:56
    Originally posted by FabianFnas
    If a/b, where b=0 is a member of Q, then I don't know what part of the world you're from, that can make this kind of math possible.
    Doesn't take a genius to understand that this definition is not 100% correct.

    By the way, is this a poser or is it a puzzle? From what university math book is this puzzle/poser taken from?
    edited...

    i'm never to sure what "poser" means. it's a problem, and it is almost completly solvable...and i got it from a past paper of one of my courses last semester, although it is worded a little differently. (there was less definitions needed )
  5. 25 Mar '07 16:06
    Originally posted by genius
    edited...

    i'm never to sure what "poser" means. it's a problem, and it is almost completly solvable...and i got it from a past paper of one of my courses last semester, although it is worded a little differently. (there was less definitions needed )
    Now I totally agree in the definition of Q.

    What was the title of the course? "Set theory"?
  6. Standard member TheMaster37
    Kupikupopo!
    25 Mar '07 19:11
    1) Yes

    2) Yes

    3) No

    4) Indeterminable. Assuming the existence of such a set A is exactly what the Continuum Hypothesis says. If you manage to prove or disprove it, you've made a mistake, since it's proven that it can't be proven or disproven

    Man, I love math
  7. Standard member genius
    Wayward Soul
    25 Mar '07 19:13 / 1 edit
    Originally posted by FabianFnas
    Now I totally agree in the definition of Q.

    What was the title of the course? "Set theory"?
    "fundamentals of pure mathematics" - the syllabus reads:

    "Review of sets, relations, functions.

    Construction and algebraic and order properties of number systems:

    - Natural Numbers: with a brief discussion of the Peano axioms.

    - The Integers.

    - The Rational Numbers: construction from integers, derivation of basic algebraic properties, Archimedean property.

    - The Real Numbers: construction via Dedekind cuts, basic algebraic properties, completeness, extraction of roots, decimal expansions, properties of e and pi.

    - The Complex Numbers: basic properties; Fundamental Theorem of Algebra.

    Infinite sets: countable and uncountable sets, cardinal numbers, arithmetic of cardinals, Axiom of Choice."

    Essentially we started with the natural numbers and the, slowly, constructed the real numbers, whilst delving into everything on the way, the fiddling around with how these sets interact.

    and our text book was "The Foundations of Mathematics: Ian Stewart & David Tall, Oxford Science Publications, 1997.".
  8. Standard member PBE6
    Bananarama
    25 Mar '07 20:59
    Originally posted by TheMaster37
    1) Yes

    2) Yes

    3) No

    4) Indeterminable. Assuming the existence of such a set A is exactly what the Continuum Hypothesis says. If you manage to prove or disprove it, you've made a mistake, since it's proven that it can't be proven or disproven

    Man, I love math
    The "answer" to question (4) sounds very interesting...could you expand on this?
  9. Standard member TheMaster37
    Kupikupopo!
    25 Mar '07 21:14
    Originally posted by PBE6
    The "answer" to question (4) sounds very interesting...could you expand on this?
    Hmm, not very much I'm afraid. I can write down CH and GCH (Generalised CH) without much effort (I recently passed Axiomatic Set Theory), though I haven't seen the proof.

    I did manage to mix it up a little, this is what I meant;

    CH: If there is an injection from N to A and an injection from A to R, then Card(A)=N or Card(A)=R

    GCH: For subsequent cardinals X and Y; If there is an injection from X to A and an injection from A to Y, then Card(A)=X or Card(A)=Y


    Here I've used the definitions I know. Card(A) is the smallest Cardinal B so that there is an isomorphism between A and B. There is a whole range of definitions preciding the definition of cardinals. It's quite an interesting subject, you really start at the foundations of math and work your way up to very large sets. It's quite interesting to know that adding CH as an axiom doesn't lead to contradictions, but taking the denial of CH doesn't either. In that respect it's much like Euclids 5th postulate.

    I can try to find something on the proof on internet, but I'm certain you can find anything I find
  10. Standard member genius
    Wayward Soul
    26 Mar '07 14:13
    Originally posted by TheMaster37
    Hmm, not very much I'm afraid. I can write down CH and GCH (Generalised CH) without much effort (I recently passed Axiomatic Set Theory), though I haven't seen the proof.

    I did manage to mix it up a little, this is what I meant;

    CH: If there is an injection from N to A and an injection from A to R, then Card(A)=N or Card(A)=R

    GCH: For subsequen ...[text shortened]... ind something on the proof on internet, but I'm certain you can find anything I find
    if we assume GHC in ZF* this implies the axiom of choice, which is dicey, philisophical territory. although AOC is assumed by most, it is still something to be wary of...i mean, remeber Hausdorff-Banach-Tarski paradox?

    *the standard axioms of set theory
  11. Standard member TheMaster37
    Kupikupopo!
    26 Mar '07 18:56
    Originally posted by genius
    if we assume GHC in ZF* this implies the axiom of choice, which is dicey, philisophical territory. although AOC is assumed by most, it is still something to be wary of...i mean, remeber Hausdorff-Banach-Tarski paradox?

    *the standard axioms of set theory
    I don't mind that one as much as the paradox of Novak in ZF;

    In every stadium a (with a an ordinal) I get countably infinite candies and give one candy away. Still I'll run out of candies.

    For others, if any of this doesn't make sense, just ask! This is one of the few subjects that really caught my interest
  12. Standard member forkedknight
    Defend the Universe
    26 Mar '07 22:50 / 3 edits
    If you want the example bijections:

    N => Z
    0 . . . 0
    1 . . . 1
    2 . . . -1
    3 . . . 2
    4 . . . -2
    etc.

    For N => Q, a 2 dimensional table must be used to visualize, and the table is read diagonally (up and right, or down and left) e.g.
    . . 1 . . 2 . . 3 . . .4 ....
    1 . 1/1 . 1/2 . 1/3 . 1/4 ..
    2 . 2/1 . 2/2 . 2/3 . 2/4 ..
    3 . 3/1 . 3/2 . 3/3 . 3/4 ..
    .. .. .. .. ..

    Now omit the repeated values and start with 0 => (1,1), 1 => (1,2), 2 => (2,1) etc.


    Question 3 is disproven by "diagonalization".
  13. Standard member TheMaster37
    Kupikupopo!
    28 Mar '07 15:55
    Originally posted by forkedknight
    If you want the example bijections:

    N => Z
    0 . . . 0
    1 . . . 1
    2 . . . -1
    3 . . . 2
    4 . . . -2
    etc.

    For N => Q, a 2 dimensional table must be used to visualize, and the table is read diagonally (up and right, or down and left) e.g.
    . . 1 . . 2 . . 3 . . .4 ....
    1 . 1/1 . 1/2 . 1/3 . 1/4 ..
    2 . 2/1 . 2/2 . 2/3 . 2/4 ..
    3 ...[text shortened]... h 0 => (1,1), 1 => (1,2), 2 => (2,1) etc.


    Question 3 is disproven by "diagonalization".
    I'm mising the negatives in your second bijection.
  14. Standard member genius
    Wayward Soul
    29 Mar '07 09:59 / 2 edits
    Originally posted by TheMaster37
    I don't mind that one as much as the paradox of Novak in ZF;

    In every stadium a (with a an ordinal) I get countably infinite candies and give one candy away. Still I'll run out of candies.

    For others, if any of this doesn't make sense, just ask! This is one of the few subjects that really caught my interest
    curious-do you know of anywhere i could read up some more on that? i can't seem to find much (and nothing that doesn't meerly refer to it ) on t'internet that i don't need an athens account for...

    from what i vaguely gathered, is the novak paradox not just a consequence of the axiom of general choice in NBG not ZF? or, indeed, meerly a consequence of NBG. However, i have just discovered that a theorem is true in NBG if and only if it is true in ZFC. unless, of course, it is the equivalent paradox? essentially they are the same paradox, Novak and Hausdorff-Banach-Tarski, meerly represented using different axioms? or am i just leaping and bounding off in the direction of ignorance?

    i like set theory too, although i prefer group theory to the wider study. groups are fun!
  15. Standard member TheMaster37
    Kupikupopo!
    29 Mar '07 21:58
    Originally posted by genius
    curious-do you know of anywhere i could read up some more on that? i can't seem to find much (and nothing that doesn't meerly refer to it ) on t'internet that i don't need an athens account for...

    from what i vaguely gathered, is the novak paradox not just a consequence of the axiom of general choice in NBG not ZF? or, indeed, meerly a consequence of NBG ...[text shortened]...

    i like set theory too, although i prefer group theory to the wider study. groups are fun!
    I don't know much of NBG, I've done all of the class in ZF

    Novak was in one of the excersizes, so I haven't seen the proof (since I didn't do the exercise). As far as I can tell Novak hold in ZF (AC isn't needed). I'll do what I can to type the exercise here.

    I'll type W when I mean omega/aleph0, and UN(n) for the union over all n. In the following the variables a and b represent ordinals.

    Define for all a in aleph1;
    Aa = { W*a + n |n in W}

    Notice:
    For all a in aleph1, for all b in aleph1
    [ a =/ b --> Aa through Ab = empty]
    and
    For all a in aleph1[Aa is countable]

    For every a in aleph1 we also define subsets of aleph1 wich satisfy the following two conditions:
    1) For every a in aleph1: Ca = Un(b in a)Ab \ Un(b in a)Bb
    2) For every a in aleph1: If Ca =/ empty then; Ba is a subset of Ca and: Ba has exactly 1 element.

    Show: There exists an a in aleph1[Ca = empty]