 cardinality (complicated question(s), cute answ... genius Posers and Puzzles 25 Mar '07 15:18
1. 25 Mar '07 15:188 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. 25 Mar '07 15:211 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. 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. 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. 25 Mar '07 19:131 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. 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. 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. 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. 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. 26 Mar '07 22:503 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. 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. 29 Mar '07 09:592 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. 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]