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

3
votes
0answers
24 views

Basic question on appication of Sunflower lemma

A sunflower or $\Delta$-system is a collection of sets $\mathscr{F}$ whose pairwise intersections are all the same set $S$, possibly empty. Elements of the collection of sets $\mathscr{F}$ are called ...
1
vote
0answers
43 views

Cantor set countable? [duplicate]

I know the Cantor set is uncountable, but I just came with an argument that shows it is countable. Obviously my argument is wrong, but I just don't know where is the mistake. Here it is. Let $C$ be ...
0
votes
3answers
42 views

Showing that $S_1 \cup S_2$ is countable [duplicate]

Let's say that $S_1$ and $S_2$ are two countable infinite sets that are disjoint (i.e. $S_1 \cap S_2 = \emptyset$). How would you show that $S_1 \cup S_2$ is also countable?
3
votes
2answers
73 views

$x=x^2$ in a sub group?

I have a set E defined in ℝXℝ (E=ℝXℝ) and the operation * defined like this ...
0
votes
0answers
20 views

Equivalence relation find cardinality of quotient set

At $A=\mathbb{Z}^{\mathbb{N}}$ we define equivalence relation $\equiv$ $f\equiv g \iff \forall n\in \mathbb{N} ((f(2n)=g(2n)) \wedge(f(n)\cdot g(n)> 0 \ \vee f(n)=g(n)=0)) $ a)find cardinality ...
1
vote
2answers
38 views

Prove/disprove $A\cap B=A\cap C $ for every $A$ $\iff B=C$

Let $A,B,C$ be sets, prove/disprove: $A\cap B=A\cap C $ for every $A$ $\iff B=C$ I think it's wrong, choose $A=\{1,2\}, B=\{2,3\}, C=\{2,4\}$ so $A\cap B=A\cap C$ but $B\neq C$ Although it's a ...
4
votes
1answer
52 views

Rudin Ex 2.2: Proving countability of algebraic numbers with the hint

NOTE: I know that countability of algebraic numbers has been proven on this site before, but I'm concerned about this specific hint they give and I don't know how to prove it using that advice. I am ...
0
votes
2answers
48 views

Every infinite set has an infinite countable subset?

As the title says, that's all my question. Let me state it again: Is it true that every infinite set has an infinite countable subset? It seems so trivial, my thought goes like this: pick an ...
1
vote
0answers
22 views

Proving with a given definition that if $|A|=|B|$ then $A,B$ are equivalent (with induction but without using the induction hypothesis)

Let $A,B$ be finite sets, we'll say the sets are equivalent if $|A\setminus B|=|B\setminus A|$. Prove with the above definition that if $|A|=|B|$ then $A,B$ are equivalent. Suppose ...
0
votes
1answer
25 views

$G_1\cup G_2\setminus F_1\cup F_2\subset (G_1\setminus F_1)\cup (G_2\setminus F_2)$

How to show that $(G_1\cup G_2\setminus F_1\cup F_2)\subset (G_1\setminus F_1)\cup (G_2\setminus F_2)$ where $G_1,G_2$ is open and $F_1,F_2$ is closed Hints would be welcome!
0
votes
0answers
20 views

Proving bijection of a function of the form f(x,y).

I am trying to prove that the function $f:\mathbb{R}^2\rightarrow \mathbb{R}^2$ defined by $$f(x,y) = ((x^2+1)y, x^3)) $$ is bijective. I know that to prove a function is bijective we have to prove ...
2
votes
2answers
20 views

Power set of a set containing a set

I need some help understanding this concept a little better. I understand the general power sets, but only worked nice and easy examples where only the set consisted of only single elements like ...
1
vote
1answer
14 views

How can I find line segment connecting two vectors?

Let $S$ be a subset of $\mathbb{R}^n$. it is called convex if for all pairs of $a$, $b$, line segment from $b$ to $a$ is element of $S$. And it is given that $at+(1-t)$ is line segment between two ...
1
vote
2answers
26 views

Proving if $A$ or $B$ are symmetric then $AB$ is symmetric

Prove if $A$ or $B$ are symmetric then $AB$ is symmetric. Symmetric set definition: $A$ is symmetric if for every $a\in A$ there's $-a\in A$ Product set definition: $AB=\{ab\mid a\in A, ...
0
votes
1answer
18 views

Union and Intersection of sets proofs

So I am learning about proving intersection and union statements of sets, but the problem is I am never confident about my proofs, I never know when I am right. So if you could check my attempt, and ...
1
vote
1answer
27 views

One problem on set theory having two parts

Problem: Let $S$ be a universal set and $A$ be a fixed subset of $S$. If $A\cup B = B$ holds for all subset $B$, prove that $A = \varnothing$, If $A\cap B= B$ holds for all subset $B$, ...
1
vote
1answer
23 views

