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
2answers
54 views

Does ZFC allow for the existence of any paradoxical sets?

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
18 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
47 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
18 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
48 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
16 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
99 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
47 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
36 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
28 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
14 views

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
15 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
40 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
50 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
47 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
44 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
11 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
71 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
566 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
40 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
39 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
37 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
36 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
40 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
33 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
33 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
55 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
21 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
32 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 ...
0
votes
1answer
41 views

Why is $\inf_{m\geq n} X_m = \cap_{m\geq n} X_m$?

Why is $\inf_{m\geq n} X_m = \bigcap_{m\geq n} X_m$? Any help would be appreciated.
0
votes
0answers
24 views

problem based on transfinite number concept (Is aleph null itself a set?) [duplicate]

Is transfinite number (aleph null, continuum etc.) itself a set, or it is generalization of numbers in a correlation sense to compare the size of infinite set in terms of number of elements in $1-1$ ...
1
vote
2answers
46 views

Can you go from $\aleph_0$ to $\aleph_1$ with tetration or other higher order operators?

The paradox of Hilbert's Hotel shows us that you can not get past the cardinality of the natural numbers ($\aleph_0$) by adding a finite number (one new guest), adding an infinite quantity (infinitely ...
0
votes
1answer
14 views

Number of relations and number of functions on an infinite set

Let $A = \{$ Relations which are not functions from $\mathbb R \rightarrow \mathbb R\}$ and $B = \{$ Functions from $\mathbb R \rightarrow \mathbb R\}$ How do I compare their cardinalities? I think ...
1
vote
2answers
50 views

If there is a bijective function from A to B, then prove that |A| = |B| [on hold]

What is the best way to approach this problem? For some reason I can't get my head around this problem. It seems like such an obvious conclusion to draw, but when I sat down to solve this question, I ...
1
vote
1answer
30 views

Show that $\mathcal{O}$ forms a $\sigma$-algebra

Let $\Omega$ any uncountable set and $\mathcal{O}$ is the collection of all subsets of $\Omega$ which are countable or have countable complements be the collection. We want to show that $\mathcal{O}$ ...
2
votes
0answers
11 views

Minimum vs. Minimal Elements of a Set [duplicate]

Suppose you have a set $\textit{S}$ with a generalized inequality $\preceq_k$. Is it possible for such a set to have a $\textit{unique}$ minimal element that is not a minimum element? I feel like it ...
0
votes
1answer
31 views

Cardinal equality: $\;\left|\{0,1\}^{\Bbb N}\right|=\left|\{0,1,2,3\}^{\Bbb N}\right|$

I need to prove the above equality without Cantor-Bernstein Theorem or cardinals arithmetic (i.e., a bijection must be found). I know that for example $\;S\to 1_S=\;$ the indicator function, gives a ...
0
votes
1answer
57 views

Countable union of sets

Suppose $f$ is a one-to-one function. $\forall{n}: F(A_1)=B_1, F(A_2)=B_2, F(A_3)=B_3, \ldots, F(A_n)=B_n$ (I'm talking about a countable amount of infinite sets, A_1, A_2, A_3...) $\forall{i} \neq ...
0
votes
2answers
39 views

Is a relation, R, an Equivalence Relation of a Power Set?

Where $A = \{1,2,3,4,5,6\}$ and $S = P(A)$ is the power set, for $a,b \in S$ define a relation $R: (a,b) \in R$ where $a$ and $b$ have the same number of elements. Is $R$ an equivalence relation on ...
0
votes
1answer
50 views

Cardinality of the set of all bijections

Let $A$ be an infinite set and let $S$ be the set of all bijections $A \rightarrow A$. Then if $\mid A \mid = \kappa$, then $\mid S \mid = 2^\kappa$. I'm able to prove it for $A = \mathbb{N}$ by ...
0
votes
1answer
25 views

Find the maximum $\%$ of students who could have problems in all $4$ subjects

In a school $90\%$ of students faced problem in $maths$, $80\%$ of students faced problem in $computers$, $75\%$ of students faced problem in $sciences$, $70\%$ of students faced problem in ...
7
votes
2answers
83 views

Proof verification for $\mathcal{P}(A) \cap \mathcal{P}(B) = \mathcal{P}(A \cap B)$

I propose here my proof for: $$\mathcal{P}(A) \cap \mathcal{P}(B) = \mathcal{P}(A \cap B)$$ $\Longrightarrow$ $$x \in \mathcal{P}(A) \land x \in\mathcal{P}(B)$$ $$x \subseteq A \land x \subseteq B$$ ...
4
votes
2answers
79 views

Why was $\aleph$ (aleph) chosen for infinities?

Why did Cantor choose a letter from the Hebrew alphabet to represent infinities, rather than using some Greek letter?