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

1
vote
1answer
27 views

Measurable Subsets

Let $\{E_{j}\}$, $j = 1, 2, ..., \infty$, be measurable subsets of $[0,1]$. Also, $\displaystyle\sum_{j=1}^{\infty} |E_j| = M < \infty$ Let $S_n$ be the set of points in $[0,1]$ contained in at ...
0
votes
0answers
22 views

satisfaction of a sentence with two quantifiers

I want to be sure that I understand how to show that a structure satisfies a sentence under a variable assignment, and suspect that I'm handling the computation of multiple quantifiers incorrectly. ...
-3
votes
1answer
12 views

Proving or disproving set statements. [on hold]

I'm not sure how to approach proving or disproving these statements. I don't know where to begin, or more specifically, what it's asking me to prove or disprove. If $ A \cap B \subseteq C$ and $A ...
1
vote
3answers
33 views

How to prove that $x^2 + 3y^2 = 1$ is contained inside of the unit ball?

What is the best way to show that $S = \{(x,y) | x^2 + 3y^2 = 1\}$ is contained in the unit ball without graphing the set?
2
votes
3answers
30 views

Largest possible value of $P(A \cap B)$

Suppose $A$ and $B$ are events with $P(A)+P(B)>1$. Show that the largest possible value of $P(A \cap B)$ is $ \min(P(A), P(B))$. I suspect I'm supposed to use $P(A \cap B) = P(A)+P(B) -P(A ...
0
votes
3answers
53 views

Explicit bijection between $\mathbb{R}$ and $\mathcal{P}(\mathbb{N})$

Is there any known explicit bijection between these two sets? I know it can be proved that such bijection exists using two injections and Schröder–Bernstein theorem, but I wanted to know whether ...
1
vote
1answer
45 views

Interpretation of set operations notation

I've been given a task that reads: Prove that given formulae is correct with the use of set theory axioms: $(\forall a)(\exists b)(\forall c)((c \in b) \iff (\exists d \in a)(c \subset d))$ ...
1
vote
1answer
31 views

Show that binary words with the same numbers of 0s and 1s are countable by finding bijection from the natural numbers to the set.

Consider all finite binary words that have the same number of zeroes as ones (ex: 0101). How can we show that this is countable? I have tried listing some words in lexicographic order, but I don't ...
0
votes
3answers
51 views

Why does the equality not hold for $(A \times B ) \cup ( C \times D ) \subset ( A \cup C ) \times ( B \cup D )$

