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

0
votes
0answers
12 views

Is there a key difference between the principle of transfinite induction and the principle of transfinite induction for ordinals?

In a recent question I was asked to prove the principle of transfinite induction for ordinals but I mistakenly proved the principle of transfinite induction, since I have a only a vague understanding ...
3
votes
4answers
137 views

Definition of smallest equivalence relation

I came across the term 'smallest equivalence relation' in the course of a proof I was working on. I have never thought about ordering relations. I googled the term and checked stackexchange and ...
0
votes
2answers
22 views

Show that $(A \cup B)(C \cup D) = AC \cup AD \cup BC \cup BD$

Given nonempty subsets $A,B,C,$ and $D$ of $\mathbb{R}$, show that $(A \cup B)(C \cup D) = AC \cup AD \cup BC \cup BD$. I am not sure how to go about proving this since we aren't given intervals. ...
1
vote
0answers
20 views

What is $\frac{\left(A \cap B\right)}{C}$ and $\frac{C}{\left(A \cap B\right)}$

If $A=\{3,5,6,7,9\}$ and $B=\{1,2,3,4,7\}$ and $C=\{3,4,5,6\}$ I found the following: $A\cap B=\{3,7\}$ $A\cup B=\{1,2,3,4,5,6,7\}$ $\frac{\left(A\cap ...
-1
votes
3answers
56 views

Is it true that, if $A\setminus B \subseteq C$, then $A\setminus C \subseteq B$?

Prove or provide counterexample for : If $A\setminus B \subseteq C$ then $A\setminus C \subseteq B$ My approach was, supposed $A\setminus B \subseteq C$, then let $x \in A\setminus B$, since ...
1
vote
3answers
80 views

How can I show that $\mathcal{B} = \{(a,b)\subset \mathbb{R}\mid a,b \in \mathbb{Q}\}$ is a countable set?

I know that $\mathcal{B} = \{(a,b)\subset \mathbb{R}\mid a,b \in \mathbb{Q}\}$ is a basis on $\mathbb{R}$. I need to show that $\mathcal{B}$ is countable. How can this be done? Attempt: Take ...
1
vote
2answers
51 views

Problem on $\sigma$-algebra from Rudin

Does there exist an infinite $\sigma$-algebra which has only countably many members ? Proof: Suppose that $\sigma$-algebra $\mathfrak{M}$ has countably many members, namely $\{A_i\}_{i=1}^{\infty}$. ...
3
votes
1answer
32 views

Is my proof correct that there are uncountably many sets of positive integers?

Let $\mathbb{N}$ be the set of natural numbers. Prove that $2^{\mathbb{N}}$ is uncountable. Proof: Suppose that $2^{\mathbb{N}}$ is countable then $2^{\mathbb{N}}=\{A_1, A_2, A_3,\dots\}$. We have to ...
0
votes
2answers
23 views

Why aren't there uncountably many disjoint open intervals of $\mathbb{R}$?

I know that this can't be true given that $\mathbb{R}$ is separable, but I'm having a hard time coming to grips with why this is, exactly. In particular, can't I just take some uncountable strictly ...
1
vote
2answers
27 views

Countable set can be listed in a sequence

Let $S$ be a countable set, i.e. exists bijection between $\mathbb{N}$ and $S$. Why elements of $S$ can be listed in a sequence? EDIT: I guess that bijection is not crucial. It's sufficient that ...
1
vote
1answer
24 views

Why can we choose a greatest ordinal $\beta$, such that $\omega^\beta\leq \alpha$?

I am reading a proof of Cantor's normal form theorem. In it, I read: for arbitrary $\alpha>0$ let $\beta $ be the greatest ordinal such that $\omega^\beta \leq \alpha$. Why should such an ...
0
votes
1answer
22 views

Some ordinal arithmetic exercises

I reckon it's easier if I don't open an extra thread for each of these small exercises. I'm trying to get a better grasp of ordinal arithmetic. If someone could please give me feedback on my ...
0
votes
1answer
52 views

Find a bijection between the Reals and an interval

I need to find a bijection between the reals and (−∞, 0) however I'm struggling to do so. I'm trying to prove that these two have the same cardinality. Also need to prove that the Reals and the ...
1
vote
1answer
324 views

Number of sigma algebras for set with 4 elements

I am supposed to watch out for sigma algebras that belong to the set $X=\{1,2,3,4\}$. I found 15(now with the new set even more) of them. I was wondering whether there is some nice proof how to see ...
0
votes
1answer
50 views

Problems with Apostol's calculus

I am self teaching myself so I couldn't ask any teacher but here are somethings in Chapter 1 that I can't understand. In the book Area is defined axiomatically but some parts of it are not just making ...
17
votes
1answer
2k views

Number of $\sigma$ -Algebra on the finite set

Let $X$ is a nonempty set with $m$ members . How many $\sigma$ -algebra can we make on this set?
1
vote
1answer
142 views

Set builder notation for matching element pairs

I have a set of pairs, $S = \{ \langle a,b \rangle_1, \langle a,b \rangle_2, ..., \langle a,b \rangle_n \} $ where $a$ is not unique amongst the pairs. If I want to express the extraction of all the ...
-1
votes
2answers
76 views

Doesn't statement 'S is a set of all sets that are not elements of themselves.' hold true by reductio ad absurdum?

The simplest of the logical paradoxes is Russell's paradox, which can be described as follows: Let $S$ denote the set of all sets that are not elements of themselves. Is $S$ an element of ...
2
votes
1answer
19 views

Ordinal Arithmetic Identity

Let $\alpha$ be an Ordinal and $S$ a set of Ordinals. Is it the case that $$\alpha\bigcup\limits_{x\in S} x=\bigcup\limits_{x\in S} \alpha x$$ and if so how could one prove this?
0
votes
3answers
70 views

Is it okay to say 'an element of a family'?

I haven't seen a book mentioning 'an element of a family', though either 'a member of a family' or 'a member of a set' is mentioned frequently. Indexed Families of Sets Recall that a set is a ...
1
vote
3answers
44 views

Why "to every set and to every statement p(x), there exists {$x\in A | p(x)$}?

As a rule, to every set A and to every statement p(x) about $x\in A$, there exists a set {$x\in A | p(x)$} whose elements are precisely those elements x of $A$ for which the statement $p(x)$ is ...
3
votes
3answers
4k views

How to determine transitivity and intransitivity of this relation?

I am having trouble finding if the following relation is transitive or intransitive. I would be very thankful if someone could help me out by explaining transitivity and its rules with regard to this ...
4
votes
2answers
327 views

Dividing a Checkerboard into L-Shaped Regions

In preparation for the GRE Math-Subject test, and honestly for the fun of it, I've been working through a select number of my texts. The first of which is Saracino's Abstract Algebra text. I was ...
1
vote
4answers
40 views

Can $A \times B$ give you a circle of radius $1$.

I've heard that $A \times B$ cannot be a circle of radius $1$. However I think this is false as I know from $\sin^2 x+\cos^2 x=1$. So can we take the set $A=\{\sin \theta | \theta \in R \}$ and ...
0
votes
2answers
63 views

Does $1-\frac{1}{2^\omega}$ equal 1? What about $1-\frac{1}{2^{\aleph_0}}$?

(Correct if I'm wrong on any of this.) Recently, I've been learning about transfinite ordinals and cardinals. For some cases, I understand the difference between ordinals and cardinals, for instance ...
0
votes
6answers
44 views

How to construct a proof of $A = (A\cap B)\cup (A-B)$? [duplicate]

Constructing a Venn diagram is not enough as a proof, how would I go about actually proving $A = (A\cap B)\cup(A−B)$?
0
votes
1answer
18 views

Show that $\bigcup_{n=1,2,3,…} [0,1-1/n^2]=[0,1)$

My proof. Initially, we will show that $\bigcup_{n=1,2,3,...} [0,1-1/n^2]\subseteq [0,1)$. For every $n=1,2,3,...$ since $0\leq 1-1/n^2 <1$, we have $[0,1-1/n^2]\subseteq [0,1)$. Now, we will ...
0
votes
2answers
62 views

Is $y \in\{f(x)\mid x \in X\} ⇔ f(x) \space ∃ x \in X$ true?

Definition 9 $f(A) =\{f (x) \mid x\in A\}$ The following is from the proof of $f(\bigcup_{\gamma \in \Gamma}A_{\gamma})$ = $\bigcup_{\gamma \in \Gamma}f(A_{\gamma})$. $$y \in f \left( ...
1
vote
1answer
59 views

Where in the proof of this theorem shows “If (x, y)$\in f$ and (x, z) $\in f$, then y=z.”?

Definition 8. Let X and Y be sets. A function from X to Y is a triple (f, X, Y), where f is a relation from X to Y satisfying (a) Dom(f) = X. (b) If (x, y)$\in f$ and (x, z) $\in f$, then y=z. ...
0
votes
1answer
26 views

How does $f: X\rightarrow W$ in the Theorem 6 satisfy Def. 8(b) “If $(x, y) \in f$ and $(x, z) \in f$, then y=z”?

Definition 8. Let X and Y be sets. A function from X to Y is a triple (f, X, Y), where f is a relation from X to Y satisfying (a) Dom(f) = X. (b) If (x, y)$\in f$ and (x, z) $\in f$, then y=z. ...
4
votes
3answers
178 views

Fixed points and cardinal exponentiation

Let the function $F: On \rightarrow On$ be defined by the following recursion: $F(0) = \aleph_0$ $F(\alpha+1) = 2^{F(\alpha)}$ (cardinal exponentiation) $F(\lambda) = \sup\{F(\alpha):\alpha \in ...
0
votes
1answer
24 views

Every infinite set is $T$- infinite.

I am trying to prove the claim in the title as stated in the Set theory book by Thomas Jech. As for the definitions: A set $X$ has $n$ elements (where $n\in \mathbb{N}$) if there is a one-one ...
0
votes
1answer
52 views

are $a$'s, $1$'s in a family $\{a, a, a\}, \{1, 2\}, \{2, 4\}$ themselves sets?

Usually in other books, a family is defined as a set whose elements themselves are sets. But I don't think $a$ in a set $\{a, a, a\}$ with repetetion of $a$ and $2$ in $\{1, 2\}$ or $\{2, 4\}$ are ...
-1
votes
1answer
49 views

Finding a bijection and using the Schröder-Bernstein to prove same cardinality

I've been asked to prove that $\mathbb{R}$ and the interval $(-\infty,0)$ have the same cardinality using two methods, one being find a bijection and the other to use the Schröder-Bernstein theorem. ...
5
votes
3answers
89 views

Are sets just predicates with syntactic sugar?

Do mathematicians agree/accept that "sets are just predicates with syntactic sugar"? If not, then Why not? I mean, I can translate between $ x \in S $ and $ S(x) $. Will that change the correctness ...
0
votes
1answer
16 views

Can you denote a family $F: N → P(R)$ such that $F(n) = R\space, ∀n ∈ N$ in a set builder notation?

I don't fully understand the meaning of the following underlined explanation. Can you denote $F: N → P(R)$ such that $F(n) = R\space, ∀n ∈ N$ in a set builder notation? Definition A family of ...
0
votes
1answer
31 views

Can you give an example of function $F: N → P(R)$, such that $F(n) = R\space ∀n ∈ N$?

I don't fully understand the meaning of the following underlined explanation. Can you give an example of function $F: N → P(R)$ such that $F(n) = R\space ∀n ∈ N$? Definition A family of sets is ...
0
votes
1answer
25 views

Logic of Set Theory & Partially Order (Informative Discussion)

My final exam passed but, honestly I want to understand what this (Question 4) problem means because I don't know what it is asking for. I am a undergraduate, so it would be most helpful if the ...
1
vote
2answers
9 views

Find total number of relations that are equivalence as well as partial order set

Find total number of relations that are equivalence as well as partial order set. Assume set contains total $n$ elements. My attempt: As equivalence relation has property reflexive, symmetric ...
0
votes
2answers
37 views

Why is $A \times \bigcup \mathscr{B} = \bigcup\{ A \times Z \mid Z \in \mathscr{B} \}$?

I have seen this answer given as a solution: Solution. Take $\langle x, y \rangle \in A \times \bigcup \mathscr{B}$. So $y \in \bigcup \mathscr{B}$, and thus there exists some $X \in \mathscr{B}$ ...
-1
votes
1answer
23 views

Prove that $f^{-1}(Y \setminus B_1) = X \setminus f^{-1}(B_1)$

Let $f:X \to Y$ be a map with $A_1,A_2 \subset X$ and $B_1,B_2 \subset Y$. Prove that $f^{-1}(Y \setminus B_1) = X \setminus f^{-1}(B_1)$ where $f^{-1}(B) = \{x \in X: f(x) \in B\}$. Attempt: ...
6
votes
0answers
52 views

How to solve probability when sample space is infinite?

I came up with a random problem yesterday: Suppose that in a random trial, each point $(x,y)$ where $x,y \in \mathbb{R}$ and $0 \leq x,y \leq 1$ is assigned a value of $0$ with 50% chance and a ...
0
votes
1answer
23 views

Proving union of family set

I am having trouble with the following exercise in Velleman's How To Prove This: Suppose B is a set and $\mathscr F$ is a family of sets. Prove that $\bigcup\{A\setminus B|A\in \mathscr ...
0
votes
0answers
26 views

Given X and Y ind. rv's, when is f(X,Y), g(X,Y) ind.?

I have to parallel questions. I was trying to solve this one: "Given two independent real-valued randomvariables X and Y defined on the same sample space, is it true that X and X+Y are independent." ...
2
votes
0answers
38 views

Constructing a family of sets

I am completely stuck at the following question. Suppose $X$ is an infinite set. Show that there is a family $\mathcal{F}$ of subsets of $X$ satisfying the following: (a) If $A \subseteq X$ is ...
1
vote
2answers
32 views

Prove that if $g \circ f$ is onto and $g$ is one-to-one, then $f$ is onto

Let $f:A \to B$ and $g:B \to C$ be maps. Prove that if $g \circ f$ is onto and $g$ is one-to-one, then $f$ is onto. Attempt: If $g \circ f$ is onto, then for all $y \in A$, $\exists x$ such ...
2
votes
2answers
11 views

Checking injectivity of a certain function from a union of a family indexed by $K$ to $K$

Let $A = \{ A_k | k \in K \}$ be a family of sets indexed by $K$. By Zermelo's theorem, $K$ can be well-ordered. Now, let $\leq$ be a well-order on $K$. Define $j: \bigcup\limits_{k \in K} A_k \to ...
2
votes
2answers
39 views

What do sets in $S := \{ (-\infty, b) : b \in \Bbb{R} \} \cup \{ (a, \infty) : a \in \Bbb{R} \}$ look like

If I'm given a collection $S := \{ (-\infty, b) : b \in \Bbb{R} \} \cup \{ (a, \infty) : a \in \Bbb{R} \}$ Then would the sets of S only be of the form $(-\infty, b) \cup (a, \infty)$ or could they ...
2
votes
2answers
57 views

Intersection of subgroups is a subgroup: What if collection of subsets is empty?

Theorem: The intersection of any arbitrary collection of subgroups of a group is again a subgroup. http://groupprops.subwiki.org/wiki/Intersection_of_subgroups_is_subgroup I don't understand the ...