This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

9
votes
4answers
246 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
3answers
378 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
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
1answer
772 views

What is the name of the $\in$ symbol and where does it come from?

It looks like a lower-case epsilon, but the Wikipedia page on epsilon states that they are not the same. Does this symbol have a typographic identification outside of mathematics? Where did the ...
9
votes
6answers
2k 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
520 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
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
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
262 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
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
253 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
262 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
2answers
145 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 ∈ ...
8
votes
7answers
4k 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 ...
8
votes
5answers
840 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 ...
8
votes
4answers
2k views

Why is an empty function considered a function?

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

how do we assume there is infinity?

Definition of infinite: A set is infinite iff it is equivalent to one of its proper subsets. We know that our universe doesn't contain infinite number of elements (including subatomic particles), so ...
8
votes
6answers
2k views

Why is the supremum of the empty set $-\infty$ and the infimum $\infty$? [duplicate]

I read in a paper on set theory that the supremum and the infimum of the empty set are defined as $\sup(\{\})=-\infty$ and $\inf(\{\})=\infty$. But intuitively I can't figure out why that is the case. ...
8
votes
4answers
420 views

Is it correct to say that $\mathbb{R}$ has fewer elements than $\mathbb{C}$ if both are infinite?

My math teacher said that. I disagreed, but he said that I was wrong. But I'm not convinced - is it really right? Please notice that I'm not talking about $\mathbb{R}$ $⊂$ $\mathbb{C}$, but ...
8
votes
3answers
1k views

The largest number system

If my number set construction memory doesn't fail me (I'll edit if errors are pointed out), we start out with Peano's axioms to get to $\mathbb{N}$, and in the need of an additive inverse for its ...
8
votes
5answers
479 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 ...
8
votes
4answers
2k views

Interpretation of limsup-liminf of sets

What is an intuitive interpretation of the 'events' $$\limsup A_n:=\bigcap_{n=0}^{\infty}\bigcup_{k=n}^{\infty}A_k$$ and $$\liminf A_n:=\bigcup_{n=0}^{\infty}\bigcap_{k=n}^{\infty}A_k$$ when $A_n$ are ...
8
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 ...
8
votes
6answers
376 views

Why should $|2^\mathbb{N}|>|\mathbb{N}^2|$ be true?

I've been thinking a bit about infinite things lately, and this question I had wondered about came back to me. One of the classic expository demonstrations of Cantor's work is the two equally ...
8
votes
3answers
511 views

Hilbert Hotel: what if countably many buses each with countably many guests arrived?

Situation: There's a hotel owner David Hilbert who owns a hotel with countably many (infinity that can be mapped by natural number surjectively) rooms, and there are countable guests who lived inside ...
8
votes
1answer
821 views

function that is its own inverse

$f(f(x))=x \ \forall x \in \mathbb{R}$. I am trying to prove there exists an irrational $t$ such that $f(t)$ is also irrational. I have been trying things like assume $t$ irrational implies $f(t)$ is ...
8
votes
2answers
792 views

countable group, uncountably many distinct subgroup?

I need to know whether the following statement is true or false? Every countable group $G$ has only countably many distinct subgroups. I have not gotten any counter example to disprove the statement ...
8
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$ ...
8
votes
4answers
2k views

Simple Set Theory Question

I'm starting to learn Set Theory and I'm stuck on a question: Show that the relations $$(A \cup C)\subset(A\cup B), (A\cap C) \subset (A\cap B)$$ when combined, imply $C\subset B$. If it's in anyone's ...
8
votes
3answers
664 views

Uncountability of countable ordinals

According to Wikipedia, there are uncountably many countable ordinals. What is the easiest way to see this? If I construct ordinals in the standard way, $$1,\ 2,\ \ldots,\ \omega,\ \omega +1,\ \omega ...
8
votes
2answers
415 views

Is $\emptyset \in \emptyset$ or $\emptyset \subseteq \emptyset$?

Can someone give an argument, if possible using only the axioms of set theory, because I'm very weak there and have virtually no background, except the usual knowledge of the operation with sets one ...
8
votes
4answers
855 views

What's the cardinality of all sequences with coefficients in an infinite set?

