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
991 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 ...
0
votes
2answers
31 views

Subsets and Cardinality

I'm confused on if I should count a subset as one element or if I should count all the elements of that subset when computing cardinality. Example: Given the set $A = \{1,2,3,\{4,5,6\}\}$ does $A$ ...
1
vote
3answers
71 views

Zermelo–Fraenkel set theory the natural numbers defines $1$ as $1 = \{\{\}\}$ but this does not seem right

If 1 can be defined as the set that contains only the empty set then what of sets which contain one thing such as the set of people who are me. number 1 does not just mean $1$ nothing, it means $1$ ...
1
vote
1answer
60 views

A question about cardinal numbers in ZF set theory.

It is well known that cardinal numbers and the relations between them can be defined in ZF set theory (using the notion of "rank"), without the need of additional axioms. Can the following statement ...
25
votes
2answers
1k views

Lamport claims there is an error in Kelley's proof of the Schroeder-Bernstein theorem. What is it?

In section 4.1 of his note How to write a proof, Leslie Lamport mentions an error in Kelley's exposition of the Schroeder-Bernstein theorem: Some twenty years ago, I decided to write a proof of ...
0
votes
1answer
17 views

Fallacy considering a relation between infinite sets and empty set

Namely I have stumbled upon a theorem due to Dedekind which says: A set is infinite iff it is equinumerous to a proper subeset of itself Since empty set is proper subset of every set except itself ...
7
votes
7answers
228 views

Is $\mathbb{C}$ equal to $\mathbb{R}^2$?

Complex numbers are usually formally defined as pairs of real numbers. Although there are operations on $\mathbb{C}$, such as complex multiplication, which are not found in operations usually applied ...
1
vote
1answer
25 views

Notation for building ordered sets of zeros

I want to define a lattice where each site is occupied by an ordered set of zeros. Later in the calculation, the zeros grow to nonnegative integers, but I need to start with zeros. At the $i$th site, ...
5
votes
3answers
255 views

Diagonalisation argument for real numbers

I know that the the set of real numbers has been proved uncountable by mathematicians, so my question is why this is wrong. In countability arguments that I have seen the numbers are laid out in a ...
1
vote
1answer
11 views

Composition of mappings on finite sets

If I'm working in the realm of finite sets on the form $\underline{n} = \{1, \ldots, n\}, n \in \mathbb{N} $. Consider any two transformations $f :\underline{n} \to \underline{m}$ and $g ...
0
votes
2answers
42 views

The intersection of ordered pairs.2

Definition of (a,b) is the set {{a},{a,b}}. Of course, (a,b) intersection with (b,a) is the set {{a,b}}. But if we represent ordered pairs as points in a plane, they do not intersect. Please explain.
2
votes
2answers
90 views

The Intersection of Ordered Pairs

I've seen that the ordered pair $(a,b)$ is defined as a set that is $(a,b)=\{\{a\},\{a,b\}\}$. Can you explain what do we mean when $(a,b) \cap (b,a) = \{\{a,b\}\}$? I feel that there should be no ...
0
votes
4answers
30 views

Empty preimage of an intersection implies empty intersection of the preimages

Assume $f:A\to A'$ is a function, $B\subset A'$, $C\subset A'$, and $f^{-1}(B\cap C)=\emptyset$ How can we see that $f^{-1}(B)\cap f^{-1}(C)=\emptyset$?
-1
votes
2answers
28 views

Prove this result about power sets [duplicate]

I have to prove this result: If $P$ be the power set, and $B$ and $C$ are two sets, then if $B \subseteq C$ prove that $P(B) \subseteq P(C)$. Now, it seems obvious to me that since all the ...
2
votes
1answer
58 views

Proving there's a set with the cardinality $\mathfrak c$ on the $x$ axis of points that do not belong to the set of disks

Prove/disprove: On the $x$ axis there's a set with the cardinality $\mathfrak c$ of points that do not belong to any disk of a set $O$ of disjoint disks of positive radius $\{(x,y)\in \mathbb ...
-2
votes
2answers
117 views

How to understand some bewildering limits of sequences of sets [closed]

Let $(s_n)$ be the sequence of sets $s_n=\{n\}$ of natural numbers $1, 2, 3, ...$ Then the limit is the empty set $\{\}$. The sequences of sets $a_n=\{n^1\}$ or $b_n=\{n^n\}$ or ...
2
votes
2answers
21 views

How to prove that $R\cup S$ and $R\cap S$ are symmetric if R and S are symmetric?

The question is as follows- R and S are two symmetric relations on the same set A. Prove that $R\cup S$ and $R\cap S$ are symmetric. I tried it like this but I can't continue it. Any help is ...
0
votes
1answer
51 views

Help with a proof. Countable sets.

This is a Lemma from N.L. Carothers Real Analysis. Lemma. An infinite subset $A$ of $\mathbb{N}$ is countable. Proof. Since $A\ne\emptyset$, there is a smallest element $x_1\in A$. Then ...
1
vote
1answer
56 views

