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. B

    Cardinality Proof (Set Theory)

    I'm trying to prove the following: if E is infinite set and F is finite set. prove that E and E U F have the same cardinality ? So what I did: I'm going to use Schroeder-Bernstein Thm. 1st, it's easy to show that |E| is less of equal to |E U F| since it is a subset of this latter. Now...
  2. D

    Can the Set of Rational Numbers Be Counted? And the Irrational Numbers?

    I need help with this math problem: Show that the set of rational numbers, Q, is countable. and Show that the set of irrational numbers is uncountable.
  3. S

    Cardinality Question from Basic Analysis. Thanks for any help.

    Homework Statement If the cardinality of A is less than or equal to the cardinality of the reals and the cardinality of B is less than or equal to the cardinality of the reals, I need to show that the cardinality of the union of A and B is less than or equal to the cardinality of the reals...
  4. A

    Cardinality of Sets Homework: Find Subsets of Natural Numbers

    Homework Statement The problems are to find the cardinality of several sets, a proof is not required, but there must be a decent argument. a) What is the cardinality of the set of all subsets of the natural numbers that contain up to 5 elements? b) What is the cardinality of the set of all...
  5. C

    Abstract algebra questions relating to Ideals and cardinality of factor rings

    Homework Statement Find the number of elements in the ring Z_5[x]/I, where I is a) the ideal generated by x^4+4, and b) where I is the ideal generated by x^4+4 and x^2+3x+1. Homework Equations Can't think of any. The Attempt at a Solution I started by finding the zeros of the...
  6. M

    Cardinality of Line Segment & Half Circumference: Bijection Established

    Homework Statement Do the following have the same cardinality? If so, establish a bijection and if not explain why. A line segment of 4 units and half of a circumference of radius 1 (including both endpoints). The attempt at a solution So my thought is that if I manipulate the...
  7. W

    Question about cardinality and CH

    Under the continuum hypothesis, we readily see that that |{a < \aleph_1 : \textrm{a is a cardinal}}| = \aleph_0 . What happens under the negation of CH? Is this equality still true or not? If the latter, always under the negation of CH, are there any infinite cardinals lambda for which the...
  8. mnb96

    Triangle inequaility for sets of same cardinality

    Hello, given a set \Omega, we consider all its subsets A_1,A_2,A_3,\ldots with same cardinality k. Do you have some hint in order to prove the following: \forall A_x,A_y,A_z\subseteq \Omega such that |A_x|=|A_y|=|A_z|=k |A_x-A_z| \leq |A_x-A_y|+ |A_y-A_z| Thanks
  9. F

    Cardinality of Natural even numbers and Natural numbers

    Is Card (N even)< Card (N)? Where N even is set of all even Natural numbers, N is set of all Natural numbers. Hint: use the mapping from N eve→Nn N even to N is given by n-->n a. Show examples of this mapping from N even N even to N. b. Is the mapping above onto? One-to-one? My try...
  10. J

    What are the cardinality problems in set theory and how can they be solved?

    I have been studying set theory, and come across a few problems that I have not been able to solve. I am trying to prove the bijections exist. Let N = Set of all natural numbers Let BA = Set of all functions from A to B 1) Prove |NN x NN| = |NN| 2) Prove |(NN)N| = |NN| Any explanation into...
  11. K

    Cardinality of an interval of rationals

    For any two rational numbers q1<q2, card ((q1,q2) cap Q) = card Q, right? How to prove it, if it's true?
  12. F

    Cardinality of the set of well-orderings on N

    Homework Statement How many different ways can one well-order the natural numbers? Different orders are those which are NOT order isomorphic.Homework Equations The Attempt at a Solution My approach thus far has been to examine a well-ordering on N. Clearly, any well-ordering is one that...
  13. D

    Intro Topology - Cardinality of a subset of N

    Homework Statement Every subset of \mathbb{N} is either finite or has the same cardinality as \mathbb{N} Homework Equations N/A The Attempt at a Solution Let A \subseteq \mathbb{N} and A not be finite. \mathbb{N} is countable, trivially, which means there is a bijective...
  14. A

    What is the Cardinality of Sets X, Y, and A, B, C?

    Hey guys, this is my first post, (Hi) was just wondering if i could get your help. I'm studying for my repeats and you guys can save me. If X = {1,2,3,4}, Y = {2,4,6} what is the cardinality of the following sets? (i) A = {x|x mod 2 = 0 and 0 <=x<=20} (ii) B = X * X * Y (iii) C = {(x,y)|x ≠ y...
  15. R

    Cardinality of a uncountable set.

    Homework Statement Let S be the set consisting of all sequences of 0's and 1's. S = {(a_1, a_2, a_3,...):a_n = 0 or 1 } Show that S is uncountable. Homework Equations The Attempt at a Solution I'm not sure where to start. I think I should either assume that S~N and use...
  16. J

    Cardinality of \mathbb{R}^{\mathbb{N}} - Is it \mathbb{R} or \{0,1\}?

    What's the cardinality of \mathbb{R}^{\mathbb{N}}? It must be \mathbb{R} or \{0,1\}^{\mathbb{R}}, but I'm not sure which.
  17. D

    Cardinality of sets: prove equality

    A=\mathbb{R}-0 (0,1)\subseteq \mathbb{R}-0 Assume A is countable. Since A is countable, then A\sim\mathbb{N}. Which follows that (0,1)\sim\mathbb{N}. However, (0,1) is uncountable so by contradiction, Card(A)=c Correct?
  18. C

    Cardinality Problem: Prove |A| < |N|

    Prove cardinality of every finite nonempty set A is less then cardinality of natural number N |A|<|N| set A is nonempty finite set natural number N is denumerable (infinite countable set) |A|<|N| if there exist a injective (one-to-one) function f: A->N, but NO bijective function, which...
  19. K

    Cardinality: |R\N| = |R\C| where C is countable

    If C is countable, then |N|=|C|, so there exists a bijection bewteen N and C, but does this imply that |R\N| = |R\C|? It is intutively believable, but I don't see how it rigorously follows. What is the bijection between R\N and R\C? Is it provable in general that If |A|=|C| and |B|=|D|...
  20. K

    Q3) Proving the Cardinality of Infinite Sets: A Rigorous Approach

    Homework Statement Q1) Assuming that |R|=|[0,1]| is true, how can we rigorously prove that |R2|=|[0,1] x [0,1]|? How to define the bijection? [Q1 is solved, please see Q2] Q2) Prove that |[0,1] x [0,1]| ≤ |[0,1]| Proof: Represent points in [0,1] x [0,1] as infinite decimals...
  21. K

    Cardinality of Transcendental Numbers

    Homework Statement Assuming the fact that the set of algebraic numbers is countable, prove that the set of transcendental numbers has the same cardinality R, the set of real numbers. Homework Equations N/A The Attempt at a Solution Let A be the set of algebraic numbers and T the set of...
  22. G

    Would the cardinality of a set S = {a, b, {c, d}} be 5?

    Would the cardinality of a set S = {a, b, {c, d}} be 5?
  23. T

    Cardinality of continuous functions

    Homework Statement What is the cardinality of the set of all continuous real valued functions [0,1] \rightarrow R . The Attempt at a Solution In words: I will be using the Cantor Bernstien theorem. First the above set, let's call it A, is lesser then or equal to the set of all...
  24. S

    Prove by Induction (Cardinality)

    If S1 and S2 are finite sets, show that |S1 x S2| = |S1||S2|. Here is what I've tried: Let |S1| = m and |S2| = n. Let P(k) be true. That is, P(k) = |S1 x S2| = km. P(1) is true since, if |S1| = 1 and |S2| = 1, |S1 x S2| = 1. Now, let |S1| = k+1 and |S2| = m. Then, P(k+1) = |S1 x...
  25. A

    Proving One-to-One Correspondence b/w (-1, 7) and R

    I need help proving this: Find an explicit one to one correspondence between the interval (-1;7) and the real numbers R Any ideas?
  26. M

    Cardinality of Real Numbers & Irrationals: Prove They're Equal

    Need help with this proof: Prove that the set of irrational numbers has the same cardinality as the set of real numbers.
  27. nomadreid

    Cardinality argument in the Casimir effect

    There is an argument to account for the Casimir effect based on cardinalities: that inside the two plates only (virtual) photons with wavelengths corresponding to the harmonic series can exist, hence countable infinity, whereas photons of all wavelengths can exist in the space around it, hence...
  28. B

    Constructing Structures with Cardinality W2: A Puzzle in Model Theory

    I was reading Hodges' Model Theory when I came across this question in the first chapter: Specify a structure of cardinality w2 which has a substructure of cardinality w but no substructure of cardinality w1. (Working in ZFC) I am assuming w2 means 2w1 but I'm not sure. I haven't really...
  29. C

    Analysis involving Cardinality of Infinite sets

    1. If X is an infinite set and x is in X, show that X ~ X \ {x} A~B if there exists a one-to-one function from A onto B. Attempt at a solution I'm pretty much completely stumped on this problem. I know that since X is infinite then it contains a sequence of distinct points. So...
  30. M

    Set theory and analysis: Cardinality of continuous functions from R to R

    Homework Statement Prove the set of continuous functions from R to R has the same cardinality as RHomework Equations We haven't done anything with cardinal numbers (and we won't), so my only tools are the definition of cardinality and the Schroeder-Bernstein theorem and its consequences. I...
  31. K

    Set theory cardinality question

    Can anyone please give a really explicit proof (omitting no steps) and with as simple words as possible that any infinite set can be writtern as the union of disjoint countable sets? Thank you.
  32. Phrak

    A set of cardinality Aleph^aleph

    A set of cardinality \aleph_0 has elements that are sets of size \aleph_0, and so on. Counting elements, I get \aleph_0 + \aleph_0^2 + ... + \aleph_0^{\aleph_0}\ . Is this the same size as \aleph_0 ?
  33. A

    Solving Union/Intersection Problem: 554 is Absurd!

    If I know: |A \cup B \cup C| = 1000 |A| = 344 |B| = 572 |C| = 296 |A \cap B| = 301 |B \cap C| = 252 |A \cap C| = 213 and I use the standard formula to compute |A \cap B \cap C|, I get 554, which is absurd. Can someone tell me what's wrong here? Is there something inconsistent in the initial...
  34. F

    Proving Even Cardinality of a Set w/o Inverse Elements in G

    Show that the Cardinality of a set which doesn't include inverse elements from a group G is always even. So the set with all g in G, which includes no inverse elements from G. (g=!g^-1) I can get this in every example I've done, checking mainly with dihedral groups, it's always been true but I...
  35. S

    Cardinality of Sets: N & Omega Explained

    The cardinality of set of [N]\omega . what does omega stands for?
  36. S

    Cardinality of [N]^ω: What Does ω Stand For?

    The cardinality of set of [N]^\omega . what does omega stands for?
  37. I

    What is the Cardinality of Multiple Cross Products?

    Since Tex is giving me a hard time this question is going to be a lot more undeveloped than it was going to be. We were discussing in class the cardinality of the Natural numbers being aleph null and that the cross product was also of cardinality aleph null. Is it true then that...
  38. I

    Counting Equivalence Relations on N

    Homework Statement Find the cardinality of the set of all equivalence relations on N Homework Equations by what we have learned yet we only have to determine if it's countable or not The Attempt at a Solution I know that the set of all relations on N is equivalent to P(NXN) thus is...
  39. M

    Show intervals of real numbers have the same cardinality

    Homework Statement Prove the intervals of real numbers (1,3) and (5,15) have the same cardinality by finding an appropriate bijective function of f:(1,3) ->(5,15) and verifying it is 1-1 and onto Homework Equations I know there are multiple ways to prove one to one and onto I am not sure...
  40. T

    Cardinality of set of real periodic functions

    what is the cardinality of a set A of real periodic functions ? f(x)=x is periodic so R is subset of A but not equal because sin(x) is in A but not in R. hence aleph_1<|A|.
  41. U

    How Can We Prove the Cardinality of Intervals in Real Numbers?

    Homework Statement Let a,b\in\Re such that a < b. Show |(a,b)|=|(0,1)| and Show |(0,1)|=|(0,\infty)| Homework Equations The Attempt at a Solution] I know that |(0,1)| is equal to the continuum and has the same cardinality as the reals. I would guess that |(0,\infty)| is also...
  42. J

    Why Is the Set of Real Numbers Larger Than the Set of Natural Numbers?

    I was reading about this topic of my own leisure, and I came across something that I couldn't quite understand. The solution of Galileo's Paradox is that the set of natural numbers and the set of perfect squares are both infinite sets of the same cardinality (namely aleph 0). This I can...
  43. E

    The cardinality of the set of all finite subsets of an infinite set

    How do I prove that the set of all finite subsets of an infinite set has the same cardinality as that infinite set?
  44. M

    Question about Cardinality - Is the Universe One-Dimensional?

    Something has been bothering me. I can't sleep, and neither can the little people inside my head. I'm not a mathematician, and I don't understand what I'm dealing with all that well, but I'm trying to figure out if the following makes sense: The cardinality of R^{1} is equal to the...
  45. sujoykroy

    Cardinality of Cartesian Product

    Can you prove the following theory of cardinality for a Cartesian product, - \left|\:A\:\right|\:\leq\:\left|\:A\:\times\:B\:\right|\: if\: B\neq\phi In English, The cardinality of a set A is less than or equal to the cardinality of Cartesian product of A and a non empty set B.
  46. M

    Do Infinite Sets K Have Equal Cardinalities for Permutations and All Functions?

    Is it true that the set of permutations on a infinite set K has the same cardinality as all functions between a infinite set K to itself?
  47. O

    Proving Cardinality Equality for Powersets of Infinite Sets

    Hi there, I'm having a lot of trouble understanding this particular problem, and I hope the fine people of this forum can help me out =) Homework Statement Let A and B be infinite sets with the same cardinality. Prove that P(A) and P(B) have the same cardinality. Do this by giving...
  48. K

    Cardinality of infinity (3)

    Homework Statement 1) Find the cardnality of the set of constructible angles whose cosine is a) irrational b) rational 2. The attempt at a solution For the other questions I have posted my attempt, but for this one I really have no clue... Could someone please give me some general...
  49. K

    How Is Cardinality of Infinite Sets Defined in Mathematics?

    I am still struggling with the topic of cardinality, it would be nice if someone could help: 1) http://www.geocities.com/asdfasdf23135/absmath2.jpg In the solutions , they said that{y=ax+b|a,b E R} <-> R2. But I am wondering...what is the actual mapping that gives one-to-one...
  50. K

    How Many Constructible Points Exist on the X-Axis?

    1) Consider the xy-plane. Find the cardinality of the set of constructible points on the x-axis. Attempt: Every constructible number is algebraic (i.e. Let A=set of algebraic numbers, C=set of constructible nubmers, then C is a subset of A) and A is countable. => |C|<|A|=|N|...
Back
Top