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

14k 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'...
11k 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.
15k 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 ...
5k 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 ...
4k views

### Cartesian Product of Two Countable Sets is Countable

How can I prove that the Cartesian product of two countable sets is also countable?
4k 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)...
8k 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?
4k views

1k 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 ...
1k 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 ...
915 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 ...
3k views

### Proving the Cantor Pairing Function Bijective

How would you prove the Cantor Pairing Function bijective? I only know how to prove a bijection by showing (1) If $f(x) = f(y)$, then $x=y$ and (2) There exists an $x$ such that $f(x) = y$ How would ...
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 ...
3k views

### An infinite subset of a countable set is countable

In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I ...
954 views

### Prove $f(S \cup T) = f(S) \cup f(T)$

$f(S \cup T) = f(S) \cup f(T)$ $f(S)$ encompasses all $x$ that is in $S$ $f(T)$ encompasses all $x$ that is in $T$ Thus the domain being the same, both the LHS and RHS map to the same $y$, since the ...
376 views

### $x\in \{\{\{x\}\}\}$ or not?

I wonder if we can we say $x\in \{\{\{x\}\}\}$? In one viewpoint the only element of $\{\{\{x\}\}\}$ is $\{\{x\}\}$. In the other viewpoint $x$ is in $\{\{\{x\}\}\}$, for example all people in ...
16k 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?
11k 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 ...
4k views

### Partition of N into infinite number of infinite disjoint sets? [duplicate]

Is it possible to have a countable infinite number of countable infinite sets such that no two sets share an element and their union is the positive integers?
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 ...
1k views

### Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? [duplicate]

Possible Duplicate: What's the cardinality of all sequences with coefficients in an infinite set? Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? I thought I saw this ...
4k views

Show that: Let A be a set and let $P(A)$ be the set of all subsets of $A$. Then there is no surjection $f: A→P(A)$. Here is what I thought: if $A=\{a,b\}$ then it has only two elements where $P(A)=\{... 1answer 4k 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)? 2answers 5k views ### The cardinality of the set of all finite subsets of an infinite set Let$X$be an infinite set of cardinality$|X|$, and let$S$be the set of all finite subests of$X$. How can we show that Card($S$)$=|X|$? Can anyone help, please? 2answers 24k 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 ... 3answers 7k views ### Bijection from$\mathbb R$to$\mathbb {R^N}$How does one create an explicit bijection from the reals to the set of all sequences of reals? I know how to make a bijection from$\mathbb R$to$\mathbb {R \times R}$. I have an idea but I am not ... 2answers 3k views ### Every partial order can be extended to a linear ordering How do I show that every partial order can be extended to a linear ordering? I think that I manage to prove that claim for finite set, how can I prove it for infinite set? Thank you. 3answers 6k views ### Injective and Surjective Functions Let$f$and$g$be functions such that$f\colon A\to B$and$g\colon B\to C$. Prove or disprove the following a) If$g\circ f$is injective, then$g$is injective Here's my proof that this is ... 2answers 760 views ### How to show equinumerosity of the powerset of$A$and the set of functions from$A$to$\{0,1\}$without cardinal arithmetic? How to show equinumerosity of the powerset of$A$and the set of functions from$A$to$\{0,1\}$without cardinal arithmetic? Not homework, practice exercise. 3answers 3k views ### Surjectivity of Composition of Surjective Functions Suppose we have two functions,$f:X\rightarrow Y$and$g:Y\rightarrow Z$. If both of these functions are onto, how can we show that$g\circ f:X\rightarrow Z$is also onto? 7answers 10k 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 ... 1answer 832 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 ... 3answers 2k views ### There exists an injection from$X$to$Y$if and only if there exists a surjection from$Y$to$X$. Theorem. Let$X$and$Y$be sets with$X$nonempty. Then (P) there exists an injection$f:X\rightarrow Y$if and only if (Q) there exists a surjection$g:Y\rightarrow X$. For the P$\implies$Q part, ... 6answers 1k views ### The simplest way of proving that$|\mathcal{P}(\mathbb{N})| = |\mathbb{R}| = c\$

What is the simplest way of proving (to a non-mathematician) that the power set of the set of natural numbers has the same cardinality as the set of the real numbers, i.e. how to construct a bijection ...