Page 2 of 2 FirstFirst 12
Results 11 to 16 of 16

Thread: Infinite Sets

  1. Top | #11
    Quantum Hot Dog Kharakov's Avatar
    Join Date
    Aug 2000
    Location
    OCCaUSA
    Posts
    4,344
    Archived
    3,383
    Total Posts
    7,727
    Rep Power
    75
    Quote Originally Posted by lpetrich View Post
    Quote Originally Posted by Kharakov View Post
    The power set of a set doesn't have a bijection with the set in most cases, this doesn't mean that the power set has more elements- it just means mapping them one to one is not possible.

    Infinite elements= infinite elements. They don't have a set size.
    So are you claiming that there is no such thing as an infinite set? That the only sets are finite ones?

    What makes a difference here?
    Whether or not a power set has more elements than its root set, Mr. infinity to the infinitieth power.

    It's like equating \lim_{x\to+\infty} \,\, x \, < \,x^2 with {+\infty}<\,{+\infty}^2...

  2. Top | #12
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,066
    Archived
    16,829
    Total Posts
    22,895
    Rep Power
    79
    Georg Cantor thus concluded that there is a series of infinite cardinalities or set sizes. He called the series aleph-0, aleph-1, aleph-2, ... or A-0, A-1, A-2, ...

    He tried to prove that C = (A-1), the Continuum hypothesis, but he failed. Later mathematicians proved that it is independent of a common axiomatic formulation of set theory, the Zermelo-Fraenkel axioms with the Axiom of Choice (ZFC). Both its truth and its falsehood are consistent with those axioms.


    There is a sequence of infinite cardinals that can be constructed using power sets, however, the beth numbers, after the next letter in the Hebrew alphabet. Take a countable set, and then take power sets:
    beth-0 = aleph-0
    beth-(n+1) = 2^(beth-n)
    beth-1 = C, the set size of the real numbers
    beth-2 is the set of all functions of real numbers that give real numbers
    Mathematicians have not been able to find any straightforward interpretation of beth-3 or any higher ones.

    -

    beth-0 = aleph-0
    Countably infinite sets:
    Positive integers N+, nonnegative integers N0, integers Z, rational numbers Q, real algebraic numbers A, computable numbers T, definable numbers D
    "Natural numbers" N are variously defined as N+ (starting at 1) and N0 (starting at 0).

    All n-tuples of positive integers (n finite) -- do zigzagging for pairs (2-tuples) and mathematical induction for the rest -- (A-0)^n = (A-0)
    This means that all complex integers, complex rational numbers, complex algebraic numbers, complex computable numbers, and complex definable numbers have set size aleph-0, since they are pairs of their prototype numbers.

    All finite sets of positive integers -- for each n, there are 2^n sets that may contain positive integers <= n.

    All finite multisets of positive integers -- a multiset is like a set, but with some elements repeated. One can zigzag over maximum element and maximum multiplicity.

    -

    beth-1 = 2^(A-0) = C
    The continuum cardinality:
    Real numbers R, continuous intervals in the real numbers like R(0,1) -- can be closed, semiopen, and open. For n > 1, n^(A-0) = C
    Irrational numbers, transcendental numbers, uncomputable numbers, undefinable numbers

    All n-tuples of real numbers (n finite) -- one can prove that by mapping onto R(0,1) and then interleaving the numbers' trailing digits -- C^n = C.
    All complex numbers, since they are pairs of real numbers.

    All finite subsets of real numbers.

    All sequences of positive integers (or rational numbers or other elements of countable sets) -- (A-0)^(A-0) = C
    All sequences of real numbers -- C^(A-0) = C

    All real analytic functions and real continuous functions of real numbers
    All complex analytic functions of complex numbers

    Continuous functions have f(x) = limit of n->oo for f(x(n)) where limit of n->oo for x(n) = x itself. Since every real number is the limit of some Cauchy sequence of rational numbers, and since there are C of such sequences, that means that there are C of such functions.

    -

    beth-2 = 2^C
    All functions from real numbers to real numbers: C^C

  3. Top | #13
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,066
    Archived
    16,829
    Total Posts
    22,895
    Rep Power
    79
    Now for some explicit bijections.

    Galileo's paradox -- there are as many squares of positive integers as there are positive integers themselves: n <-> n^2.

    Positive and nonnegative integers. For x in N+ (starting at 1) and y in N0 (starting at 0), x = y + 1 and y = x - 1.

    Nonnegative integers and integers in general. For x in N+: if x is even, then one gets x/2, while if x is odd, then one gets -(x-1)/2-1.

    Ordered pairs of positive integers: do zigzagging:
    (1,1) . (2,1) (1,2) . (3,1) (2,2) (1,3) . (4,1) (3,2) (2,3) (1,4) ...
    For (x,y), find z = x + y - 1, and then n = (1/2)z*(z+1) + (y-1)
    One can then find x and y from any positive integer n.

    N-tuples of positive integers in general (ordered sets of n of them). Use mathematical induction:
    Tuple (x,y, ..., z) = ((x,y, ...), z).
    If there is a bijection between (n-1)-tuples of N+ and N+ itself, then an n-tuple over N+ reduces to a pair over N+, and that has a bijection with N+.
    So every n-tuple over N+ has a bijection with N+, and (A-0)^n = (A-0).


    Taking on (A-0)^(A-0), that can be interpreted as all infinite sequences of rational numbers. That includes all the Cauchy sequences of rational numbers, and there is a surjection of these sequences into the real numbers, since a real number may be represented by more than one Cauchy sequence. Thus,
    C <= |functions of N+ to Q| = |functions of countable set to countable set|

    I don't know how to get the opposite inequality.


    For a pair of real numbers, one maps them onto R(0,1) and finds a place-system decomposition:
    a = 0.a1a2a3...
    b = 0.b1b2b3...
    One then constructs an interleaved number:
    0.a1b1a2b2a3b3...

    For an n-tuple, one repeats this operation for all the numbers, making a sequence of the numbers' first digits, then their second digits, etc. Thus, C^n = C.

    For an infinite sequence of real numbers, one maps them onto R(0,1) and then recognizes that each number has a countable number of digits:
    x(1): 0.x(1,1)x(1,2)x(1,3)...
    x(2): 0.x(2,1)x(2,2)x(2,3)...
    x(3): 0.x(3,1)x(3,2)x(3,3)...
    So one constructs an interleaved number:
    0.x(1,1)x(2,1)x(1,2)x(3,1)x(2,2)x(1,3)...
    using the zigzagging for pairs of positive integers.

    Thus, there is a bijection between the infinite sequences of real numbers and the real numbers themselves, and C^(A-0) = C.

    For continuous function s, their continuity is
    f(limit of x(k) for k to infinity) = limit of f(x(k)) for k to infinity

    Thus, f(real value) = limit of f(rational values) where the rational values form a Cauchy sequence. Thus, one can find every continuous function by finding its values for the rational numbers. There are thus at most C^(A-0) of these functions, and thus at most C of them. Since there are at least C of such functions, since there are C of the constant-valued ones, there are thus exactly C of them.


    I'm stumped by beth-2 and functions of real numbers to real numbers.

  4. Top | #14
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,066
    Archived
    16,829
    Total Posts
    22,895
    Rep Power
    79
    Now a bijection between finite subsets of N0 and N0 itself.

    For each element of N0, do a binary-system decomposition, and then turn the 1's into trues and the 0's into falses. Apply this to which elements of N0 are present: k is present if bit k is 1, and absent if bit k is 0. Since the elements of N0 are finite, they have a finite number of 1's, and thus map onto finite subsets of N0.

    One can add a count over the 1's:
    1: 0, 2: 1, 3: 0 1, 4: 2, 5: 0 2, 6: 1 2, 7: 0 1 2, 8: 3, ...
    and one gets countability there also.

    Thus, all the finite subsets of the real numbers contain a countable number of real numbers, and that set's size is thus C.

  5. Top | #15
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,066
    Archived
    16,829
    Total Posts
    22,895
    Rep Power
    79
    The operation of finding all functions from one set to another may be given the shorthand name of exponentiation of sets:
    A^B = {all functions f from B to A}

    Ordinary exponentiation to power n is using B = {1, 2, 3, ..., n}. If A is the empty set, then A^B is also the empty set. If B is the empty set, then A^B has one element, an element that may be called the empty function.

    Set exponentiation has some familiar properties: (A*B)^C = (A^C)*(B^C) and (A^B)^C = A^(B*C)
    Also inequalities:
    A1 < A2 -> A1^B < A2^B ... |A1| < |A2| -> |A1|^|B| <= |A2|^|B| for nonempty B
    B1 < B2 -> A^B1 < A^B2 ... |B1| < |B2| -> |A|^|B1| <= |A|^|B2| for nonempty A

    For finite n >= 2,

    A-0 = beth-0

    2^(A-0) = n^(A-0) = (A-0)^(A-0) = C = beth-1
    (A-0)^2 = (A-0)^n = A-0

    2^C = n^C= (A-0)^C = C^C = beth-2
    C^2 = C^n = C^(A-0) = C

  6. Top | #16
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,066
    Archived
    16,829
    Total Posts
    22,895
    Rep Power
    79
    Mathematicians recognize three different kinds of infinity:
    • Cardinal numbers, the sizes of sets.
    • Ordinal numbers, numbers in sequence.
    • Limits of arbitrarily large finite numbers.


    There is a theory of infinite ordinal numbers, and it is very different from the theory of infinite cardinal numbers. That is unlike the finite case, where cardinals and ordinals match.


    The continuum hypothesis may be stated as beth-1 = aleph-1. There is a generalization of that: beth-n = aleph-n for all ordinals n.

Similar Threads

  1. Judge loses reelection, so he sets all the defendants free
    By ZiprHead in forum Political Discussions
    Replies: 7
    Last Post: 11-13-2018, 06:36 AM
  2. Arsonist sets 7 fires at Jewish synagogues and schools
    By Underseer in forum Political Discussions
    Replies: 11
    Last Post: 11-04-2018, 05:52 PM
  3. Eleven Year Old Genius Sets Out to Prove Existence of God
    By Opoponax in forum Existence of God(s)
    Replies: 121
    Last Post: 05-29-2018, 07:11 PM
  4. God Paradox: Infinite Sets and Omniscience
    By lpetrich in forum Existence of God(s)
    Replies: 36
    Last Post: 08-10-2017, 07:52 PM
  5. Don the Con sets new Yuge approval rating record
    By funinspace in forum US Presidential Politics
    Replies: 12
    Last Post: 06-21-2017, 01:20 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •