What is Cardinality: Definition and 173 Discussions

In mathematics, the cardinality of a set is a measure of the "number of elements" of the set. For example, the set



A
=
{
2
,
4
,
6
}


{\displaystyle A=\{2,4,6\}}
contains 3 elements, and therefore



A


{\displaystyle A}
has a cardinality of 3. Beginning in the late 19th century, this concept was generalized to infinite sets, which allows one to distinguish between the different types of infinity, and to perform arithmetic on them. There are two approaches to cardinality: one which compares sets directly using bijections and injections, and another which uses cardinal numbers.
The cardinality of a set is also called its size, when no confusion with other notions of size is possible.
The cardinality of a set



A


{\displaystyle A}
is usually denoted




|

A

|



{\displaystyle |A|}
, with a vertical bar on each side; this is the same notation as absolute value, and the meaning depends on context. The cardinality of a set



A


{\displaystyle A}
may alternatively be denoted by



n
(
A
)


{\displaystyle n(A)}
,



A


{\displaystyle A}
,



card

(
A
)


{\displaystyle \operatorname {card} (A)}
, or



#
A


{\displaystyle \#A}
.

View More On Wikipedia.org
  1. R

    Combinatorics and set cardinality

    QUESTION: If A is a finite set, its cardinality, o(A), is the number of elements in A. Compute (a) o(A) when A is the set consisting of all five-digit integers, each digit of which is 1, 2, or 3. (b) o(B), where B = {x ∈ A : each of 1,2 and 3 is among the digits of x} and A...
  2. C

    I Cardinality of decreasing functions from N to N

    Problem: Find the cardinality of the set ## A = \{f \in \Bbb N \to \Bbb N. \forall n\leq m .f(n) \geq f (m) \} ##. I know that ## A \subseteq P(\Bbb N \times \Bbb N) ## implies ## |A| \leq |P(\Bbb N \times \Bbb N)| = | P(\Bbb N) | = \aleph ##. So I have a feeling that ## \aleph \leq |A| ##...
  3. H

    I A quick question regarding the application of Aleph numbers to reality

    Hi everyone, I have a quick question about Aleph numbers. Are they even possible? By containing infinity to a finite set, isn’t that essentially disproving the infinity in the first place? Can they be used in an actual scenario’s, or are they just purely hypothetical? Can they be used to...
  4. A

    I Add an exponential number of elements, what will be the final cardinality?

    Suppose we construct a set, adding at each step a polynomial number of elements. My impression that after we do countably infinite number of steps, the set will have countably infinite cardinality. But what happens if we add exponential number of elements each step? For instance, on step 0 we...
  5. Look

    MHB Understanding the Intersection of Inductive Sets & the Limits of λ Cardinality

    By ZFC, the minimal set satisfying the requirements of the axiom of infinity, is the intersection of all inductive sets. In case that the axiom of infinity is expressed as ∃I (Ø ∈ I ∧ ∀x (x ∈ I ⇒ x ⋃ {x} ∈ I)) the intersection of all inductive sets (let's call it K) is defined as set K = {x...
  6. Xavier Labouze

    I Cardinality of Unions of Powersets

    Mentor note: In this thread I (Mark44) have edited "cardinal" to "cardinality." In English, we talk about the "cardinality of a set," not the "cardinal of the set." Given A a set of n elements - note |A| its cardinal and P(A) its powerset. Let A1, A2... Ak, be k subsets (not empty) of A. What...
  7. S

    I Does the definition of cardinality assume distinguishability?

    Physics speaks of a set S of N "indistinguishable particles", giving the set S a cardinality but forbidding any equivalence relation that can distinguish between two particles. Is this terminology inconsistent with the mathematical definition of cardinality? Suppose ##S## is a set with...
  8. W

    I Cardinality of Theorems vs True Sentences in a Theory

    Given a Structure , is the Set of True Sentences (which I think is called the full theory generated by the Structure) with, say, countable symbols. Is there always a bijection between the true sentences (Semantic ) vs the Theorems (Syntactic)? I believe this depends on the existence of a model...
  9. Demystifier

    I Cardinality of non-measurable sets

    The interval ##[0,1]## of real numbers has a non-zero measure. The set of all rational numbers in the interval ##[0,1]## has zero measure. But there are also sets that are somewhere in between, in the sense that their measure is neither zero nor non-zero. They are sets for which measure is not...
  10. George Jones

    Synonyms "cardinality" with "carnality"?

    The PF spell-checker suggests replacing the mathematical term "cardinality" with "carnality". Are these terms synonymous? Hmm ... finite carnality ... infinite carnality ... different levels of infinite carnality ...
  11. nomadreid

    I Cardinality of a set of constant symbols (model theory)

    First, I want to be pedantic here and underline the distinction between a set (in the model, or interpretation) and a sentence (in the theory) which is fulfilled by that set, and also constant symbols (in the theory) versus constants (in the universe of the model) Given that, I would like to...
  12. A

    MHB Inequality of Cardinality of Sets

    I am working on a proof problem and I would love to know if my proof goes through: If $A, B$ are sets and if $A \subseteq B$, prove that $|A| \le |B|$. Proof: (a) By definition of subset or equal, if $x \in A$ then $x \in B$. However the converse statement if $x \in B$ then $x \in A$ is not...
  13. T

    Number of indie vectors ##\leq ## cardinality of spanning set

    Homework Statement In a finite-dimensional vector space, the length of every linearly independent list of vectors is less than or equal to the length of every spanning list. It's quite long :nb), hope you guys read through it. Thanks! :smile: Homework Equations N/A The Attempt at a Solution...
  14. T

    I Regarding cardinality and mapping between sets.

    why is not always true that if ##\vert A\vert\leq\vert B\vert## then there exist an injection from ##A## to ##B##?
  15. Jarvis323

    I Divisibility of bounded interval of reals

    Can (0,1)\subset\mathbb{R} be divided into an infinite set S of non-empty disjoint subsets? It seams like any pair of points in different subsets of the partitioning must have a finite difference, and so there must be some smallest finite difference overall, d where |S| \leq 1/d. Can someone...
  16. PsychonautQQ

    I Cardinality of fibers same for covering maps

    I'm having trouble following one part of a proof. Proposition: For any covering map ##p: X-->Y##, the cardinality of the fibers ##p^{-1}(q)## is the same for all fibers Proof: If U is any evenly coverd open set in ##X##, each component of ##p^{-1}(q)## contains exactly one point of each fiber...
  17. FallenApple

    I Countable or Uncountable Cardinality of Multiverse?

    In the MWI, are the number of universes in the multiverse countable or uncountable? It seems like if all possibilities happen, then that is like the power set, which has uncountable cardinality. Or maybe a Cantor diagonalization argument can be used on the discrete sequence of events over the...
  18. Mr Davis 97

    Proving Cardinality of P(S) > S

    Homework Statement Prove that the cardinality of ##P(S)## is greater than the cardinality of S, where S is any set. Homework EquationsThe Attempt at a Solution It would seem that we could simply define ##T: S \rightarrow P(S)## such that ##T(s) = \{s \}##. This is clearly an injection, so...
  19. Mr Davis 97

    Show Cardinality of Real Numbers and Complements

    Homework Statement ##\mathbb{R} \setminus C \sim \mathbb{R} \sim \mathbb{R} \cup C##. Homework EquationsThe Attempt at a Solution I have to show that all of these have the same cardinality. For ##\mathbb{R} \cup C \sim \mathbb{R}##, if ##C = \{c_1, c_2, ... c_n \}## is finite we can define ##...
  20. Mr Davis 97

    I [0,1] same cardinality as (0,1)

    To show that two sets have the same cardinality you have to show that there is a bijection between the two. Apparently, one bijection from [0,1] to (0,1) is ## f(x) = \left\{ \begin{array}{lr} 1/2 & : x = 0\\ \frac{1}{n+2} & : x = \frac{1}{n}\\ x & : \text{any other...
  21. jaketodd

    I Cardinality of the Power Series of an Infinite Set

    According to this page: https://en.wikipedia.org/wiki/Cantor's_theorem It says: "Cantor's theorem is a fundamental result that states that, for any set A, the set of all subsets of A (the power set of A) has a strictly greater cardinality than A itself." Furthermore, it says: "Cantor's...
  22. cyclogon

    B Cardinality and Natural Numbers

    Hi, I hoping someone might be kind enough to possibly tell me where I have made an error :) I'm more of a recreational maths person, lol - and I'm trying to make a scheme that 'maps' any decimal number to a natural one. The method I have come up with is a bit odd, I'm hoping it works but still...
  23. T

    I What is the required amount of information to specify an element in \omega_1?

    To select an element from countably infinite set (list set of integers) you need to provide finite amount of information. To specify an element in continuum in general case you have to provide infinite amount of information: any real number is specified as countable-infinite number of digits. So...
  24. M

    MHB Cardinality: Is the last sum correct?

    Hey! :o We have the set $A=\{a_1, a_2, \ldots \}$, the $a_i$'s might be finitely or infinitely many. We have that $\mathbb{Q}(A)=\left \{\frac{f(a_1, \ldots , a_n)}{g(a_1, \ldots , a_n)} : f,g\in \mathbb{Q}[x_1, \ldots , x_n], g\neq 0, a_1, \ldots , a_n\in A, n\in \mathbb{N}\right \}$. We...
  25. M

    I Proof that every basis has the same cardinality

    Hello all. I have a question concerning following proof, Lemma 1. http://planetmath.org/allbasesforavectorspacehavethesamecardinalitySo, we suppose that A and B are finite and then we construct a new basis ##B_1## for V by removing an element. So they choose ##a_1 \in A## and add it to...
  26. T

    I Cardinality of Universes in the Multiverse

    Is there a consensus on the cardinality of the infinite number of universes in the Multiverse? Is it countable or more than countable? Is it the same in different theories?
  27. PengKuan

    Cardinality of the set of binary-expressed real numbers

    Cardinality of the set of binary-expressed real numbers This article gives the cardinal number of the set of all binary numbers by counting its elements, analyses the consequences of the found value and discusses Cantor's diagonal argument, power set and the continuum hypothesis. 1. Counting...
  28. T

    Proof of |2^N x 2^N| = |2^N| with N the natural numbers

    Hello, At my exam I had to proof the title of this topic. I now know that it can easily be done by making a bijection between the two, but I still want to know why I didn't receive any points for my answer, or better stated, if there is still a way to proof the statement from my work. My work...
  29. O

    MHB Cardinality of Set A: 1 or $\le$1?

    Suppose that set A have unique element...Can we say that cardinality(A)=1 or $cardinality(A)\le1$ ? Which one is true ?
  30. Demystifier

    Application of sets with higher cardinality

    Sets with cardinality ##2^{\aleph_0}##, that is, with cardinality of the set of real numbers, obviously have many applications in other branches of mathematics outside of pure set theory. For example, real any complex analysis is completely based on such sets. How about higher cardinality? Is...
  31. evinda

    MHB Cardinality of continuous real functions

    Hi! (Wave) Find the cardinal number of $C(\mathbb{R}, \mathbb{R})$ of the continuous real functions of a real variable and show that $C(\mathbb{R}, \mathbb{R})$ is not equinumerous with the set $\mathbb{R}^{\mathbb{R}}$ of all the real functions of a real variable. That's what I have tried: We...
  32. evinda

    MHB Proving Cardinality of Sets: $\{a_n: n \in \omega\}$

    Hello! (Wave) Suppose that $X$ contains a countable set. Let $b \notin X$. Show that $X \sim X \cup \{b\}$. Prove that in general if $B$ is at most countable with $B \cap X=\varnothing$ then $X \sim X \cup B$. Proof:We will show that $X \sim X \cup \{b\}$. There is a $\{ a_n: n \in \omega \}...
  33. Stoney Pete

    Mary Tiles confused about infinite ordinals and cardinality?

    O.k. I am seriously confused... Not being to good at math but nevertheless interested in set theory, infinity, etc. I started reading Mary Tiles, The Philosophy of Set Theory (Dover edition). I particularly wanted to know more about the relation between infinite ordinals and cardinality, but...
  34. evinda

    MHB Proving the Same Cardinality of Sets A & B

    Hello! (Smile) If we want to show that the sets: $$A=\{ 3X^2| X \in \mathbb{Z}_p \}\ \ \text{ and } \ \ B=\{ 7-5Y^2| Y \in \mathbb{Z}_p\}$$ have the same cardinality, could we take the bijective function $f$ such that $f(x)=\frac{7-5x}{3}$ ? Or am I wrong? (Thinking)
  35. B

    MHB Proof related to the expected value of cardinality

    Consider N random variables X_{n} each following a Bernoulli distribution B(r_{n}) with 1 \geq r_{1} \geq r_{2} \geq ... \geq r_{N} \geq 0. If we make following assumptions of sets A and B: (1) A \subset I and B \subset I with I=\{1,2,3,...,N\} (2) |A \cap I_{1}| \geq |B \cap I_{1}| with...
  36. B

    MHB A question related to cardinality and probability

    Dear all, I have a question attached related to both probability and cardinality. Let me know if my formulation of the problem is non-rigorous or confusing. Any proof or suggestions are appreciated.Thank you all. The question follows.Consider a set \(I\) consists of \(N\) incidents...
  37. A

    In need of proof checking

    Hello everyone I was given a question in a homework (this is not a homework thread though as I have submitted it) is was to : Show that there is no infinite set A such that |A| < |Z+| =ℵ0. I thought of it and tried to work my way out and came up with those proofs , which I am not quiet sure...
  38. F

    MHB Cardinality of an interval as a limit

    Let $I$ be an interval and $A_{n}$ be the set of $k/n$ where $k$ is an integer. Prove that $|I|$ is the limit as $n$ tends to infinity of $\frac{1}{n}|(IA_{n})|$ where $IA_{n}$ denotes intersection. My plan was to split it up into cases for the different type of intervals and come up with...
  39. C

    MHB Cardinality, Subsets, Sequences

    Define F(A) = The set of all finite subsets of A Seq(A) = The set of all finite sequences with elements from A Let A be an infinite set (not necessarily countable). I want to prove the following lines. 1. Card seq(A) \le Card(A^\omega) 2. Card A = Card seq(A) = Card F(A)
  40. G

    Set whose cardinality is [itex]\aleph_2[/itex]?

    I know that we can easily construct a set whose cardinality is strictly greater than that of the set of real numbers by taking P(\Re) where P denotes the power-set operator. But as far as I am aware there aren't really any uses for this class of sets (up to bijection), or any intuitive ways of...
  41. C

    Finding Cardinality of Power Set

    Homework Statement Let S be the set of functions from a set A to {0,1} Prove that |P(A)|= |S| Homework Equations P(A) is the power set of A The Attempt at a Solution I have no idea how to do this... If A is finite then A has n elements, and we can write out the elements from one to...
  42. K

    Show F is Injective & Cardinality of Domain

    Homework Statement Let ## S = \{ (m,n) : m,n \in \mathbb{N} \} \\ ## a.) Show function ## f: S -> \mathbb{N} ## defined by ## f(m,n) = 2^m 3^n ## is injective b.) Use part a.) to show cardinality of S. The Attempt at a Solution a.) ## f(a,b) = f(c, d ) ; a,b,c,d \in \mathbb{N} \\\\ 2^a...
  43. K

    Prove Same Cardinality (1,3) and [1,4]

    Homework Statement Prove that the open interval (1,3) and the closed interval [1,4] have the same cardinality. Homework Equations The Attempt at a Solution I have to prove bijection. The injective part is obvious. Say, A =(1,3) and B =[1,4] f: A → B f(x) = x It's...
  44. G

    Finding the Cardinality of Set C: A Problem in Subsequence Coverage

    I have faced the following problem recently: We have a sequence A of M consecutive integers, beginning at A[1] = 1: 1,2,...M (example: M = 8 , A = 1,2,3,4,5,6,7,8 ) We have the set T consisting of all possible subsequences made from L_T consecutive terms of A, which do not overlap. (example...
  45. Y

    MHB Does cardinality of a set refer to the number of elements it has?

    Is cardnality of a set refers to the number of elements that set has?
  46. M

    MHB Calculating the Euler's Totient Function for a Given Integer

    Hey! :o I am looking at an exercise and I got stuck... $n\epsilon \mathbb{N},n>1$ $φ(n)=|\{1 \leq k \leq n :$ the greatest common divisor of $k$ and $n$ is $1\}|$ I am asked to find $φ(n)$,but I don't know how...
  47. B

    Cardinality of infinite subset of infinite set

    Am a bit confused about the meaning of cardinality. If ## A \subseteq B ##, then is it necessarily the case that ## |A| \leq |B| ##? I am thinking that since ## A \subseteq B ##, an injection from A to B exists, hence its cardinality cannot be greater than that of B? But this cannot be...
  48. B

    Gödel's Incompleteness TheoremsWhat is the limit of mathematical knowledge?

    Homework Statement Let K be any set and let F* be the set of all functions with domain K. Prove that card K < card F*.The Attempt at a Solution I am first able to show that card K <= card F*, by creating an invertible function from K into F*. let f: K -> F* be defined so that if k is an...
  49. 3

    Equivalence Relations, Cardinality and Finite Sets.

    Hey everyone, I have three problems that I'm working on that are review questions for my Math Final. Homework Statement First Question: Determine if R is an equivalence relation: R = {(x,y) \in Z x Z | x - y =5} and find the equivalence classes. Is Z | R a partition? Homework...
  50. K

    MHB Prove that the interval A = [0 , 2) has the same cardinality as the set B = [5 , 6) U [7 , 8)

    Prove that the interval A = [0 , 2) has the same cardinality as the set B = [5 , 6) U [7 , 8) by constructing a bijection between the two sets Attempt: x ↦ x + 5 for x ∈ [0 ; 1) x ↦ x + 6 for x ∈ [1 ; 2) What to do next?
Back
Top