Questions tagged [elementary-set-theory]

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, differences and complements, De Morgan's laws, Venn diagrams, relations, etc. More advanced topics should use (set-theory) instead.

Filter by
Sorted by
Tagged with
203
votes
22answers
36k views

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

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. ...
151
votes
9answers
8k 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 ...
144
votes
8answers
35k 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 that'...
132
votes
15answers
38k 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 the ...
112
votes
2answers
26k views

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

Could any one give an example of a bijective map from $\mathbb{R}^3\rightarrow \mathbb{R}$? Thank you.
95
votes
4answers
30k 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?
80
votes
4answers
4k views

How do we know that Cantor's diagonalization isn't creating a different decimal of the same number?

Edit: As the comments mention, I misunderstood how to use the diagonalization method. However, the issue I'm trying to understand is a potential problem with diagonalization and it is addressed in the ...
77
votes
3answers
21k views

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 ...
73
votes
6answers
6k 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', ...
72
votes
11answers
11k views

Infinite sets don't exist!?

Has anyone read this article? This accomplished mathematician gives his opinion on why he doesn't think infinite sets exist, and claims that axioms are nonsense. I don't disagree with his arguments, ...
71
votes
6answers
38k 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= \bigcap_{...
68
votes
7answers
36k 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 ...
67
votes
6answers
20k 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 ...
65
votes
8answers
7k 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 "="(equals-sign)...
64
votes
6answers
34k 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 ...
63
votes
6answers
14k views

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$ ...
62
votes
8answers
11k views

Is “The empty set is a subset of any set” a convention?

Recently I learned that for any set A, we have $\varnothing\subset A$. I found some explanation of why it holds. $\varnothing\subset A$ means "for every object $x$, if $x$ belongs to the empty set,...
59
votes
10answers
46k 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?
56
votes
1answer
10k 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)?
55
votes
9answers
4k 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 ...
55
votes
2answers
3k views

What does it take to divide by $2$?

Theorem 1 [ZFC, classical logic]: If $A,B$ are sets such that $\textbf{2}\times A\cong \textbf{2}\times B$, then $A\cong B$. That's because the axiom of choice allows for the definition of ...
54
votes
7answers
23k 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?
52
votes
5answers
44k 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 ...
52
votes
3answers
33k views

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 ...
51
votes
8answers
67k views

What is the proof that the total number of subsets of a set is $2^n$?

What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).
47
votes
10answers
7k views

Why are integers subset of reals?

In most programming languages, integer and real (or float, rational, whatever) types are usually disjoint; 2 is not the same as 2.0 (although most languages do an automatic conversion when necessary). ...
47
votes
7answers
6k views

How did early mathematicians make it without Set theory?

It is said that Cauchy was a pioneer of rigour in calculus and a founder of complex analysis. Yet if baffles me as set theory was an invention of the 1870s, 20 years after the death of Cauchy. ...
47
votes
5answers
15k 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 ...
46
votes
9answers
24k 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 ...
45
votes
8answers
45k views

Example of Partial Order that's not a Total Order and why?

I'm looking for a simple example of a partial order which is not a total order so that I can grasp the concept and the difference between the two. An explanation of why the example is a partial ...
45
votes
2answers
5k views

Is the axiom of choice really all that important?

According to this book: The Axiom of Choice is the most controversial axiom in the entire history of mathematics. Yet it remains a crucial assumption not only in set theory but equally in modern ...
44
votes
7answers
12k 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 ...
43
votes
6answers
34k 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 ...
42
votes
9answers
7k views

Correct set notation for “all integers which are not multiples of 7”?

What is correct set notation for "all integers which are not multiples of $7$"? My best guess is: $$ \{ x : (\forall k \in \mathbb{Z})(\neg(7k = x)) \}$$ Or $$ \{ x : \neg(\exists k \in \mathbb{Z})(...
40
votes
7answers
23k 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 ...
40
votes
4answers
15k 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)?
39
votes
8answers
4k views

Is symmetric group on natural numbers countable?

I guess it is too difficult a question to ask about the cardinality of $S_{\mathbb{N}}$ so I would like to ask whether it is countable or not. I tried to prove it is uncountable somewhat mimicking ...
39
votes
7answers
7k views

Can you have negative sets?

I figure that since you can, of course, have members in a set, have only a single member in a set, and then have no members in a set, it seems not then a big step forward (or backwards depending how ...
39
votes
6answers
16k views

How can a set contain itself?

In Russell's famous paradox ("Does the set of all sets which do not contain themselves contain itself?") he obviously makes the assumption that a set can contain itself. I do not understand how this ...
38
votes
7answers
55k views

Prove that the union of countably many countable sets is countable.

I am doing some homework exercises and stumbled upon this question. I don't know where to start. Prove that the union of countably many countable sets is countable. Just reading it confuses me. ...
38
votes
5answers
4k views

Is there a simple, constructive, 1-1 mapping between the reals and the irrationals?

Is there a simple, constructive, 1-1 mapping between the reals and the irrationals? I know that the Cantor–Bernstein–Schroeder theorem implies the existence of a 1-1 mapping between the reals and the ...
38
votes
3answers
61k 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 ...
37
votes
5answers
3k views

Is it possible to define countability without referring the natural numbers?

Cantor defined countable sets as A set is countable if there exists an injective function from the set to the set of natural numbers. Still today countability is almost always defined in Cantor's ...
37
votes
6answers
32k views

Create unique number from 2 numbers

is there some way to create unique number from 2 positive integer numbers? Result must be unique even for these pairs: 2 and 30, 1 and 15, 4 and 60. In general, if I take 2 random numbers result must ...
37
votes
6answers
3k 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 ...
36
votes
12answers
6k views

Is this a valid proof that there are infinitely many natural numbers?

I remember reading a simple proof that natural numbers are infinite which goes like the following: Let $ℕ$ be the set of natural numbers. Assume that $ℕ$ is finite. Now consider an arbitrary number $...
36
votes
8answers
8k 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 ...
35
votes
2answers
8k 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 ...
34
votes
1answer
1k views

Rudin's Principle of Mathematical Analysis Theorem 2.14 Question

$\mathbf{Theorem 2.14:}$ Let $A$ be the set of all sequences whose elements are the digits $0$ and $1$. Then A is uncountable, meaning there does not exist a one-to-one mapping of A onto $\mathbb{Z}$. ...
33
votes
9answers
3k views

Why do we say ‘pairwise disjoint’, rather than ‘disjoint’?

I don’t see the ambiguity that ‘pairwise’ resolves. Surely if $A$, $B$ and $C$ are disjoint sets then they are pairwise disjoint and vice versa? Or am I being dim?