I have proved this expression but I want to prove that they both are not equal. $$(A \times B ) \cup ( C \times D ) \subset ( A \cup C ) \times ( B \cup D )$$ May be I have to prove that $( A \cup C ...
2
votes
3answers
141 views

Can the cardinality of a power set ever be odd? [on hold]

Can the cardinality of a power set ever be odd? If it can, what conditions must be met?
0
votes
2answers
21 views

Elementary Set Theory ~ Partitions

I tried searching for a related thread to this, so please don't roast me too hard if one already exists. Anyways, if I have a set $A = \{a, b, c\}$ then $\{a, b, c\}$ would not be considered a ...
1
vote
2answers
33 views

Separation and Russell's paradox

I just want to be sure that I understand the connection between "Naive Comprehension", the Axiom of Separation, Russell's Paradox, and the existence of a universal set. Is the following correct? The ...
1
vote
3answers
57 views

Power set, Why is a right?

Can someone tell me why the first choice is the correct answer?
0
votes
1answer
26 views

Proof of Sets involving the Cartesian Product

The question goes: Let $A,B,C,D$ be sets. Prove that $\big(A\times B\big)\bigcup \big(C\times D\big)=\big(A\bigcap C\big)\times \big(B\bigcap D\big)$ I started with the definition of the cartesian ...
0
votes
2answers
73 views

Does ZFC allow for the existence of any paradoxical sets? [on hold]

ZFC doesn't allow for classes like the Russell Set (aptly named as a set I suppose...) to be sets, but my question is the following: In general, if X is a set in the ZFC universe, then for some ...
0
votes
1answer
22 views

If P(i) is true for all integers i with 2≤i≤k as inductive hypothesis, then why also p(t) is true by the inductive hypothesis?

"Let P(n) be the property n is divisible by a prime number. We prove that P(n) is true for all integers n with n> 1. Basis step. If n=2, then P(n) is true because 2 is a prime and every ...
0
votes
1answer
50 views

Cardinality of infinite sets

Georg Cantor postulated a theorem that states that for any set (even if it's an infinite set) $A$, the power set of A ($\mathbb{P}(A)$) has cardinality greater than $A$. Could this theorem also be ...
0
votes
0answers
23 views

Is this a valid notation in set theory?

I have three sets, $A:=\{a_1,\ldots,a_n\}$, $B:=\{b_1,\ldots,b_n\}$ and $C:=\{0\}$. Let $D:=A\times B \cup C$. I do not know if this is a valid notation? For example, Is $(0,b_2)\in D$? Or, is ...
2
votes
2answers
51 views

Proof on Functions /Set Theory

Let $S$ be the set of all numbers of the form $a + b\sqrt 2$ where $a$ and $b$ are rational. Let $f : S \to R$ be a function such that $f(x+y)=f(x)+f(y)$ for all $x$ and $y$ in $S$. Then $f(x)=f(1)x$ ...
0
votes
1answer
20 views

Equality between 3 sets using 3 inclusions

Let $A$, $B$ and $C$ be 3 sets. I want to show that $A=B=C$, can we use only three inclusions to do that ? For example we use $A \subset B\subset C\subset A$. Is this the only way to do this with ...
2
votes
3answers
101 views

Russell's paradox question

Tao's analysis book uses following example for Russell's paradox: $$P(x) \Longrightarrow `` x\text{ is a set, and }x \notin x"\\ \Omega := \{x : P(x)\text{ is true} \} = \{x : x\text{ is a set and }x ...
1
vote
2answers
48 views

Is my proof of the principle of backward induction using well-ordering correct?

I'm trying to prove backward induction, which I'll state as follows: Consider the set $\mathsf{A}$, where $n\in{\mathsf{A}}$, and $m+1\in{\mathsf{A}}$ $\implies$$m\in{\mathsf{A}}$. Then ...
0
votes
1answer
39 views

Mathematical induction condition “p(k)$\Rightarrow$p(k+1)” for the divisibility by a prime number

" Mathematical induction If p(n) is a statement involving the natural number n such that: p(1) is true, and p(k)$\Rightarrow$p(k+1) for any arbitrary natural number k, then p(n) is true ...
1
vote
1answer
31 views

$A$ and $B$ be non-empty bounded set of real numbers, give a counter example to the following.

Assume $A \cap B \neq \emptyset$. Find a counter-example to the claim: $\sup(A \cap B) = \min\{\sup(A), \:\sup(B)\}$ I cant seem to find a counter example to the above claim, can anyone provide a ...
0
votes
1answer
21 views
+50

Finding the data regarding the four racket games.

In a vijantkhand sports stadium, athletes choose from $4$ different racket games (apart from athletes which is compulsory for all) These are tennis, table tennis, squash and badminton. It is ...
1
vote
1answer
12 views

Partition generated $\sigma$-algebra

I saw this example given as a $\sigma$-algebra in various places. It goes like this: Let $X$ be a set and assume that the collection $\{A_1,\dots, A_N\}$ is a partition of $X$. Then the collection ...
0
votes
0answers
20 views

Term for a “Cartesian union/intersection/difference” of set families

Let $A,B$ be two families of sets. What is a term for the following families: $$C = \{a\cup b|a\in A, b\in B\}$$ $$D = \{a\cap b|a\in A, b\in B\}$$ $$E = \{a\setminus b|a\in A, b\in B\}$$ Since ...
-4
votes
1answer
41 views

Prove that $(A \cup B)\setminus B=A$ if and only if $A$ and $B$ are disjoint. [on hold]

Like the title says. Prove that $(A \cup B)\setminus B=A$ if and only if $A$ and $B$ are disjoint.
1
vote
2answers
51 views

Countable Union of Countable Sets [duplicate]

Why can't I use this proof to prove that the countable union of countable sets is countable without the axiom of countable choice? Take the set of integers; some proper subset of it, call it $A$, ...
-2
votes
1answer
49 views

How good is Naive Set Theory by Halmos? [on hold]

I happened to run into this book in an old shop and got it for like half a dollar. Has anyone read this book? Is it worth the time? (Please don't respond things like "every math book is worth the ...
1
vote
1answer
45 views

Prove or disprove if set is uncountable

Prove or disprove: The set Y of numbers in (0,1) with a decimal expansion that contains only 0s and 1s, and only finitely many 0s, is an uncountable set. Uncountable means it's not finite or not ...
1
vote
1answer
18 views

From sets of subsets to partitions

Let S be a non-empty set, and Q be a set of non-empty subsets of S such that $\bigcup Q=S$. Let $P'$ be the set of all non-empty subsets x of S such that: $\forall q\in Q. x\subseteq q \lor x\cap ...
0
votes
0answers
13 views

Successor function and transitive sets

proof I'm struggling to follow this proof, I understand the first line, but why does this give us the result. Note, $S(x)$ is the successor function, defined $S(x) = x \cup \{x\}$
2
votes
2answers
74 views

Proof of $\aleph_0^{\aleph_0} = \mathbb{c}$ without using Cantor's $2^{\aleph_0} = \mathbb{c}$

Prove that $\aleph_0^{\aleph_0} = \mathbb{c}$ without using Cantor's $2^{\aleph_0} = \mathbb{c}$ Card $\mathbb{N}^\mathbb{N} = \aleph_0^{\aleph_0}$ Card $(0, 1) = \mathbb{c}$ Define: $f: ...
7
votes
3answers
572 views

Subsets of sets containing empty set [duplicate]

Why is $\{\emptyset\}$ not a subset of $\{\{\emptyset\}\}$? It contains this element, but why is it not a subset?
1
vote
1answer
41 views

Why doesn't Cantor's diagonalization work on integers? [duplicate]

Why can't you use Cantor's diagonalization argument to prove that the integers are countably infinite? i.e. 1: 12345.... 2: 42345.... 3: 56903... 4: 46234... 5: 23421... etc. Then we could ...
0
votes
1answer
40 views

How to prove $\displaystyle\bigcup^\infty_{k=1}(\bigcap^\infty_{n=1}A_{k,n})\subset\bigcap^\infty_{n=1}(\bigcup^\infty_{k=1}A_{k,n})$

Want to show $$\displaystyle\bigcup^\infty_{k=1}\left(\bigcap^\infty_{n=1}A_{k,n}\right)\subset\bigcap^\infty_{n=1}\left(\bigcup^\infty_{k=1}A_{k,n}\right)$$ Note the bottoms are $k=1,n=1$ and ...
1
vote
1answer
11 views

Countability of generated ring $R(E)$

I am studying Paul R. Halmos Measure theory. In the section 5 of chapter 1, theorem 5 states that : If $E$ is a countable class of sets, then $R(E)$ is countable. The proof uses class of all finite ...
0
votes
0answers
14 views

Family of infinite sets with finite intersections [duplicate]

I read somewhere that there exists a family of infinite sets $F \subset P_{inf}(\mathbb N)$, such that any two $X, Y \in F$ have a finite intersection and $\lvert F \rvert = \mathfrak c$. ...
0
votes
0answers
39 views

how to mathematically represent a matrix of vectors?

My problem is the following: I have a dataset in particular have $4$ dimensions, for didactic reasons I need to represent this dataset as a $m\times n$ matrix array such that the ($i$-th, $j$-th) ...
1
vote
1answer
37 views

Where's the mistake in my reasoning?

Task: Find the cardinality of all such functions $f: P(\mathbb N) \rightarrow P(\mathbb N)$ that $f(\bigcup S) = \bigcup \lbrace f(Z) \mid Z \in S \rbrace$ The answer is: $\mathfrak c$ My ...
0
votes
2answers
42 views

Prove either A subset B or B subset A [on hold]

Sets $A$ and $B$ are subsets of $C$. What conditions ensure only 2 possibilities $A$ is a subset of $B$ $B$ is a subset of $A$
3
votes
3answers
35 views

How to prove these two sets are identical?

This is more a question of the methadology one should use to solve these type of questions: Say there is a set $V \subseteq X \subseteq Y$ and $U \subseteq Y$ such that $$X \setminus V = U \cap X $$ ...
0
votes
1answer
36 views

Prove that $|A| \geq |B|$ implies $|B| \leq |A|$ [duplicate]

If $|A| \geq |B|$, then there exists an onto function $f: A \rightarrow B$. If $|B| \leq |A|$, then there exists a one-to-one function $f: B \rightarrow A$. My issue is that I don't think that $|A| ...
1
vote
3answers
87 views

Is $(-\infty, 0)$ the same size as $(0, \infty)$?

A differential equations problem asked about the largest interval on which the solution was defined. The solution was defined except for $t=0$, which made me wonder whether the intervals $(-\infty, ...
1
vote
2answers
58 views

Set theory - Image, preimage

I have this assignment. Let $X$ be a set and $f:X\to X$ a function. Let $A\subseteq X$. Determine whether each of the following statements is true in general, and give a proof of the correct ...
0
votes
1answer
22 views

What is the composition of the two given relations $R_1\circ R_2$?

I have a set $A = \{a,b,c,d\}$ on which two relations are $R_1=\{(a,b),(a,d),(b,c),(c,a),(c,d),(d,b)\}$ and $R_2=\{(a,b),(b,c),(d,c),(a,d),(a,c)\}$. What will $R_1\circ R_2$ be? $\circ$ is a the ...
2
votes
1answer
34 views

How do i determine whether a relationship is transitive and has the trichotomy property or not?

I have a relation on the set A {a,b,c,d}- R1={(d,c),(c,a),(b,d),(d,a),(a,a),(b,c),(b,a)} I need to determine whether this relation has the trichotomy property or not? P.S- If by any chance you do ...
0
votes
3answers
34 views

Find minimum number of customers that must have visited the bakery that day?

A bakery sells three kinds of pastries -pineapple, choclate and black forest. On a particular day, the bakery owner sold the following number of pastries : $90$ pineapple , $120$ chocolate ...
0
votes
1answer
31 views

Prob. 9, Sec. 19 in Munkres' TOPOLOGY, 2nd edition: Equivalence of the choice axiom and non-emptyness of Cartesian product

The Axiom of Choice is as follows: Given a collection $\mathcal{A}$ of disjoint non-empty sets, there exists a set $C$ consisting of exactly one element from each element of $\mathcal{A}$; that ...