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

159
votes
24answers
32k views

Is it faster to count to the infinite going one by one or two by two? [closed]

A young child asked me this question yesterday: Would it be faster to count to the infinite going one by one or two by two? And I was split with these two answers: In both case it'll take an ...
74
votes
12answers
11k views

Are there real-life relations which are symmetric and reflexive but not transitive?

Inspired by Halmos (Naive Set Theory) . . . For each of these three possible properties [reflexivity, symmetry, and transitivity], find a relation that does not have that property but does have ...
59
votes
6answers
5k views

Why can't you pick socks using coin flips?

I'm teaching myself axiomatic set theory and I'm having some trouble getting my head around the axiom of choice. I (think I) understand what the axiom says, but I don't get why it is so 'contentious', ...
37
votes
5answers
5k 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 ...
32
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 ...
31
votes
7answers
1k views

Refuting the Anti-Cantor Cranks

I occasionally have the opportunity to argue with anti-Cantor cranks, people who for some reason or the other attack the validity of Cantor's diagonalization proof of the uncountability of the real ...
30
votes
6answers
3k views

Why can't a set have two elements of the same value?

Suppose I have two sets, $A$ and $B$: $$A = \{1, 2, 3, 4, 5\} \\ B = \{1, 1, 2, 3, 4\}$$ Set $A$ is valid, but set $B$ isn't because not all of its elements are unique. My question is, why can't ...
28
votes
5answers
10k 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 ...
26
votes
10answers
6k 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?
25
votes
6answers
4k 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 ...
25
votes
8answers
3k 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 ...
25
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 ...
25
votes
6answers
4k views

Difference between bijection and isomorphism?

First, let me admit that I suffer from a fundamental confusion here, and so I will likely say something wrong. No pretenses here, just looking for a good explanation. There is a theorem from linear ...
25
votes
2answers
1k views

Lamport claims there is an error in Kelley's proof of the Schroeder-Bernstein theorem. What is it?

In section 4.1 of his note How to write a proof, Leslie Lamport mentions an error in Kelley's exposition of the Schroeder-Bernstein theorem: Some twenty years ago, I decided to write a proof of ...
23
votes
6answers
4k 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?
22
votes
12answers
3k views

How is the set of all programs countable?

I'm having a hard time seeing how the number of programs is not uncountable, since for every real number, you can create a program that's prints out that number. Doesn't that immediately establish ...
20
votes
9answers
1k views

A simple example of an uncountable set that is not $\mathbb{R}$

Let's suppose that I have only defined $\mathbb{N}$ and then I define the terms finite and infinite set, and also countable and uncountable set. I can think of some examples of finite, infinite and ...
20
votes
5answers
682 views

What does it mean for a set to exist?

Is there a precise meaning of the word 'exist', what does it mean for a set to exist? And what does it mean for a set to 'not exist' ? And what is a set, what is the precise definition of a set?
20
votes
3answers
1k views

If the infinite cardinals aleph-null, aleph-two, etc. continue indefinitely, is there any meaning in the idea of aleph-aleph-null?

If the infinite cardinals aleph-null, aleph-two, etc. continue indefinitely, is there any meaning in the idea of aleph-aleph-null? Apologies if this isn't a sensible question, I really don't know too ...
20
votes
4answers
698 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 ...
19
votes
3answers
2k 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 ...
19
votes
5answers
3k views

What's wrong with this proof of the infinity of primes?

While reviewing an online textbook in abstract algebra for my website—which I'm hoping will go live by the end of the month—one of the exercises in the book inspired me to produce a simple, set ...
19
votes
4answers
400 views

“$f$ is a function from $A$ to $B$” vs. “$f $is a function from $A$ into $B$”?

When we say that $f$ is a function from $A$ to $B$ is this different from saying $f$ is a function from $A$ into $B$ I know what injective ("1-1"), surjective ("onto"), and bijective ...
18
votes
10answers
6k 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 ...
18
votes
10answers
2k views

Does there exist a system such that the additive identity is non-zero?

I am trying to explain how although the additive identity is written as $0$, it is not the same as the number $0$. For example for a $2\times 2$ matrix the additive identity is $\begin{pmatrix} 0 ...
18
votes
5answers
2k views

Why isn't the Cantor Set contradictory?

So you start with a 1-dimensional stick, remove the middle third of it, leaving 2 pieces. From each of these 2 pieces, remove the middle third. Etc. Whatever is left at the end of infinitely many ...
18
votes
7answers
2k views

