# Tagged Questions

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)...

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$ ...
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 ...
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}$ ...
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 ...
378 views

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 ...
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 ...
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?
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. ...
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,...
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 ...
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 ...
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 ...
3k views

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 ...
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.
2k views

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 ...
895 views

### What does “closed under …” mean?

What exactly is meant by "closed under fill in the blank"? Thanks.
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 ...
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:...
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 ...
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 ...
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 ...
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 ...
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.
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$, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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\}$...
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 ...
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?
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. ...
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 ...
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 ?
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 ...
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 ...
### 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$.