This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

14
votes
2answers
3k 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.
36
votes
5answers
4k views

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

How do I 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 ...
13
votes
6answers
4k 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 ...
12
votes
3answers
965 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 ...
4
votes
2answers
1k views

Cartesian Product of Two Countable Sets is Countable

How can I prove that the Cartesian product of two countable sets is also countable?
29
votes
6answers
4k 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 ...
24
votes
6answers
3k 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 ...
27
votes
5answers
9k 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 ...
9
votes
1answer
3k 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?
17
votes
2answers
731 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 ...
15
votes
3answers
1k 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 ...
4
votes
2answers
2k 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 ...
8
votes
5answers
1k 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
3answers
4k 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 ...
20
votes
2answers
3k views

Cardinality of set of real continuous functions

The set of all ℝ → ℝ continuous functions is c. How to show that? Is there are bijection between ℝn and the set of continuous functions?
14
votes
8answers
2k 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 ...
4
votes
2answers
1k 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 ...
3
votes
3answers
351 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 ys, since the function ...
14
votes
2answers
3k 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 ...
10
votes
4answers
505 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 ...
8
votes
4answers
730 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
3answers
560 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 ...
9
votes
2answers
7k 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 ...
17
votes
1answer
646 views

Characterising functions $f$ that can be written as $f = g \circ g$?

I'd like to characterise the functions that ‘have square roots’ in the function composition sense. That is, can a given function $f$ be written as $f = g \circ g$ (where $\circ$ is function ...
7
votes
2answers
2k 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 ...
1
vote
3answers
1k 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 ...
16
votes
2answers
1k views

Infinite product of measurable spaces

Suppose there is a family (can be infinite) of measurable spaces. What are the usual ways to define a sigma algebra on their Cartesian product? There is one way in the context of defining product ...
19
votes
4answers
682 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 ...
10
votes
2answers
836 views

Subset of a finite set is finite

We define $A$ to be a finite set if there is a bijection between $A$ and a set of the form $\{0,\ldots,n-1\}$ for some $n\in\mathbb N$. How can we prove that a subset of a finite set is finite? It is ...
5
votes
3answers
600 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.
12
votes
10answers
2k views

Intuitive explanation for how could there be “more” irrational numbers than rational?

I've been told that the rational numbers from zero to one for a countable infinity, while the irrational ones form an uncountable infinity, which is in some sense "larger". But how could that be? ...
7
votes
3answers
614 views

Bijecting a countably infinite set $S$ and its cartesian product $S \times S$

From Herstein's Topics in Algebra (exercise 14, section 1.2): If $S$ is infinite and can be brought into one-to-one correspondence with the set of integers, prove that there is one-to-one ...
9
votes
3answers
2k 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 ...
-5
votes
3answers
134 views

Give an example of a function $f: \mathbb{N} \rightarrow \mathbb{N}$ with the property that there exists [closed]

Give an example of a function $f: \mathbb{N} \rightarrow \mathbb{N}$ with the property that there exists a function $g: \mathbb{N} \rightarrow \mathbb{N}$ such that the composition $g \circ f$ is the ...
15
votes
1answer
1k 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)?
11
votes
3answers
1k views

Preimage of generated $\sigma$-algebra

For some collection of sets $A$, let $\sigma(A)$ denote the $\sigma$-algebra generated by $A$. Let $C$ be some collection of subsets of a set $Y$, and let $f$ be a function from some set $X$ to $Y$. ...
8
votes
7answers
3k views

difference between maximal element and greatest element

I know that it's very elementary question but I still don't fully understand difference between maximal element and greatest element. If it's possible, please explain to me this difference with some ...
4
votes
3answers
287 views

Proving $f(C) \setminus f(D) \subseteq f(C \setminus D)$ and disproving equality

Let $f: A\longrightarrow B$ be a function. 1)Prove that for any two sets, $C,D\subseteq A$ , we have $f(C) \setminus f(D)\subseteq f(C\setminus D)$. 2)Give an example of a function $f$, and sets ...
4
votes
2answers
1k 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 ...
7
votes
4answers
319 views

Is this proof correct for : Does $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$?

Is this proof correct? To prove $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$. Let any number $y\in F(A)\cap F(B)$. We want to show $y\in F(A\cap B).$ Therefore, $y\in F(A)$ and ...
1
vote
2answers
356 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 ...
6
votes
3answers
574 views

How to prove cardinality equality ($\mathfrak c^\mathfrak c=2^\mathfrak c$)

How do I prove this cardinality equality:$\mathfrak c^\mathfrak c=2^\mathfrak c$ I have failed to prove this after lots of trail - but I am certain it's true How can I prove this?
5
votes
3answers
2k 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 ...
6
votes
2answers
427 views

How to show equinumerosity of the powerset of $A$ and the set of functions from $A$ to $\{0,1\}$ without cardinal arithmetic?

How to show equinumerosity of the powerset of $A$ and the set of functions from $A$ to $\{0,1\}$ without cardinal arithmetic? Not homework, practice exercise.
2
votes
4answers
911 views

Empty set does not belong to empty set

Herbert in his book "Elements of set theory" on page no 3 says that we can form the set $ \{ \emptyset \} $ whose only member is $\emptyset $. Note that $ \{ \emptyset \} \neq \emptyset $, ...
18
votes
10answers
5k views

Do infinity and zero really exist?

I'm not going to prove something, this is just a question. From the first day which I went to University until now I had some root problems in some basic mathematical assumptions and concepts. Please ...
23
votes
8answers
2k views

Why does the Dedekind Cut work well enough to define the Reals?

I am a seventeen year old high school student and I was studying some Real Analysis on my own. In the process, I encountered the Dedekind Cut being used to construct the Reals. I just can't get the ...
15
votes
1answer
627 views

Bijection between $\mathbb{R}$ and $\mathbb{R}/\mathbb{Q}$

I was wondering if it is possible to produce an explicit bijection $h\colon \mathbb{R} \rightarrow \mathbb{R}/\mathbb{Q}$. If we can produce an explicit injection $i\colon \mathbb{R} \rightarrow ...
11
votes
3answers
2k 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 ...
6
votes
1answer
365 views

First-order logic advantage over second-order logic

What is the advantage of using first-order logic over second-order logic? Second-order logic is more expressive and there is also a way to overcome Russell's paradox... So what makes first-order ...