Proving Equivalence of Two Version of Axiom of Choice

I am working on an assignment that requires proving the equivalence of two versions of the axiom of choice. (1st form): For any relation $R$, there is a function $H \subseteq R$ with dom $H =$ dom ...
1
vote
2answers
25 views

Find all intersections of subsets.

I am having trouble with what seems like it should be a simple problem. I am trying to find intersections of connections between multiple people but I want to include any intersection of connections ...
1
vote
1answer
28 views

Finding the cardinality of $\{X\in \mathcal P(\mathbb R)| |X|=\aleph_0 \}$

Let $S$ be a relation over $\mathcal P(\mathbb R)$ such that $A,B\subseteq\mathbb R: \exists f:A\to B, \exists g: B\to A$ and $f,g$ are injections. Find the cardinality of $\{X\in \mathcal ...
1
vote
0answers
42 views

Is $2^{\alpha} < 2^{\beta}$, where $\alpha$ and $\beta$ are cardinal numbers, such that $\alpha < \beta$? [duplicate]

Let $\alpha$ and $\beta$ be cardinal numbers such that $\alpha < \beta$. Isn't it always true that $2^{\alpha} < 2^{\beta}$ ? Because if I am not wrong, $2^{\alpha}$ denotes the immediate ...
2
votes
2answers
55 views

Proof of $A \subseteq B \Leftrightarrow A \cap B = A$ (Check chain of implications)

Prove $A \subseteq B \Leftrightarrow A \cap B = A$. My attempt: Case $\Rightarrow$: $$\begin{align} A \subseteq B & \Rightarrow & [x\in A \Rightarrow x\in B] \\ &\Rightarrow &[x ...
1
vote
1answer
28 views

How many order relations there are on $A=\{1,2,3 \}$

How many order relations there are on $A=\{1,2,3 \}?$ An order relation is defined like here, I know the answer is 19 but I just can't get to it. Here's a rough sketch, each element $abc$ ...
1
vote
1answer
30 views

Find how many People Like dancing Only,People Like Movies

A survey was conducted among 402 persons regarding their interest in movies,dancing and games it was found that (i) 100 People Like games. (ii) 142 People Like movies or dancing but not games. (iii) ...
2
votes
1answer
31 views

Let $\alpha, \beta, \gamma$ be cardinals, $\beta \leq \gamma$, prove $\alpha ^{\beta}\le \alpha ^{\gamma}$

Let $|A|=\alpha, |B|=\beta, |C|= \gamma$ be cardinals and $\beta \leq \gamma$. Prove $\alpha ^{\beta}\le \alpha ^{\gamma}$. So from the given we know that there's an injection $f:B\to C$ and some ...
1
vote
0answers
26 views

Chains and upward directed families of sets.

A family $\mathcal F$ of subsets of a set is closed under unions of chains if and only if it is closed under unions of upward directed families. One way is straightforward. For the other one: if ...
1
vote
1answer
29 views

Question about a bijection between $\mathbb R$ and $\mathbb R \cup \{\infty\}$

About a bijection between $\mathbb R$ and $\mathbb R \cup \{\infty\}$ If we'll take a line $f(x)=\begin{cases} ax &, x\in\mathbb R\\ 0 &, x=\infty \end{cases}$ then we'll have a bijection. ...
1
vote
1answer
42 views

comparing two sets in set theory

I have two sets A and B and this condition holds: $\forall x \in A , y \in B: x \leq y$ Is there any standard term to describe the relation of A and B? something like $A \leq B$? Thanks for your ...
3
votes
0answers
20 views

Prove that $\operatorname{ran} f \subseteq \operatorname{dom} g \implies\operatorname{dom} (g \circ f)=\operatorname{dom} f$

Some preliminaries: A function $f$ is a binary relation such that $(x,y_1) \in f$ and $(x, y_2) \in f$ implies $y_1 = y_2$. $\operatorname{ran} f = \{y: \exists x$ such that $(x,y) \in f\}$ ...
2
votes
2answers
32 views

$|A|=\mathcal c \ \ |B|=\aleph_0 \ \ A\cap B=\emptyset$ prove that $ |A\cup B|=\mathcal c$

Let $|A|=\mathcal c, \ |B|=\aleph_0, \ A\cap B=\emptyset,$ Prove that $ |A\cup B|=\mathcal c$ So $|A\cup B|=|A|+|B|$ but this just leads to cardinal arithmetic which I don't think is the right ...
2
votes
2answers
45 views

Monotonicity Question in Enderton's text on Set Theory

I am struggling to begin solving the following question in Enderton's textbook on set-theory: Assume that $F: P(A) \rightarrow P(A)$ and that $F$ has the monotonicity property: $X \subseteq Y ...
0
votes
2answers
49 views

Understanding morphisms in FinSet

I'm looking at the skeletal FinSet category ; there is one object for each natural number $n$ (including $n=0$), and a morphism from $m$ to $n$ is an $m$-tuple $(f_0, \ldots, f_{m-1})$ of numbers ...
1
vote
1answer
25 views

Prove that $R[A \cup B] = R[A] \cup R[B]$, where $R$ is a binary relation.

Can someone please verify this? Prove that $R[A \cup B] = R[A] \cup R[B]$, where $R$ is a binary relation. Here, $R[C] = \{y: \exists x \in C $ such that $(x,y) \in R\}$ Let $z \in R[A \cup ...
1
vote
3answers
73 views

Why do we define functions to be set theoretic objects?

Why do we define functions to be set theoretic objects? Functions are so intuitive, why do we define it in complicated set theory language?
9
votes
3answers
253 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}$ ...
5
votes
1answer
97 views

Does any uncountable set contain two disjoint uncountable sets?

Is it true that for any uncountable $S$, there exits two uncountable subsets $S_1,S_2 \subseteq S$ with $S_1 \cap S_2 = \emptyset$? I can find no counter example, but no proof either. I am aware of ...
3
votes
1answer
85 views

Does $f^{-1}(Y)$ make sense if $Y$ is “bigger” than $X$

My textbook asks me to decide whether or not this expression is true: Given the function $f: X \to Y$ with $B_1 \subseteq Y $. $ f^{-1}(Y $ \ $ B_1) = X $ \ $f^{-1}(B_1) $ I was confused ...
2
votes
4answers
475 views

What is the truth table for demorgan's law?

From Demorgan's law: $(A \cup B)^c = A^c \cap B^c$ I constructed the truth table as follows: $$\begin{array}{cccccc|cc} x\in A & x \in B & x \notin A & x \notin B & x \in A^c ...
0
votes
3answers
74 views

Inclusion-Exclusion Principle for basic combinatorics problem…

How many ways are there to pick five people for a committee if there are six (different) men and eight (different) women and the selection must include at least one man and one woman? I know ...
2
votes
2answers
60 views

Element of a Singleton (set with one element) notation

I was wondering what the notations are for indicating the element of a singleton (or unit set, or set with cardinality 1). This would be the inverse of set construction: $$X = \{y\} \tag{1}$$ $$y = ...
2
votes
1answer
60 views

Use principle of mathematical induction to show a function defined recursively is uniquely determined.

I'm having difficulty with the following taken from "Elementary Number Theory And Its Applications" by Rosen section 1.1 questions. "Use the Principal Of Mathematical Induction to show that the value ...
1
vote
1answer
60 views

correct Set theory notations.

What is correct notation for the following, I have seen both in some books. To show an empty set, is it Φ(phi) or Ø(slash O) or both. To show an Universal set, is it ε(epsilon) or U or both. I am ...
0
votes
1answer
40 views

Confused about images, reverse images.

I am confused over a seemingly simple practice question which I will post below. I am confused over the concept as well, but this question just helps to show what it is I am not understanding. ...
1
vote
1answer
54 views

Showing $ (R ∪ R^{-1})^∗ = R^∗ ∪ R^{−1∗} $ is false by giving a counterexample.

Show that $$ (R ∪ R^{-1})^∗ = R^∗ ∪ R^{−1∗} $$ is false by giving a counterexample. I tried the following, but every time it keeps coming out as true (instead of false): If $R = \{(a,b), ...
4
votes
3answers
59 views

Show that $A \subseteq B \iff A \subseteq B-(B-A)$

Can someone please verify this? Show that $A \subseteq B \iff A \subseteq B-(B-A)$ $(\Rightarrow)$ Let $x \in A$. Then, $x \notin B-A$. Also, $x \in B$. Therefore, $x \in B-(B-A)$ So, $A ...
2
votes
1answer
51 views

$A \setminus B \cup C = A \setminus (B \cup C)$? [duplicate]

$A \setminus B \cup C$ or $A \setminus (B \cup C)$? Sorry as this is a very soft question, but I couldn't find the answer anywhere. Are these two things generally considered the same?
1
vote
0answers
94 views

Inequality with size of sets

Let $ k$ be an integer, $ k \geq 2$, and let $ p_{1},\ p_{2},\ \ldots,\ p_{k}$ be positive reals with $ p_{1}+p_2+\cdots+p_k= 1$. Suppose we have a collection $ \left(A_{1,1},\ A_{1,2},\ \ldots,\ ...
2
votes
2answers
200 views

The union of well-ordered sets is a well-ordered set

In Halmos's Naive Set Theory about well-ordering set, it states that if a collecton $\mathbb{C}$ of well-ordered set is a chain w.r.t continuation, then the union of these sets is a well-ordered set. ...
1
vote
1answer
43 views

Axiom of extension

I am learning Set Theory from the book Naive Set Theory by Halmos as part of my course. The first chapter is on the Axiom of Extension. I understand what it is but what I don't understand is why it ...