Questions tagged [elementary-set-theory]

For elementary questions on set theory. Topics include intersections and unions, differences and complements, De Morgan's laws, Venn diagrams, relations and countability.

This tag is for elementary questions on set theory, focusing on material usually covered in undergraduate set theory texts. More advanced topics should use instead.

Topics include intersections and unions, De Morgan's laws, Venn diagrams, relations and countability.

29107 questions
224
votes
4 answers

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?
Martin Sleziak
  • 56,778
214
votes
22 answers

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

A 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 two answers: In both case it will take an infinite time. Skipping half of the number should be really faster.…
Thomas Ayoub
  • 1,645
  • 3
  • 12
  • 12
202
votes
9 answers

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 infinities, but they're only words to me. Any help…
Allain Lalonde
  • 2,147
195
votes
9 answers

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 that's how you're supposed to do it): I make a function…
user1411893
  • 2,173
174
votes
3 answers

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.
Banturam
  • 37,254
  • 28
  • 177
  • 354
162
votes
15 answers

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 the other two. One can construct each of these…
000
  • 5,808
153
votes
7 answers

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 $\limsup$ and $\liminf$ of a sequence of sets. For a sequence of subsets $A_n$ of a set $X$ we have $$\limsup A_n= \bigcap_{N=1}^\infty \left( \bigcup_{n\ge N} A_n…
Comic Book Guy
  • 5,938
137
votes
10 answers

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 can anyone produce an explicit formula for such…
Alex Basson
  • 4,421
117
votes
3 answers

What are the differences between class, set, family, and collection?

In school, I have always seen sets. I was watching a video the other day about functors, and they started talking about a set being a collection, but not vice-versa. I also heard people talking about classes. What is their relation? Some background…
Asinomás
  • 108,167
108
votes
8 answers

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 elements in each subset and sending that sum to…
user39794
107
votes
6 answers

Why isn't reflexivity redundant in the definition of equivalence relation?

An equivalence relation is defined by three properties: reflexivity, symmetry and transitivity. Doesn't symmetry and transitivity implies reflexivity? Consider the following argument. For any $a$ and $b$, $a R b$ implies $b R a$ by symmetry. Using…
Chao Xu
  • 6,006
107
votes
8 answers

Does mathematics become circular at the bottom? What is at the bottom of mathematics?

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 "="(equals-sign), functions and relations. Now is the "=" taken…
user119615
  • 10,702
  • 6
  • 51
  • 125
106
votes
7 answers

Cardinality of set of real continuous functions

I believe that the set of all $\mathbb{R\to R}$ continuous functions is $\mathfrak c$ , the cardinality of the continuum . However, I read in the book "Metric spaces" by Ó Searcóid that set of all $[0, 1]\to\mathbb{R}$ continuous functions is…
kennytm
  • 7,813
105
votes
5 answers

Prove that the set of all algebraic numbers is countable

A complex number $z$ is said to be algebraic if there are integers $a_0, ..., a_n$, not all zero, such that $a_0z^n+a_1z^{n-1}+...+a_{n-1}z+a_n=0$. Prove that the set of all algebraic numbers is countable. The Hint is: For every positive integer $N$…
PandaMan
  • 3,387
104
votes
12 answers

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?
ieb
  • 1,057
1
2 3
…
99 100