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

learn more… | top users | synonyms

10
votes
4answers
905 views

Difference between a function and a graph of a function?

Formally, I learned that a function $f: X \to Y$ is a subset $f \subset X \times Y$ subject to the condition that for every $x \in X$, there is exactly one $y \in Y$ such that $(x, y) \in f$. We write ...
10
votes
3answers
3k 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 ...
10
votes
5answers
797 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 ...
10
votes
2answers
1k views

Subset of a finite set is finite

We define $A$ to be a finite set if there is a bijection between $A$ and a set of the form $\{0,\ldots,n-1\}$ for some $n\in\mathbb N$. How can we prove that a subset of a finite set is finite? It is ...
10
votes
2answers
174 views

Bolzano-Weierstrass for sequences of sets

Let $\mathcal{A}_n,\,n\in\mathbb{N}$ be a sequence of subsets of, say, $\mathbb{R}$. Let $\limsup_{n\rightarrow\infty} \mathcal{A}_n = \{x:x\in\mathcal{A}_n\mbox{ for infinitely many } n\}$, and ...
10
votes
4answers
626 views

How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$?

When showing that $\mathbb{N}\times\mathbb{N}$ is in bijection with $\mathbb{N}$, it seems standard to give a proof by picture that shows a way to systematically weave through all the points in ...
10
votes
1answer
90 views

a totally ordered set with small well ordered set has to be small?

doing something quite different the following question came to me: 1)If you have a totally ordered set A such that all the well ordered subset are at most countable, is it true that A has at most the ...
10
votes
6answers
247 views

what is a function? please.

Axiom schema of replacement: Let the domain of the function $F$ be the set $A$. Then the range of $F$ (the values of $F(x)$ for all members $x$ of $A$) is also a set. — Tarski–Grothendieck ...
10
votes
0answers
127 views

Analogue of the term 'summand' for unions and intersections.

If we have a sum $\sum\limits_{i=1}^na_i$, we call the terms $a_i$ summands. In fact, in the cases of addition, subtraction, multiplication, and division, we have a large vocabulary to describe the ...
9
votes
14answers
2k views

Using set notation, define the set of even natural numbers between 100 and 500.

Using set notation, define the set of even natural numbers between 100 and 500. This is what I have so far: $P$ is even numbers so the set of natural numbers between 100 and 500 would be $$P = ...
9
votes
5answers
928 views

Contradictory definition in set theory book?

I'm using a book that defines $A\setminus B$ (apparently this is also written as $A-B$) as $\{x\mid x\in A,x\not\in B\}$, but then there was an exercise that asked to find $A\setminus A$. Wouldn't it ...
9
votes
8answers
3k views

What is larger — the set of all positive even numbers, or the set of all positive integers?

We will call the set of all positive even numbers E and the set of all positive integers N. At first glance, it seems obvious ...
9
votes
5answers
1k 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 ?
9
votes
3answers
725 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 ...
9
votes
4answers
218 views

$\bigcup \emptyset$ is defined but $\bigcap \emptyset$ is not. Why?

Why does $\bigcup \emptyset = \emptyset$ but $\bigcap \emptyset$ is not defined? If I had to guess, I'd say it's also equal to $\emptyset$.
9
votes
5answers
600 views

If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$? [duplicate]

Prove, disprove, or give a counterexample: If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$. Assume $\mathcal{P}(A)=\mathcal{P}(B)$. Since we know $A \subseteq A$, we know $A \in ...
9
votes
5answers
621 views

Set {1,1} = Set {1}, origin of this convention

Is there any book that explicitly contain the convention that a representation of the set that contain repeated element is the same as the one without repeated elements? Like $\{1,1,2,3\} = ...
9
votes
7answers
1k views

Is an empty set equal to another empty set? [duplicate]

I have a definition that claims that two sets are equal A = B, if and only if: $\forall x ( x \in A \leftrightarrow x \in B)$ An empty set contains no elements. If I define the sets: A = ...
9
votes
4answers
1k views

Is any relation which contains only one ordered pair transitive?