My motivation for asking this question is that a classmate of mine asked me some kind of question that made me think of this one. I can't recall his exact question because he is kind of messy (both ...
8
votes
3answers
831 views

In Cantor's Diagonalization Argument, why are you allowed to assume you have a bijection from naturals to rationals but not from naturals to reals?

Firstly I'm not saying that I don't believe in Cantor's diagonalization arguments, I know that there is a deficiency in my knowledge so I'm asking this question to patch those gaps in my ...
8
votes
1answer
421 views

Why is the collection of all groups considered a proper class rather than a set?

According to Wikipedia, The collection of all algebraic objects of a given type will usually be a proper class. Examples include the class of all groups, the class of all vector spaces, and ...
8
votes
4answers
521 views

Is this proof correct for : Does $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$?

Is this proof correct? To prove $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$. Let any number $y\in F(A)\cap F(B)$. We want to show $y\in F(A\cap B).$ Therefore, $y\in F(A)$ and ...
8
votes
6answers
6k views

Is the empty set a subset of itself?

Sorry but I don't think I can know, since it's a definition. Please tell me. I don't think that $0=\emptyset\,$ since I distinguish between empty set and the value $0$. Do all sets, even the empty ...
8
votes
5answers
904 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, ...
8
votes
4answers
614 views

The set of all sets of the universe?

I can't understand Russell's paradox. What I understand is that Russell's paradox arises because the set of all sets that are members of themselves is empty. That it's impossible to find a set that's ...
8
votes
2answers
484 views

Does taking the power set give you the “next biggest cardinal”

I know that if you take the power set of a set, it has a higher cardinality. Therefore there are an infinite number of them as $P^{n}(\mathbb{N})$(the nth power set of the naturals) Let's say $$C_{n} ...
8
votes
3answers
278 views

Is there any way to save this “proof” that $\aleph_0=\aleph$? [closed]

I came up with this idea of proving that $\aleph_0=\aleph$. I know this is not true at all, but maybe there is more to it than I can see. we start with the inequality $\aleph_0 \leq ...
8
votes
5answers
754 views

Dependence of Axioms of Equivalence Relation?

This question is problem 11(a) in chapter 1 in 'Topics in Algebra' by I.N. Herstein. These are the properties of equivalence relation given in this book. Prop 1 $a \sim a$ Prop 2 $a \sim b$ ...
8
votes
2answers
330 views

Why is $|Y^{\emptyset}|=1$ but $|\emptyset^Y|=0$ where $Y\neq \emptyset$

I have a question about the set of functions from a set to another set. I am wondering about the degenerate cases. Suppose $X^Y$ denotes the set of functions from a set $Y$ to a set $X$, why is ...
8
votes
3answers
196 views

Can any subset of $x$ be moved out of $x$?

Let $x$ be a set and let $y\subset x$. Does it exist a set $z$ such that: (1) $z\cap x=\emptyset$ and (2) there exists a bijection $y \to z$ ? It is quite intuitive that the answer should be ...
8
votes
2answers
206 views

Countability of irrationals

Since the reals are uncountable, rationals countable and rationals + irrationals = reals, it follows that the irrational numbers are uncountable. I think I've found a "disproof" of this fact, and I ...
8
votes
3answers
242 views

Group of groups

The product $\times$ of two groups is associative and commutative and there's a neutral element $\{1\}$. Let's say I create "virtual groups" which are inverses with respect to $\times$ (like getting ...
8
votes
4answers
125 views

Is $0^\omega=1$?

According to a definition of ordinal exponentiation defined in Kunen's Set Theory: An Introduction to Independence Proofs (pp. 26), we define $$\begin{align} \alpha^0&=1\\ ...
8
votes
1answer
281 views

Is every element in a set also an element of the powerset?

From my understanding of powersets, a powerset contains all the possible subsets of a set. So if we want the power set of {1} then the powerset of {1} is {{}, {1}}. I was speaking to my tutor who was ...
8
votes
3answers
300 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 ...
8
votes
1answer
702 views

Cannot find a mistake in an incorrect proof.

I am reading an introductory book on proof-writing techniques. One of the exercises asks to demonstrate why the proof is incorrect. I spent quite a while thinking about it and still feel puzzled. ...
8
votes
2answers
134 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 ...