Determining if a function is one-to-one or onto.

We have two sets: {1,2} and {a,b,c}. How would I go about listing the functions between these two sets and then identifying if those functions are either one-to-one or onto? Would the functions be ...
1
vote
2answers
48 views

How to prove that $A × (B ∩ C) = (A × B) ∩ (A × C)$?

I have to prove that $A × (B ∩ C) = (A × B) ∩ (A × C)$. While I know this is true by thinking about it I'm having a lot of trouble actually writing the proof. I'm relatively new to proofs so I have a ...
1
vote
2answers
44 views

Proving if $|A|\ge 4 \vee |A|\le 2$ then $|A+A|\neq 4$ with direct, contradiction and contraposition

Prove if $|A|\ge 4 \vee |A|\le 2$ then $|A+A|\neq 4$. $A$ is some set and we define $A+B=\{a+b|a\in A, b\in B\}$, $A$ is some subset of the reals. In a direct proof and proof by contradiction I'd ...
1
vote
1answer
44 views

Clarification about the ZFC's axiom 0.

Let's consider the "axiom 0" of ZFC: $\exists x (x=x)$ I "think to" it as "there exist something which is equal to itself, in other words there exist at least something". But on the notes where I ...
-1
votes
1answer
167 views

Am I solving this question correctly?

How can I evaluate the following term: $$\left((\{a,b\}\cup\{b,a\})\times(\{b,a\}\cap\{a,b\})\right)\setminus \left((\{b,a\}\setminus\{a,b\})\cup(\{a,b\}\times\{b,a\})\right)$$ You can see the notes ...
0
votes
0answers
9 views

Equation to denote a set based on probabilities

I have a set R with elements r. Each element has a certain probability P(r|X). Now a want a formal equation/notation for a new set E which contains the expected r elements when X happens. I can't ...
-1
votes
0answers
27 views

Am I doing the Cartesian product of sets correctly?

Question in the image and how I attempt to solve it. Did I do it correctly? And is that the right answer?
1
vote
0answers
16 views

How to determine how many subsets of a set contain a particular element? [duplicate]

Let's say set A contains 500,000 elements. Inside set A, there is a particular element, which we will call x. How do I go about finding the number of subsets of A that contain x?
0
votes
2answers
41 views

Show that if $F = \emptyset$, then the statement $x\in\bigcap F$ will be true no matter what $x$ is

Show that if $F = \emptyset$, then the statement $x\in\bigcap F$ will be true no matter what $x$ is I know that $x\in\bigcap F = \forall A \in F, x\in A$ But how can $x$ be in any set, much less ...
0
votes
0answers
11 views

Cardinality of Cartesian product involving empty sets [on hold]

What is the cardinality of Cartesian product of two sets A and B when 1) both A and B are empty sets 2) One of A or B, is empty set
0
votes
3answers
30 views

Proof of intersection and union of Set A with Empty Set

I need to prove the following: Prove that $A\cup \!\, \varnothing \!\,=A$ and $A\cap \!\, \varnothing \!\,=\varnothing \!\,$ It's my understanding that to prove equality, I must prove that both are ...
0
votes
3answers
30 views

f injective, g injective, $f\circ g(a) = a$ implies $f$ bijective

We have a function $f:A \to B$ such that $f$ is injective. We have a function $g:B \to A$ such that $g$ is injective. From the Schroeder-Bernstein theorem ...
1
vote
1answer
28 views

intersection of infinite collection of finite sets?

I know that there are questions asking like "intersection of a infinite collection of sets" and I can understand that the answer for that one is a null set, but I got a question here, in which all ...
1
vote
2answers
28 views

Union and Intersection

