Page 1 of 2 12 LastLast
Results 1 to 10 of 16

Thread: Infinite Sets

  1. Top | #1
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,644
    Archived
    16,829
    Total Posts
    23,473
    Rep Power
    79

    Infinite Sets

    Our understanding of the mathematics of infinite sets owes a lot to Georg Cantor's work in the late 19th century. But it was controversial back then and into the early 20th century, though it is not very controversial now. It was controversial because some mathematicians argued that some arguments involved infinite-set proofs are illegitimate, and even that there is no such thing as an infinite set. Mathematicians like Leopold Kronecker, a contemporary of Georg Cantor.

    But that aside, I will get to the issue of cardinalities or sizes of sets. That is the count of how many elements a set has, and for set A, it is |A| or card(A). Two sets have the same cardinality / size / element count if there exists a bijection between them. A bijection? For set A to set B, a mapping gets these names if it gets these properties:
    • Injection (one-to-one): different elements of A map onto different elements of B
    • Surjection (onto): every element of B has at least one element of A that maps onto it
    • Bijection (one-to-one correspondence): both injection and surjection. Every element of B gets one and only one element of A mapped onto it.

    For a finite set A, |A| is a nonnegative integer, and for the empty set {}, |{}| = 0.

    Size equality satisfies the axioms of equality: reflexivity: x = x, symmetry: x = y gives y = x, and transitivity: x = y and y = z give x = z.


    Let's do some arithmetic on cardinalities, and do it with set theory. If A is a subset of B, A <= B, then |A| <= |B|. If A is a proper subset of B, then |A| < |B| is always true only for finite sets. For infinite sets, one can choose a proper subset A where |A| = |B|. That may even be interpreted as a defining property of infinite sets.

    Addition: if A and B are disjoint (A intersect B = {}), then |A union B| = |A| + |B|

    Multiplication: |all ordered pairs (a,b) where a is in A and b in B| = |A| * |B|

    One can get Peano's axioms out of set theory. To get those axioms' representations of numbers, one defines "0" as the empty set, {}, and the successor operation S(A) = A union {A}. Repeating the successor operation gives a unary or base-1 representation of the nonnegative integers, and applying it to this "0" gives
    {}, {{}}, {{},{{}}}, {{},{{}},{{},{{}}}}, ...


    One can easily show that these set-theory nonnegative integers and their operations have all the properties that one would expect -- commutative, associative, distributive, identities, ...

  2. Top | #2
    Veteran Member
    Join Date
    Jul 2006
    Location
    California
    Posts
    3,168
    Archived
    20,351
    Total Posts
    23,519
    Rep Power
    53
    I've read that Cantor proved that one infinity can be bigger than another infinity. Is that true?
    Do human beings have free will? I can't decide.

  3. Top | #3
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,644
    Archived
    16,829
    Total Posts
    23,473
    Rep Power
    79
    One can also define exponentiation with set theory. To do that, we start with finding the square of some cardinality / set size:

    |(a,b) for all a,b in A| = |A| * |A| = |A|^2
    Likewise, for larger tuples,
    |(a,b,c) for all a,b,c in A| = |A|^3
    |(a,b,c,d) for all a,b,c,d in A| = |A|^4

    In general,
    |(a1,a2,...,a(n)) for all a1,a2,...,a(n) in A| = |A|^n
    for nonnegative integer n. I say nonnegative, because for n = 0, one gets the empty tuple (), and the set of it has size 1.

    Let us see if we can generalize it. A tuple (a1,a2,...,a(n)) can be interpreted as a function f that reduces some component for some index value: f(1) = a1, f(2) = a2, ..., f(i) = a(i), ..., f(n) = a(n). This function accepts 1,2 , ..., n, and we can generalize that to arbitrary sets. Thus,

    |all functions f(B) -> A| = |A|^|B|

    where f(B) -> A is shorthand for f(b) = a for all b in B and some a in A.


    Let us consider an interesting case: the power set of a set, the set of all that set's subsets. Each subset can be interpreted as a function that takes that set's elements and returns true or false, depending on whether that element is in the subset or not. Thus, for a two-element set {a,b}, the subsets have functions
    {} -- f(a) = false, f(b) = false
    {a} -- f(a) = true, f(b) = false
    {b} -- f(a) = false, f(b) = true
    [a,b} -- f(a) = true, f(b) = true

    Since |{false,true}| = 2, |PowerSet(A)| = 2^|A|


    Let us consider |PowerSet(A)| and whether it is equal to |A|. We try to find a bijection between elements of A and subsets of A. Let us consider a set of "normal" subsets N, "normal" meaning that its elements x are not contained in their associated subsets X. Mapped onto it is an element of A, which I will call n. If n is in N, then by the definition of N, n must not be in N, while if n is not in N, then N must contain the element that is mapped onto N, that is, n. This contradiction proves that no bijection exists between A and PowerSet(A).

    Since all a in A have a bijection with the {a} in PowerSet(A), we have |A| <= |PowerSet(A)|. But the previous result shows that |A| != |PowerSet(A)|. This means that |A| < |PowerSet(A)|.

    Thus, for every set, one can construct a larger set from it.


    A similar sort of set is the set of all permutations of a sequence, equivalent to the set of all self-bijections of a set. For {a,b}:
    {a->a,b->b} and {a->b,b->a}

    For set A, this set, Permut(A) satisfies |Permut(A)| = |A| ! for finite A. Meaning that |Permut(A)| > |A| for |A| > 2. In fact, |Permut(A)| > 2^|A| for |A| > 3.

    elementary set theory - What is the largest set for which its set of self bijections is countable? - Mathematics Stack Exchange states that, for infinite sets,

    2^|A| <= |Permut(A)| <= |A|^|A|

    One would prove it by using proper subsets, but I haven't been very successful in that.

  4. Top | #4
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,644
    Archived
    16,829
    Total Posts
    23,473
    Rep Power
    79
    Quote Originally Posted by GenesisNemesis View Post
    I've read that Cantor proved that one infinity can be bigger than another infinity. Is that true?
    That is indeed correct.

    That follows from the size of a set always being smaller than the size of its power set, the set of all subsets of that set. Meaning that for every set, there a larger one. That holds for infinite sets as well as for finite sets, so some infinities will be bigger than other infinities.

  5. Top | #5
    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
    No he didn't. It's just an interesting troll by mathematicians.

    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.

  6. Top | #6
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,644
    Archived
    16,829
    Total Posts
    23,473
    Rep Power
    79
    Quote Originally Posted by Kharakov View Post
    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?

  7. Top | #7
    Elder Contributor
    Join Date
    Aug 2002
    Location
    Atlanta, GA
    Posts
    15,695
    Archived
    15,686
    Total Posts
    31,381
    Rep Power
    79
    Quote Originally Posted by GenesisNemesis View Post
    I've read that Cantor proved that one infinity can be bigger than another infinity. Is that true?
    Yes. Think of the set of all natural numbers and then a set of all even numbers. Both are infinite, but for every even number, there are two natural numbers.

    There is an old math puzzle (it's Hilbert's Grand Hotel Paradox actually, and it is from 1924) about a hotel with infinitely many rooms which is full. A customer arrives. How do you get him a room? Simple. You move everybody from room n to room n+1 and give the new guy the room 1.
    Then an infinite bus comes along. What does the poor guy at the front desk do? Simple! Just move every existing guest from room n to 2n and fit the new guests into the infinite number of odd-numbered rooms that are now vacant.

    Btw. that hotel's infinity pool is less deceptively named than regular infinity pools ...

  8. Top | #8
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    6,644
    Archived
    16,829
    Total Posts
    23,473
    Rep Power
    79
    Now for what sizes of infinite sets there are. The smallest one is aleph-null (A-0), the size of the set of all positive integers. Sets with that size are called countably infinite or just plain countable. Sets with larger infinities as their sizes are called uncountable.

    Aleph Null- smallest infinity? : askmath has a proof that there is no smaller one:
    In order for there to exist an infinite cardinal number less than aleph null, there must exist an infinite subset of the natural numbers that is strictly smaller than the set of natural numbers. To prove this, we would need to show that no bijection exists between the natural numbers and its carefully chosen infinite subset. A properly of natural numbers to consider is their countability and ordering. This property extends to all subsets of the natural numbers. The nth element of the natural numbers can be paired with the nth element of its infinite subset.
    Let's see what sets have size A-0. Starting with the positive integers, N+:
    1 2 3 4 5 ...

    The nonnegative integers, N:
    0 1 2 3 4 ...

    The integers, Z:
    0 1 -1 2 -2 3 -3 4 -4 ...

    For the rational numbers, Q, one needs to zigzag through them, but one can get a rational number for every positive integer. I'll do it for the positive rational numbers to avoid clutter:
    1/1 . 2/1 1/2 . 3/1 2/2 1/3 . 4/1 3/2 2/3 1/4 ...

    Since there are some duplicates, |Q| <= (A-0). But the rational numbers include the positive integers, so (A-0) <= |Q|. Thus, |Q| = (A-0).

    The real algebraic numbers A require similar zigzagging, with coefficient values 0, +-1 for linear, 0, +-1, +2 for quadratic, 0, +-1, +-2, +-3 for cubic, ... allowing degeneration into lower-order equations as one goes. Each nth-order equation has n solutions, and we must also include each of them in our zigzagging. One gets both duplication and complex solutions, and it is evident that |A| <= (A-0), and also that (A-0) <= |A|. Thus, |A| = (A-0).

    The computable numbers T require zigzagging through Turing-machine configurations that can calculate these numbers to arbitrary precision. These numbers include all the algebraic numbers, and also all the transcendental numbers that we use, numbers like e and pi. Here also, (A-0) <= |T| <= (A-0), thus giving |T| = (A-0).

    The definable numbers D are those that can be defined with some finite-sized definition, and one zigzags through them also. These numbers include the computable numbers and such uncomputable numbers as Chaitin's constant. Here also, (A-0) <= |D| <= (A-0), giving |D| = (A-0).

    One gets a hierarchy of subset inclusion:
    N+ < N < Z < Q < A < T < D < R

    All but the last one is countable, and Georg Cantor discovered that the real numbers R are uncountable. He showed that with his diagonal trick. Consider the real numbers between 0 and 1 inclusive. Suppose that they are countable. Make a list of them. Then change the first digit of the first one, the second digit of the second one, etc. That gives a number that was not in the list. This proves that the real numbers between 0 and 1 are uncountable, and thus that the real numbers in general are uncountable, since one can map from (0,1) to the entire real line with f(x) = (2x-1)/(x*(1-x)). There are the same number of numbers for a closed or semi-closed interval as for an open one, since one can push in an interval endpoint and cause an infinite chain reaction of smaller and smaller pushes. 1 -> 1/2, 1/2 -> 1/4, 1/4 -> 1/8, 1/8 ->1/16, etc.

    The cardinality or size of the real numbers is called C for continuum, and this diagonal argument works for any number base B. Thus,
    C = B^(A-0).

    B can be 2, and by mapping 0 and 1 onto false and true, one shows that the real numbers between 0 and 1 match onto subsets of N+, the set of all the digit indices. Thus, C = |PowerSet(N+)|.

  9. Top | #9
    Senior Member
    Join Date
    Nov 2002
    Location
    Bible Belt, USA
    Posts
    880
    Archived
    2,467
    Total Posts
    3,347
    Rep Power
    63
    Quote Originally Posted by Derec View Post
    Quote Originally Posted by GenesisNemesis View Post
    I've read that Cantor proved that one infinity can be bigger than another infinity. Is that true?
    Yes. Think of the set of all natural numbers and then a set of all even numbers. Both are infinite, but for every even number, there are two natural numbers.
    These sets are actually same size since you can write a one-to-one mapping of the elements:

    1 <--> 2
    2 <--> 4
    3 <--> 6
    etc.

    The natural numbers and rational numbers are also the same cardinality for the same reason. The set of irrational numbers is larger than the set of natural numbers, though.

  10. Top | #10
    Contributor
    Join Date
    Nov 2017
    Location
    seattle
    Posts
    5,028
    Rep Power
    13
    Countable in this context sounds like a reassignment of meaning.

    the set of all reals from 1 to 2 is bounded but infinite. I can add the set of 1..2 to 4..5. Operations can be derived on infinite sets.

    But assigning an integer count to an infinite set appears mutually exclusive.

    1,2,3.... can be called an infinite set, but that is a limitation of verbal language. Infinite and countable are mutually exclusive.
    k = 1,2,3...

    count = 1
    k = 1
    while forever{
    k = k + 1
    count = count + 1
    ?

    Will the term count ever stop at a finite value?

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
  •