# cardinality of infinite sets

Legal. etc. So, for the third number on the list, we see the third digit is a 0, and we choose a 1 for the third digit of our number being created. A set that is NOT countable is uncountable or uncountably infinite. There are basically two ways of doing that: if we can pair up every element a of the set A with one and only one element b of the set B so that no two elements of B are paired with the same element of A (i.e. Since |A| = |ℕ| and |ℤ| = |ℕ|, then |A| = |ℤ| = אo.∎. The concept of cardinality can be generalized to infinite sets. $$d$$ is the created number which will never be on the list. 3rd number:   0.840729312.....           our number that we are creating 0.001  Since the interval $$(0,1)$$ which is a subset of $$\mathbb{R}$$ is uncountable, then $$\mathbb{R}$$ is also uncountable (Corollary 5.6.3). Of course, finite sets are "smaller" than any infinite sets, but the distinction between countable and uncountable gives a way of comparing sizes of infinite sets as well. Before Thursday, everyone should have finished reading MCS Chapter 8. It follows the function f(n) = n/2. For a finite set, the cardinality of the set is the number of elements in the set. More formally, if we describe the "wannabe" list of real numbers in the interval $$(0,1)$$ using subscripts for each digit: $$0.a_{11}a_{12}a_{13}a_{14}a_{15} \ldots$$ We also acknowledge previous National Science Foundation support under grant numbers 1246120, 1525057, and 1413739. Thinking of how to match the natural numbers to the integers, I see how the even natural numbers could be used for the positive integers, like this: Your email address will not be published. If two (ﬁnite or inﬁnite) sets A and B are not of the same cardinality, we can try to compare which one of the two sets has at least as many elements as the other. Finite sets and countably infinite are called countable. In symbolic notation the size of a set S is written |S|. by  } f(n)=\frac{n-2}{2}.\] 6th number:   0.001101111.....           our number that we are creating 0.001100  We will deal with the idea of the cardinality of an infinite set later. Show that the set of integers ℤ is countably infinite. $$\mathbb{Z} \mbox{ and } \mathbb{Q}$$ are countably infinite sets. These will need to fit together in a piece-wise function, with one piece if $$n$$ is even and the other piece if $$n$$ is odd. One pattern we can use is to count down starting at 0, then going back and “picking up” each positive integer. Now I need to come up with a function to accomplish this mapping to the negative integers, and after some thinking, I come up with $$f(n)=-\frac{n+1}{2}.$$ Example 1. If $$S$$ is countably infinite and $$A \subseteq S$$ then $$A$$ is countable. The continuum hypothesis is the statement that there is no set whose cardinality is strictly between that of $$\mathbb{N} \mbox{ and } \mathbb{R}$$. Theorems 14.8 and 14.9 can be useful when we need to decide whether a set is countably infinite or uncountable. One function that will work is f(n) = n/2. Let $$n_i$$ be the $$i$$th smallest index such that $$x_{n_i} \in A$$. Surjectivity: Suppose the function is not surjective. Since f is both injective and surjective, it is a bijection. We can either find a bijection between the two sets or find a bijection from each set to the natural numbers. If $A$ has only a finite number of elements, its cardinality is simply the number of elements in $A$. Active 5 days ago. An infinite set is a non-empty set which cannot be put into a one-to-one correspondence with $$\{1, 2, 3, ..., n\}$$ for any $$n \in \mathbb{N}$$. These are contradictions, so the function is injective. This follows the pattern {0, -1, 1, -2, 2, -3, 3…}. Recall: a one-to-one correspondence between two sets is a bijection from one of those sets to the other. Unless otherwise noted, LibreTexts content is licensed by CC BY-NC-SA 3.0. A Tutorial in Data Science: Lecture 6 – Exploratory Data Analysis, A Tutorial in Data Science: Lecture 5 – Generating Distributions by Spectral Analysis, A Tutorial in Data Science: Lecture 4 – Statistical Inference via Systems of Hypothesis-Trees, A Tutorial in Data Science: Lecture 3 – Reconstruction of Laplacian Analytical Theory of Probabilities, A Tutorial in Data Science: Lecture 2 – The Hermeneutic Nature of Scientific Data. Schedule. \[2 \rightarrow 0 \qquad \qquad 4 \rightarrow 1 \qquad \qquad 6 \rightarrow 2 \qquad  \qquad 8 \rightarrow 3\qquad \mbox{    etc. 2nd number:  0.051023237.....           our number that we are creating 0.00 Then there exists some natural numbers x and y such that f(x)=f(y) but x≠y. $$0.a_{31}a_{32}a_{33}a_{34}a_{35} \ldots$$ Since we already found a bijection from ℤ to ℕ in the previous example, we will now find a bijection from A to ℕ. We write this as |A| = |B|. $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$, $$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$, Book: Combinatorics and Graph Theory (Guichard). To show that ℤ is countably infinite, we must find a bijection between ℕ and ℤ, i.e. In elementary set theory, Cantor's theorem is a fundamental result which states that, for any set, the set of all subsets of (the power set of , denoted by ()) has a strictly greater cardinality than itself. Exercise $$\PageIndex{1}\label{ex:invfcn-01}$$, Exercise $$\PageIndex{2}\label{ex:invfcn-02}$$, Exercise $$\PageIndex{3}\label{ex:invfcn-03}$$, Exercise $$\PageIndex{4}\label{ex:invfcn-04}$$, Exercise $$\PageIndex{5}\label{ex:invfcn-05}$$, Exercise $$\PageIndex{6}\label{ex:invfcn-06}$$, Exercise $$\PageIndex{8}\label{ex:invfcn-08}$$, Exercise $$\PageIndex{9}\label{ex:invfcn-09}$$, Exercise $$\PageIndex{10}\label{ex:invfcn-10}$$, Exercise $$\PageIndex{11}\label{ex:invfcn-11}$$, Exercise $$\PageIndex{12}\label{ex:invfcn-12}$$. The proof that a set cannot be mapped onto its power set is similar to the Russell paradox, named for Bertrand Russell.