Infinity

• Introduction to Theoretical Computer Science: Between Finite and Infinite - From Mathematical Theory to AI and Autonomous Driving

  • The concept of cardinality, if a one-to-one correspondence can be established, the cardinalities are the same.

    • It is the same as how people count objects (takker)
      • For example, let’s say there are several apples lined up.
      • To count the number of apples, you can simply count each apple by pointing at them one by one and saying “1, 2, 3, …” until you have pointed at all the apples.
        • It doesn’t have to be pointing, eye contact works too, of course.
        • The last number you said will be the total number of apples.
      • This is nothing more than establishing a one-to-one correspondence between apples and natural numbers (a subset of them).
    • The definition of cardinality is exactly the same as the naive way of counting.

  • Different infinite dimensions = unable to establish a one-to-one correspondence = different cardinalities.

    • One higher infinite dimension: it feels like there is another infinity between the selected two elements from an infinite set.

  • I feel something similar to the concept of polynomial time/exponential time (blu3mo).

  • For example, the set of integers and the set of natural numbers can be simply counted as having twice as many.

    • However, because they are infinite, this difference is crushed and a one-to-one correspondence can be established (…matching integers with natural numbers as follows: -2, -1, 0, 1, 2… with 5, 3, 1, 2, 4).
    • The reason it seems counterintuitive at first is because there is no end to counting (takker).
      • If this were between two finite sets, one of them would finish counting first and a one-to-one correspondence could not be established, resulting in different cardinalities.
        • e.g. When counting $\{0,1,2,3,4,5,6,7,8,9\}$ and $\{0,2,4,6,8\}$, the latter finishes counting first.
        • Four elements of the former cannot be matched with any element in the latter.
      • However, in the case of infinite sets, there is never a counting omission.

  • On the other hand, for example, integers and real numbers cannot be put into a one-to-one correspondence.

    • If you select two terms from the set of integers, the number of terms between them is finite.
    • If you select two terms from the set of rational numbers, the number of terms between them is infinity.
    • This comparison may be a bit off (takker).
      • The finite/infinite number of terms between two values is irrelevant.
        • It is true that there are infinitely many rational numbers between two distinct rational numbers, but it does not mean that a one-to-one correspondence cannot be established.
          • There is a way to count without omissions.
          • Ah, rational numbers and integers have the same cardinality, I see (blu3mo).
        • On the other hand, in the case of real numbers, there is no way to count without omissions in the first place.
    • The proof is the diagonal argument.
      • Proof by contradiction with the Paradox of lying.

(Information Science Expert)

---

#mathematical Girl

• The significance of dealing with sets: to handle infinities.
• It is difficult to handle infinity without using sets and logic.

#mathematics