I am trying to compute the intersections and unions of the following sets ... $A={x:x\in \mathbb{N}\ \text{and x is even}}$ $B={x:x\in \mathbb{N}\ \text{and x is prime}}$ $C={x:x\in \mathbb{N}\ ...
1
vote
1answer
77 views

Definition of the sum of natural numbers

After define the natural numbers using the Peano axioms, I'm trying to understand the definition of sum between natural numbers, let $s$ be the successor function used in the Peano axioms. The most ...
1
vote
1answer
19 views

Is an irreflexive and transitive set an anti symmetric set?

I have read that a simple ordered set is a total ordered set which is irreflexive and transitive. I want to know if irreflexivity and transitivity implies antisymmetry?
0
votes
1answer
28 views

Proving something is an equivalence relation

Problem: For two subsets $A$ and $B$ of some set $X$, we define \begin{align*} A \triangle B = (A \cup B) \setminus (A \cap B). \end{align*} We now define a relation $R$ on $P(X)$ (power set of $X$) ...
1
vote
0answers
29 views

Meaning of superscript following brackets in set definition

What does the $n$ mean in this set? $U = \{0,1\}^n$
2
votes
2answers
40 views

Show that the set of all cofinite subsets of S is enumerable.

I've been having some trouble with this question. In fact, I spend a long time on a solution which I came to realize the next day it was entirely wrong. I feel completely stumped, and I could really ...
0
votes
3answers
47 views

Prove $\overline{B} - (A-\overline{B}) \subseteq \overline{B}$

Prove $\overline{B} - (A-\overline{B}) \subseteq \overline{B}$ Attempt: Let $x \in \overline{B} -(A-\overline{B})$, then $x \not\in \overline{B} \land x \not\in (A-\overline{B})$. Then by By ...
0
votes
1answer
68 views

Can Aleph Numbers be multiplied?

i.e., does it make sense to say something like $(2 * \aleph_0) > \aleph_0$ ? The original question I was thinking about is: if A = $\mathbb{Z}$ and B = {the set of even integers} is it correct to ...
1
vote
1answer
64 views

$S = \{n: n \text{ is an integer and } n=n^n\}$

Let $S = {n: n \text{is an integer and} n= n^n}$. What elements are in $S$? I thought simply $1$ and $0$ but I'm not sure if $-1$ is since $-1$ only works sometimes.
0
votes
3answers
41 views

Principles of Topology: Operations on Sets: Union, Intersection, and Difference

I have been stuck on the following set of questions for some time now: Let $X$ be a set with subsets $A$ and $B$. Prove the following: (a) $X\setminus(X\setminus A) = A$. ...
0
votes
1answer
46 views

Elementary Operations on Sets

Let $X$ be a set with subsets $A$ and $B$. Prove: a). $X \setminus (X \setminus A) =A$. $X \setminus A$ is the set of all points of $X$ which do not belong to $A$. Given $p \in X$, we will show that ...
0
votes
1answer
27 views

What is the cardinality of a set of all finite subsets of $\Bbb{N}$? [duplicate]

I'm looking for cardinality of $P_{fin}(\Bbb{N})=\{x|x\subset\Bbb{N}$ and $x$ finite$\}$. I was told in my classes that it's $\aleph_0$, but how to prove it?
11
votes
6answers
1k views

Is there a notation for being “a finite subset of”?

I would gladly use a notation for "A is a finite subset of B", like $$A\sqsubset B \text{ or } A\underset{fin}{\subset} B,$$ but I have never seen a notation for that. Are there any? While ...
0
votes
0answers
44 views

Can number 2 be a particular instance of set membership relation? [on hold]

I have found some definitions of numbers in set theory, such as von Neumann's, Zermelo's, Frege-Russell's, and Cantor's (see e.g. this video https://www.youtube.com/watch?v=6UWhPnbZv-o&sns=fb). ...
0
votes
3answers
33 views

How to prove the equivalence relation $A\cup B=B \Leftrightarrow A\cap B = A$? [on hold]

How to prove the equivalence relation? $$A\cup B=B \Leftrightarrow A\cap B = A$$
0
votes
1answer
26 views

Proving the existence of a Bijection between Cartesian Products of Sets by Induction

Prove by induction that for any sets $A_1, \ldots , A_n$, there is a bijection from $(((A_1 \times A_2) \times A_3) \times \ldots \times A_n)$ to $A_1 \times (A_2 \times ( \ldots (A_{n-1} \times A_n) ...
1
vote
1answer
37 views

Showing that the class of all sets of a particular cardinality is not a set.

How to show that the class of all sets of a particular cardinality ,say $h$ is not a set. My argument: I assume that I've shown the following lemma. Lemma: If $X$ is an infinite set of cardinality ...
0
votes
1answer
59 views

A version of Zorn's lemma

The version of Zorn's lemma that I have found more often is Zorn's Lemma (1) If every chain belonging to the partially ordered set $S$ has an upper bound in $S$ then $S$ contains a maximal ...
-2
votes
1answer
34 views

Question about Aaronson Scott Quantum Computing Since Democritus

In the chapter on sets: Equality rules: $x=x, x=y$ implies $y=x, x=y$ and $y=z$ implies $x=z$, and $x=y$ implies $f(x)=f(y)$ are all valid. where $f$ is a function. But how do we know for ...
0
votes
1answer
9 views

Manipulating the definition of $\sigma$-algebra generated by a family of sets

I manipulated the standard definition of $\sigma$ algebra generated by a family of sets $\mathcal{A}$, $$ \sigma ( \mathcal{A}) := \bigcap \{ \Sigma \ | \ \Sigma \text{ is a $\sigma$-algebra on } X, ...
0
votes
1answer
13 views

Cantor Set and Base 3 Decimal Expansions

I'm trying to show that every point in the Cantor Set (obtained by "middle-thirds" removal, starting with $[0,1]$) has a base 3 decimal expansion consisting of only zeros and twos. I think the proof ...