cardinality (complicated question(s), cute answ...

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

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

Originally posted by genius
Q=the Rational Numbers={a/b, a,b, contained in Z}

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?

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

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 😉

Originally posted by FabianFnas
Now I totally agree in the definition of Q.

What was the title of the course? "Set theory"?

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 😉

Originally posted by PBE6
The "answer" to question (4) sounds very interesting...could you expand on this?

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 🙂

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

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

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

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 🙂

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!