This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

48
votes
2answers
11k views

Examples of bijective map from $\mathbb{R}^3\rightarrow \mathbb{R}$

Could any one give an example of a bijective map from $\mathbb{R}^3\rightarrow \mathbb{R}$? Thank you.
80
votes
5answers
14k views

How to define a bijection between $(0,1)$ and $(0,1]$?

How to define a bijection between $(0,1)$ and $(0,1]$? Or any other open and closed intervals? If the intervals are both open like $(-1,2)\text{ and }(-5,4)$ I do a cheap trick (don't know if ...
41
votes
7answers
15k views

Show that the set of all finite subsets of $\mathbb{N}$ is countable.

Show that the set of all finite subsets of $\mathbb{N}$ is countable. I'm not sure how to do this problem. I keep trying to think of an explicit formula for 1-1 correspondence like adding all the ...
93
votes
10answers
5k views

What Does it Really Mean to Have Different Kinds of Infinities?

Can someone explain to me how there can be different kinds of infinities? I was reading "The man who loved only numbers" by Paul Hoffman and came across the concept of countable and uncountable ...
17
votes
3answers
2k views

The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable

I'm examining a proof I have read that claims to show that the Cartesian product $\mathbb{N} \times \mathbb{N}$ is countable, and as part of this proof, I am looking to show that the given map is ...
9
votes
2answers
4k views

Cartesian Product of Two Countable Sets is Countable

How can I prove that the Cartesian product of two countable sets is also countable?
28
votes
6answers
11k views

Produce an explicit bijection between rationals and naturals?

I remember my professor in college challenging me with this question, which I failed to answer satisfactorily: I know there exists a bijection between the rational numbers and the natural numbers, but ...
48
votes
7answers
10k views

How does Cantor's diagonal argument work?

I'm having trouble understanding Cantor's diagonal argument. Specifically, I do not understand how it proves that something is "uncountable". My understanding of the argument is that it takes the ...
12
votes
5answers
2k views

Countable set having uncountably many infinite subsets

Can a countable set contain uncountably many infinite subsets such that the intersection of any two such distinct subsets is finite ?
24
votes
4answers
8k views

Overview of basic results about images and preimages

Are there some good overviews of basic facts about images and inverse images of sets under functions?
11
votes
4answers
4k views

Empty intersection and empty union

If $A_\alpha$ are subsets of a set $S$ then $\bigcup_{\alpha \in I}A_\alpha$ = "all $x \in S$ so that $x$ is in at least one $A_\alpha$" $\bigcap_{\alpha \in I} A_\alpha$ = "all $x \in S$ so that ...
5
votes
2answers
4k views

countably infinite union of countably infinite sets is countable

How do you prove that any collection of sets {$X_n : n \in \mathbb{N}$} such that for every $n \in \mathbb{N}$ the set $X_n$ is equinumerous to the set of natural numbers, then the union of all these ...
49
votes
8answers
4k views

Does mathematics become circular at the bottom? What is at the bottom of mathematics? [duplicate]

I am trying to understand what mathematics is really built up of. I thought mathematical logic was the foundation of everything. But from reading a book in mathematical logic, they use ...
29
votes
6answers
9k views

Cardinality of set of real continuous functions

The set of all $\mathbb{R\to R}$ continuous functions is $\mathfrak c$. How to show that? Is there any bijection between $\mathbb R^n$ and the set of continuous functions?
17
votes
2answers
5k views

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

Let $X$ be an infinite set of cardinality $|X|$, and let $S$ be the set of all finite subests of $X$. How can we show that Card($S$)$=|X|$? Can anyone help, please?
32
votes
5answers
21k views

Proof that the irrational numbers are uncountable

Can someone point me to a proof that the set of irrational numbers is uncountable? I know how to show that the set $\mathbb{Q}$ of rational numbers is countable, but how would you show that the ...
19
votes
2answers
1k views

How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers?

One of the basic (and frequently used) properties of cardinal exponentiation is that $(a^b)^c=a^{bc}$. What is the proof of this fact? As Arturo pointed out in his comment, in computer science this ...
16
votes
3answers
2k views

The Aleph numbers and infinity in calculus.

I have a fairly fundamental question. What is the difference between infinity as shown by the aleph numbers and the infinity we see in algebra and calculus? Are they interchangeable/transposable in ...
13
votes
3answers
5k views

Bijection between an open and a closed interval

Recently, I answered to this problem: Given $a<b\in \mathbb{R}$, find explicitly a bijection $f(x)$ from $]a,b[$ to $[a,b]$. using an "iterative construction" (see below the rule). My ...
34
votes
6answers
6k views

In set theory, how are real numbers represented as sets?

In set theory, if natural numbers are represented by nested sets that include the empty set, how are the rest of the real numbers represented as sets? Thanks for the answers. Several answers ...
3
votes
3answers
2k views

Infinite DeMorgan laws

Let $X$ be a set and $\{Y_\alpha\}$ is infinite system of some subsets of $X$. Is it true that: $$\bigcup_\alpha(X\setminus Y_\alpha)=X\setminus\bigcap_\alpha Y_\alpha,$$ $$\bigcap_\alpha(X\setminus ...
5
votes
2answers
3k views

An infinite subset of a countable set is countable

In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I ...
25
votes
3answers
4k views

Proof that the real numbers are countable: Help with why this is wrong

I was just thinking about this recently, and I thought of a possible bijection between the natural numbers and the real numbers. First, take the numbers between zero and one, exclusive. The ...
25
votes
4answers
909 views

Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?

I'm currently reading a little deeper into the Axiom of Choice, and I'm pleasantly surprised to find it makes the arithmetic of infinite cardinals seem easy. With AC follows the Absorption Law of ...
7
votes
3answers
1k views

Associativity of symmetric difference of sets

By $A\oplus B$ we denote the symmectric difference of two sets. The definition is $A\oplus B =(A\setminus B) \cup (B\setminus A)$. Now I hope to show that $A\oplus (B\oplus C) = (A\oplus B)\oplus C$. ...
46
votes
3answers
11k views

difference between class, set , family and collection

In school I have always seen sets. But I was watching a video the other day about functors and they started talking about any set being a collection but not vice-versa and I also heard people talking ...
32
votes
4answers
13k views

lim sup and lim inf of sequence of sets.

I was wondering if someone would be so kind to provide a very simple explanation of lim sup and lim inf of s sequence of sets. For a sequence of subsets $A_n$ of a set $X$, the $\limsup A_n= ...
29
votes
1answer
4k views

Overview of basic results on cardinal arithmetic

Are there some good overviews of basic formulas about addition, multiplication and exponentiation of cardinals (preferably available online)?
16
votes
7answers
2k views

Exactly half of the elements of $\mathcal{P}(A)$ are odd-sized

Let $A$ be a non-empty set and $n$ be the number of elements in $A$, i.e. $n:=|A|$. I know that the number of elements of the power set of $A$ is $2^n$, i.e. $|\mathcal{P}(A)|=2^n$. I came across ...
11
votes
5answers
643 views

Prove that every set with more than one element has a permutation without fixed points

I cannot prove this statement so need help. This problem is one of exercises right after the chapter about Hausdorff's maximal principle and Zorn's Lemma. Thus, you cannot use the concept of cardinal ...
9
votes
3answers
981 views

Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? [duplicate]

Possible Duplicate: What's the cardinality of all sequences with coefficients in an infinite set? Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? I thought I saw this ...
4
votes
3answers
934 views

Prove $f(S \cup T) = f(S) \cup f(T)$

$f(S \cup T) = f(S) \cup f(T)$ $f(S)$ encompasses all $x$ that is in $S$ $f(T)$ encompasses all $x$ that is in $T$ Thus the domain being the same, both the LHS and RHS map to the same $y$, since the ...
23
votes
3answers
7k views

How can an ordered pair be expressed as a set?

My book says \begin{equation} (a,b)=\{\{a\},\{a,b\}\} \end{equation} I have been staring at this for a bit and it is not making since to me. I have read several others posts on this, but none made ...
12
votes
3answers
7k views

Bijection from $\mathbb R$ to $\mathbb {R^N}$

How does one create an explicit bijection from the reals to the set of all sequences of reals? I know how to make a bijection from $\mathbb R$ to $\mathbb {R \times R}$. I have an idea but I am not ...
8
votes
3answers
3k views

Proving the Cantor Pairing Function Bijective

How would you prove the Cantor Pairing Function bijective? I only know how to prove a bijection by showing (1) If $f(x) = f(y)$, then $x=y$ and (2) There exists an $x$ such that $f(x) = y$ How would ...
18
votes
2answers
3k views

Every partial order can be extended to a linear ordering

How do I show that every partial order can be extended to a linear ordering? I think that I manage to prove that claim for finite set, how can I prove it for infinite set? Thank you.
8
votes
4answers
1k views

What's the cardinality of all sequences with coefficients in an infinite set?

My motivation for asking this question is that a classmate of mine asked me some kind of question that made me think of this one. I can't recall his exact question because he is kind of messy (both ...
6
votes
8answers
374 views

$x\in \{\{\{x\}\}\}$ or not?

I wonder if we can we say $x\in \{\{\{x\}\}\}$? In one viewpoint the only element of $\{\{\{x\}\}\}$ is $\{\{x\}\}$. In the other viewpoint $x$ is in $\{\{\{x\}\}\}$, for example all people in ...
19
votes
2answers
23k views

Is the power set of the natural numbers countable?

Some explanations: A set S is countable if there exists an injective function $f$ from $S$ to the natural numbers ($f:S \rightarrow \mathbb{N}$). $\{1,2,3,4\}, \mathbb{N},\mathbb{Z}, \mathbb{Q}$ are ...
19
votes
9answers
3k views

Why Are the Reals Uncountable?

Let us start by clarifying this a bit. I am aware of some proofs that irrationals/reals are uncountable. My issue comes by way of some properties of the reals. These issues can be summed up by the ...
10
votes
3answers
2k views

There exists an injection from $X$ to $Y$ if and only if there exists a surjection from $Y$ to $X$.

Theorem. Let $X$ and $Y$ be sets with $X$ nonempty. Then (P) there exists an injection $f:X\rightarrow Y$ if and only if (Q) there exists a surjection $g:Y\rightarrow X$. For the P $\implies$ Q part, ...
15
votes
5answers
2k views

Is $\{\emptyset\}$ a subset of $\{\{\emptyset\}\}$?

$\{\emptyset\}$ is a set containing the empty set. Is $\{\emptyset\}$ a subset of $\{\{\emptyset\}\}$? My hypothesis is yes by looking at the form of "the superset $\{\{\emptyset\}\}$" which contains ...
7
votes
3answers
6k views

Injective and Surjective Functions

Let $f$ and $g$ be functions such that $f\colon A\to B$ and $g\colon B\to C$. Prove or disprove the following a) If $g\circ f$ is injective, then $g$ is injective Here's my proof that this ...
4
votes
2answers
3k views

Non-existence of a Surjective Function from a Set to Its Subsets (Cantor's theorem)

Show that: Let A be a set and let $P(A)$ be the set of all subsets of $A$. Then there is no surjection $f: A→P(A)$. Here is what I thought: if $A=\{a,b\}$ then it has only two elements where ...
4
votes
1answer
286 views

sets of natural numbers [duplicate]

Possible Duplicate: Countable set having uncountably many infinite subsets Question: Is it possible to find uncountably many infinite sets of natural numbers that any two of these sets ...
3
votes
4answers
2k views

Proving $\mathbb{N}^k$ is countable

Prove that $\mathbb{N}^k$ is countable for every $k \in \mathbb{N}$. I am told that we can go about this inductively. Let $P(n)$ be the statement: “$\mathbb{N}^n$ is countable” $\forall n \in ...
36
votes
10answers
15k views

Is there a bijective map from $(0,1)$ to $\mathbb{R}$?

I couldn't find a bijective map from $(0,1)$ to $\mathbb{R}$. Is there any example?
22
votes
6answers
1k views

When does the set enter set theory?

I wonder about the foundations of set theory and my question can be stated in some related forms: If we base Zermelo–Fraenkel set theory on first order logic, does that mean first order logic is not ...
7
votes
3answers
1k views

How is $\epsilon_0$ countable?

In Wikipedia, it says that any epsilon number with the index that is countable is countable. How is it? Out of all those numbers, I especially want to know why $\epsilon_0$ is countable. Thanks.
11
votes
4answers
855 views

How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$?

When showing that $\mathbb{N}\times\mathbb{N}$ is in bijection with $\mathbb{N}$, it seems standard to give a proof by picture that shows a way to systematically weave through all the points in ...