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, (un)...

learn more… | top users | synonyms

16
votes
3answers
2k views

Construct a bijection from $\mathbb{R}$ to $\mathbb{R}\setminus S$, where $S$ is countable

Two questions: Find a bijective function from $(0,1)$ to $[0,1]$. I haven't found the solution to this since I saw it a few days ago. It strikes me as odd--mapping a open set into a closed set. $S$ ...
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 ...
16
votes
1answer
934 views

Constructing a bijection from (0,1) to the irrationals in (0,1)

How does one construct a bijection from (0,1) to the irrationals in (0,1)? Or if I am getting my notation right, can you provide an explicit function $f:(0,1)\rightarrow(0,1)\backslash\mathbb{Q}$ ...
16
votes
1answer
733 views

Any branch of math can be expressed within set theory, is the reverse true?

Set theory seems to have the property of being "universal", in the sense that any branch of math can be expressed on its language. Is there any other branch of math with this property? I am asking ...
16
votes
1answer
378 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} \...
16
votes
3answers
270 views

Generalization of $f(\overline{S}) \subset \overline{f(S)} \iff f$ continuous

A common characterization of a continuous function $f: X \to Y$ is that for any $S \subset X$, $f(\overline{S}) \subset \overline{f(S)}$. Similarly, closed maps are such that $f(\overline{S}) \supset \...
16
votes
1answer
203 views

There's no cardinal $\kappa$ such that $2^\kappa = \aleph_0$

I am trying to prove that there is no cardinal $\kappa$ such that $2^\kappa = \aleph_0$ . My attempt: We suppose it exists. Since $\kappa<2^\kappa$, in particular, $\kappa<\aleph_0$. But ...
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 ...
15
votes
8answers
2k views

Can we have a one-one function from [0,1] to the set of irrational numbers?

Since both of them are uncountable sets, we should be able to construct such a map. Am I correct? If so, then what is the map?
15
votes
9answers
14k 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. ...
15
votes
4answers
1k 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 over,...
15
votes
5answers
2k views

Why König's lemma isn't “obvious”?

I keep facing König's lemma "Every finitely branching infinite tree over $\mathbb{N}$ has infinite branch". Why it is not taken "obvious" but needs a careful proof? It seems somewhat obvious, but I ...
15
votes
5answers
2k views

How many non-increasing sequences are there over the natural numbers?

How many non-increasing sequences are there over the natural numbers? By splitting it to categories, I sort of got it has to be $\aleph_0$. Nevertheless, I haven't seen such a question and therefore I ...
15
votes
2answers
2k views

Axiom of Choice Examples

In the wikipedia article, two examples are given which use/ do not use the axiom of choice. They are: Given an infinite pair of socks, one needs AC to pick one sock out of each pair. Given an ...
15
votes
4answers
3k views

An Intuition to An Inclusion: “Union of Intersections” vs “Intersection of Unions”

Let $E = \{E_k\}_{k \in \mathbb{N}}$ be an infinite sequence of sets. Then, the following inclusion holds: $\bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} E_k \quad\subseteq\quad \bigcap_{n=1}^{\infty}...
15
votes
2answers
10k 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 ...
14
votes
7answers
5k 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
3answers
1k views

What is an example of two sets which cannot be compared?

In set theory, if we do not assume the Axiom of Choice, we cannot prove the Trichotomy Law between cardinals. That is, we cannot prove that for any two sets, there exists an injection from one to the ...
14
votes
4answers
619 views

Uncountability of increasing functions on N

I believe I have made a reasonable attempt to answer the following question. I would like a confirmation of my proof to be correct, or help as to why it is incorrect. Question: Let $f : \mathbb{N} \...
14
votes
3answers
1k views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
14
votes
5answers
8k views

Example of set which contains itself

I am trying to understand Russells's paradox How can a set contain itself? Can you show example of set which is not a set of all sets and it contains itself.
14
votes
3answers
2k views

How do the sets $\emptyset\times B,\ A\ \times \emptyset, \ \emptyset \times \emptyset $ look like?

If we have a function $f:A \rightarrow B$, then one way to give meaning, I think, to this function, in terms of set theory, is to say, that $f$ is actually a binary relation $f=(A,B,G_f)$, where $G_f \...
14
votes
1answer
437 views

What is wrong with ZFC?

Why are there seemingly so many who want to use ETCS, or HoTT, or similar as a foundation of mathematics? I'm aware that HoTT has a good few good aspects, but that doesn't entirely explain the strong ...
13
votes
8answers
3k views

Why do we accept Kuratowski's definition of ordered pairs?

I've been struggling understanding Kuratowski's definition of ordered pairs. I understand what it means but I don't see why I should accept it. I've seen this question and this one, most importantly --...
13
votes
3answers
3k views

Why is an empty function considered a function?

A function by definition is a set of ordered pairs, and also according the Kuratowski, an ordered pair $(x,y)$ is defined to be $$\{\{x\}, \{x,y\}\}.$$ Given $A\neq \varnothing$, and $\varnothing\...
13
votes
4answers
1k views

Set builder notation: Colon or Vertical Line

I remember once hearing offhandedly that in set builder notation, there was a difference between using a colon versus a vertical line, e.g. $\{x: x \in A\}$ as opposed to $\{x\mid x \in A\}$. I've ...
13
votes
3answers
895 views

What does “closed under …” mean?

What exactly is meant by "closed under fill in the blank"? Thanks.
13
votes
7answers
437 views

Why does $\bigcup_{X \in \mathscr{P}(\mathbb{N})}X = \mathbb{N}$, instead of $\mathscr{P}(\mathbb{N})?$