There is no smallest infinity in calculus?

Somewhat of a basic question, but I tried mixing set theory and calculus and the result is a giant mess. From set theory (assume ZFC) we know there is a smallest infinite cardinal, $\aleph_0$, and ...
18
votes
2answers
2k views

Why Doesn't Cantor's Diagonal Argument Also Apply to Natural Numbers?

In my understanding of Cantor's diagonal argument, we start by representing each of a set of real numbers as an infinite bit string. My question is, why can't we begin by representing each natural ...
18
votes
4answers
3k views

Why is an image called an “image”?

Given a function $f : A \to B$, the image, denoted by $\operatorname{Im}f$ is the set of all $f(x)$ where $x \in A$. Why do we call this set the image? When was it first used, and what motivated its ...
18
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 ...
18
votes
1answer
655 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 ...
17
votes
2answers
4k 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.
17
votes
6answers
6k views

What are good books/other readings for elementary set theory?

I am looking to expand my knowledge on set theory (which is pretty poor right now -- basic understanding of sets, power sets, and different (infinite) cardinalities). Are there any books that come to ...
17
votes
2answers
799 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 ...
17
votes
3answers
1k views

What in Mathematics cannot be described within set theory? [duplicate]

I have begun reading Patrick Suppes' book Axiomatic Set Theory. The first sentence in chapter 1 reads: "Among the many branches of modern mathematics set theory occupies a unique place: with a few ...
17
votes
3answers
458 views

How do you pronounce the inverse of the $\in$ relation? How do you say $G\ni x$?

If I am talking about sets $G$ and $H$ and I want to say in words that $G\subset H$, I, like everyone else, will say that $G$ is contained in $H$, or that $H$ contains $G$. But if I am talking about ...
17
votes
4answers
812 views

Build $\mathbb{R}$ from $\mathcal{P}(\mathbb{N})$

It's well known that $\mathbb{R}$ has the same cardinality as $\mathcal{P}(\mathbb{N})$; but I would fain know if there is a way to construct $(\mathbb{R}, +,\cdot, \leq )$ using only definitions that ...
16
votes
7answers
5k 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 ...
15
votes
5answers
1k views

Importance of Axiom of Choice

First a quick question regarding the definition of the axiom of choice. Do the sets have to be mutually disjoint nonempty sets or just non-empty? One source states: "For any set X of nonempty sets, ...
15
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 ...
15
votes
3answers
730 views

Cantor set and countability.

The Cantor set is closed, so its complement is open. So the complement can be written as a countable union of disjoint open intervals. Why can we not just enumerate all endpoints of the countably ...
15
votes
4answers
3k views

Cardinality of the set of all real functions of real variable

How does one compute the cardinality of the set of functions $f:\mathbb{R} \to \mathbb{R}$ (not necessarily continuous)?
15
votes
5answers
1k views

Why study cardinals, ordinals and the like?

Why is the study of infinite cardinals, ordinals and the like so prevalent in set theory and logic? What's so interesting about infinite cardinals beyond $\aleph _0 $ and $\mathfrak{c} $? It seems ...
15
votes
4answers
4k views

Is there a bijection between $(0,1)$ and $\mathbb{R}$ that preserves rationality?

While reading about cardinality, I've seen a few examples of bijections from the open unit interval $(0,1)$ to $\mathbb{R}$, one example being the function defined by $f(x)=\tan\pi(2x-1)/2$. Another ...
15
votes
1answer
2k 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)?
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 ...
15
votes
1answer
697 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 ...
15
votes
1answer
311 views

Existence of an infinite set included in a circle with rational coordinates.

I am trying the following exercise: Let $\mathcal {C}$ the set of points of a circle with center $O$ and radius $1$ with rational coordinates. Show that there exists a infinite set $\mathcal{D} ...
14
votes
7answers
2k views

What are the ways of proving that the Cantor set is uncountable apart from Cantor diagonalization?

What are the ways of proving that the Cantor set is uncountable apart from Cantor diagonalization? Are there any based on dynamical systems?
14
votes
4answers
751 views

Set builder notation, left or right of :| convention

Set builder notation which specify a subset such as $Z$ or $R$ tend to put this condition on the left, whereas other conditions go on the right. $$\{ x ∈ Z : x > 0 \}$$ Why is this preferred ...