I need clarification. Let $A=\{1,2,3\}$ be a set and $R=\{(1,2)\}$ be a relation on $A$. Is it a Transitive relation? I am confused because some text books say $R$ is transitive if it contains only ...
9
votes
5answers
438 views

What is the canonical definition of an open set?

The definition of an open set that I see in most topology texts(like the ones found in Topology by Munkres and another w/ the same title by Hocking & Young, or Basic Topology by Armstrong) is that ...
9
votes
4answers
325 views

Infinite sets and their Cardinality

(I am a 13 year old so when you answer please don't use things that are TOO hard even though I actually can understand quite complex stuff) I was studying Infinite sets and their cardinality (not in ...
9
votes
5answers
5k views

How can one prove that the union of two finite sets is again finite, without the use of arithmetic?

The notion that the union of two finite sets is again finite is something I took as intuitively true for quite a while. A proof using arithmetic is relatively straight forward. Suppose $A$ and $B$ ...
9
votes
5answers
4k 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.
9
votes
2answers
1k views

Cardinality of the infinite sets

Consider the following problem: Which of the following sets has the greatest cardinality? A. ${\mathbb R}$ B. The set of all functions from ${\mathbb Z}$ to ${\mathbb Z}$ C. The ...
9
votes
8answers
5k 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. ...
9
votes
2answers
328 views

How many paths exist between two points in the plane?

Fix distinct $a,b \in \mathbb{R}^2$. In terms of cardinality (say, beth numbers), how many distinct continuous functions $f : [0,1] \rightarrow \mathbb{R}^2$ satisfying $f(0)=a, f(1)=b$ are there? ...
9
votes
2answers
517 views

Are known transcendental numbers countable?

Do all known algorithms that generate infinitely many transcendental numbers like Gelfond-Schneider or Liouville only generate countably many? If uncountably many, is this set of measure zero?
9
votes
5answers
1k views

Definition of the Infinite Cartesian Product

(1) If $X$ and $Y$ are two sets, we define the Cartesian product $X \times Y$ as the set of ordered pairs $(x,y)$, such that $x \in X$ and $y \in Y$. (2) On the other hand [Folland, Real Analysis, ...
9
votes
3answers
307 views

A “Cantor-Schroder-Bernstein” theorem for partially-ordered-sets

If A and B are partially-ordered-sets, such that there are injective order-preserving maps from A to B and from B to A, is there necessarily an order-preserving bijection between A and B ?
9
votes
4answers
251 views

injection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$

Today a friend of mine told me a nice fact, but we couldn't prove it. The fact is that there is an injection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ defined by the fomula $(m,n)\mapsto ...
9
votes
4answers
444 views

“The set of all true statements of first order logic”

In one of my lectures, the lecturer put a bunch of examples of sets on the board, stuff like the set of all humans, set of all well typed programs in some programming language, the set of all true ...
9
votes
3answers
3k views

The Cantor set is homeomorphic to infinite product of $\{0,1\}$ with itself - cylinder basis - and it topology

I know the Cantor set probably comes up in homework questions all the time but I didn't find many clues - that I understood at least. I am, for a homework problem, supposed to show that the Cantor ...
9
votes
4answers
1k views

Is the fact that there are more irrational numbers than rational numbers useful?

Although it is known that the cardinality of the set of irrational numbers is greater than the cardinality of the set of rational numbers, is there any usefulness/applications of this fact outside of ...
9
votes
2answers
2k views

Cartesian Product of Two Countable Sets is Countable

How can I prove that the Cartesian product of two countable sets is also countable?
9
votes
3answers
327 views

With Choice, is any linearly ordered set well-ordered if no subset has order type $\omega^*$?

I've been fumbling around with order types and ordinals these past few days. I read about partial, total, and well-ordered structures, and I'm curious to see if a linearly ordered set has no subset ...
9
votes
2answers
142 views

Can we expand numbers on the left to produce irrational numbers?

I have seen examples of irrational numbers that are expanded on the right, after the decimal point: e.g. $\pi = 3.14159265...$ But can we expand numbers on the left side as well? e.g. Is ...
9
votes
8answers
278 views

Examples of “transfer via bijection”

On some occasions I have seen the following situation: We want find out whether a set of a given cardinality $\varkappa$ has some property P. If this property is invariant under bijective maps, then ...
9
votes
2answers
639 views

Can a surjection and injection exist but not a bijection? [duplicate]

If I there exists an injection $\phi: S_1 \to S_2$ and a surjection $\tau: S_1 \to S_2$, does there necessarily exist a bijection between sets $S_1$ and $S_2$? I'd like this to be true, but I don't ...
9
votes
6answers
1k views

Improving my understanding of Cantor's Diagonal Argument

I studied Cantor's Diagonal Argument in school years ago and it's always bothered me (as I'm sure it does many others). In my head I have two counter-arguments to Cantor's Diagonal Argument. I'm not ...
9
votes
2answers
2k views

Countable/uncountable basis of vector space

I've stumbled upon this exercise in algebra book, in chapter dealing with vector spaces' dimensions. Prove that basis of the field of real numbers $\mathbb R$ as vector space over the field of ...
9
votes
3answers
3k views

limit inferior and superior for sets vs real numbers

I am looking for an intuitive explanation of $\liminf$ and $\limsup$ for sequence of sets and how it corresponds to $\liminf$ and $\limsup$ for sets of real numbers. I researched online but cannot ...
9
votes
3answers
1k views

Show $S = f^{-1}(f(S))$ for all subsets $S$ iff $f$ is injective

Let $f: A \rightarrow B$ be a function. How can we show that for all subsets $S$ of $A$, $S \subseteq f^{-1}(f(S))$? I think this is a pretty simple problem but I'm new to this so I'm confused. Also, ...
9
votes
3answers
267 views

Intersection of two 'huge' sets in the plane

Consider two sets on the plane $A=\mathbb{Q}\times \mathbb{R}$ and $B=\mathbb{R}\times \mathbb{Q}$. We know that $A\cap B=\mathbb{Q}\times \mathbb{Q}\neq\emptyset$. What about the general cases? That ...
9
votes
3answers
3k 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 ...
9
votes
3answers
268 views

Why is this proof of $\mathbb{N}\times\mathbb{N}$ being countable not formal?

My copy of Introduction to Real Analysis: Bartle and Sherbert gives: Theorem: The set $\mathbb{N}\times\mathbb{N}$ is countable. Informal Proof: Recall that $\mathbb{N}\times\mathbb{N}$ ...
9
votes
3answers
266 views

Question about members in sets

Let $A_1,A_2,...,A_n$ be sets with $k$ members in $A_i$ for every $1\le i\le n$. Suppose that the $A_i$ satisfy: 1) $|A_i\cap A_j| = 1$ for all $i\ne j$, 2) $A_1\cap A_2\cdots\cap A_n =\emptyset$. ...
9
votes
1answer
124 views

Functions that satisfy $f(x+y)=f(x)f(y)$ and $f(1)=e$

My real analysis professor mentioned in passing that there exist functions $f:\mathbb{R}\rightarrow\mathbb{R}$ that satisfy all of the following conditions for all $a,b \in \mathbb{R}$: $$f(1)=e$$ ...
9
votes
2answers
91 views

How should one think about results that depend on AC?

I just encountered this: "(Theorem of A. H. Stone) Every metric space is paracompact... Existing proofs of this require the axiom of choice... It has been shown that neither ZF theory nor ZF ...
9
votes
2answers
148 views

Question from 'How to Prove It'

Below is the question from the book mentioned above: Suppose $f : A \rightarrow B$ and $R$ is an equivalence relation on $A$. We will say that $f$ is compatible with $R$ if $∀x \in A\forall y ∈ ...
9
votes
2answers
83 views

Is $\mathbb{Z}= \{\dots -3, -2, -1, 0 ,1 ,2 , 3, \dots \}$ countable?

Question: Is $\mathbb{Z}= \{\dots, -3, -2, -1, 0 ,1 ,2 , 3, \dots \}$ countable? My attemp so far: Let us create the following one-to-one correspondence between $\mathbb{Z}$ and ...