This is a practice problem I just came across, $$\bigcup_{X \in \mathscr{P}(\mathbb{N})}X =$$ I came up with $\mathscr{P}(\mathbb{N})$, but the book lists $\mathbb{N}$ as the solution. I would've ...
13
votes
2answers
827 views

Why doesn't this definition of natural numbers hold up in axiomatic set theory?

I was reading about older definitions of the natural numbers on Wikipedia here (in retrospect, not the best place to learn mathematics) and came across the following definition for the natural numbers:...
13
votes
4answers
1k views

Is Cantor's diagonal argument dependent on the base used?

Applying Cantor's diagonal argument to irrational numbers represented in binary, one and only one irrational number can be generated that is not on the list. Wikipedia image: But if you change ...
13
votes
4answers
2k views

Proving a set in $\mathbb{Q}$ that is bounded above to have no largest number (greatest element)

I'm studying the set $Q$. At this point I don't know the real numbers. This is the theorem: Let $A$ be the set such that $A=\{p\in \mathbb{Q}^{+}:p^{2}<2\}$. Then $A$ contains no largest ...
13
votes
2answers
1k views

If A is infinite, does there have to exist a subset of A that is equivalent to A?

I was reading Rudin and there is an alternative definition of infinite set (the first definition is "not finite"): A is infinite if it is equivalent to one of its subset. Then I was wondering the ...
13
votes
6answers
2k views

A strange puzzle having two possible solutions

A friend of mine asked me the following question: Suppose you have a basket in which there is a coin. The coin is marked with the number one. At noon less one minute, someone takes the coin ...
13
votes
4answers
2k views

Formal proof for A subset of the real numbers, well ordered with the normal order of $\mathbb R$, is at most $\aleph_0$

I tried to write a formal proof for the theorem: $A$ subset of $\mathbb R$ well ordered by the normal order $\implies A$ is at most of cardinality $\aleph_0$. Any suggestions? Thanks.
13
votes
3answers
2k views

Showing any countable, dense, linear ordering is isomorphic to a subset of $\mathbb{Q}$

I'm trying to knock out a few of the later exercises from Enderton's Elements of Set Theory. This problem is #17, found on page 227. A partial ordering $R$ is said to be dense iff whenever $xRz$, ...
13
votes
1answer
973 views

Do Cantor's Theorem and the Schroder-Bernstein Theorem Contradict?

I am confused as to how Cantor's Theorem and the Schroder-Bernstein Theorem interact. I think I understand the proofs for both theorems, and I agree with both of them. My problem is that I think you ...
13
votes
4answers
348 views

What explains the asymmetry here?

The image operation distributes over unions: $$f(A \cup B) = f(A) \cup f(B)$$ but about intersections we can only say that $$f(A \cap B) \subseteq f(A) \cap f(B)$$ unless $f$ is injective. Where ...
13
votes
3answers
4k views

Need help with Recursion Theorem (Set Theory)

The recursion theorem In set theory, this is a theorem guaranteeing that recursively defined functions exist. Given a set $X$, an element $a$ of $X$ and a function $f\colon X \to X$, the theorem ...
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 ...
13
votes
3answers
2k views

Proving the countability of algebraic numbers

I am trying to prove that algebraic numbers are countably infinite, and I have a hint to use: after fixing the degree of the polynomial, consider summing the absolute values of its integer ...
13
votes
1answer
225 views

What does it mean for a set to have “structure”?

I understand that a set is like a list of things, except that the order doesn't matter and that you can't have any duplicates in a set. For example: $\{3, 1, 4, 2\}$ is the same set as $\{1, 2, 3, 4\}$...
12
votes
8answers
1k views

Does $\bigcap_{n=1}^{+\infty}(-\frac{1}{n},\frac{1}{n}) = \varnothing$?

When I learn the below theorem: If $I_n$ is closed interval, and $I_{n+1} \subset I_n$, then $$\bigcap I_n \ne \varnothing$$ and someone says if we replace closed interval with open interval, can ...
12
votes
4answers
2k views

How large is the set of all Turing machines?

How large is the set of all Turing machines? I am confident it is infinitely large, but what kind of infinitely large is its size?
12
votes
5answers
1k views

$A \in B$ vs. $A \subset B$ for proofs

I have to prove a few different statements. The first is if $A \subset B$ and $B \subset C$ then prove $A \subset C$. This one is fairly straight forward, but I'm stuck on how the next one differs. ...
12
votes
5answers
671 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 ...
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 ?
12
votes
4answers
554 views

What is $\bigcup\limits_{n=1}^\infty [0,1-\frac{1}{n}]$?

This is probably a pretty dumb question, but I am confused by set theory again. The question is whether $$\bigcup_{n=1}^\infty \left[0,1-\frac{1}{n}\right]$$ equals $[0,1]$ or $[0,1)$. However, I am ...
12
votes
6answers
594 views

subset of binary space countable?

I know that the set of all binary sequences is uncountable. Now consider the subset of this set, that whenever a digit is $1$, its next digit must be $0$. Is this set countable? I think it is not ...
12
votes
3answers
507 views

Is every set a subset?

Is every set a subset of a larger set? In other words, for an arbitrary set S, can one always construct a set S' such that S is a proper subset of S'? Is this question even meaningful?
12
votes
4answers
814 views

I want to know why $\omega \neq \omega+1$.

In Kunen's book, Set Theory,chapter I.7, he said: $1+\omega=\omega \neq \omega+1$. I want to know why $\omega \neq \omega+1$.