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
28 views

Am I solving this question correctly?

Am I solving this question correctly?
0
votes
0answers
3 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 ...
0
votes
0answers
13 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
14 views

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

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
34 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
7 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
20 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
29 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
27 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
27 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
63 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 ...
0
votes
0answers
13 views

Proving $A_i=B_i$ (Set theory)

Suppose that $P$ is a probability on a field $F$. Consider three events $A_1,A_2,A_3 \in F$ so that $P(A_i \cap A_j) = 0$ for all $i ̸\ne j$. Let $B_1 = A_1, B_2 = A_2 \cap A^c_1$ and $B_3 = A_3 \cap ...
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
28 views

Meaning of superscript following brackets in set definition

What does the $n$ mean in this set? $U = \{0,1\}^n$
2
votes
2answers
35 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
46 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
62 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
63 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
39 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
42 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
26 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
40 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
25 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
35 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
57 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
11 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 ...
-2
votes
1answer
37 views

Functions : Injective, surjective or bijection? [on hold]

I have been asked a question in one of my test. Question : Consider the relation R is a subset of X * Y where X = [a, b] and Y = [c, d] defined by R = {(x,y): x^2 + y^2 = 1}. For each of the ...
0
votes
2answers
24 views

Help with proof about functions and subsets

Problem: let $f: A \rightarrow B$. Prove that $f$ is injective if and only if for all $D \subset A$ we have that $f^{-1}(f(D)) = D$. Proof: => Suppose $f$ is injective. Let $x \in f^{-1}(f(D))$. ...
0
votes
0answers
17 views

Symbol Identification related to set-theory and graph theory

If $A$ is a set of vertices of a graph $G$ where $A=\{V_1, V_2, V_3,V_4... V_N\}$, then what is the meaning of symbol $|A|$ ? I encountered this problem when I was reading a paper related to directed ...
-4
votes
1answer
33 views

Use De Morgan's Laws to simplify the following sets

Simplify the following sets: $$ℝ\setminus \bigcap\limits_{n=1}^∞ (-1/n,1/n)\tag1$$ $$\bigcup\limits_{n=1}^∞ (ℝ\setminus[1/n,2+1/n])\tag2$$ For the first problem, I used De Morgan's law, and it ...
2
votes
1answer
66 views

How can we construct a $1-1$ correspondence between $(0,1$) and $\mathbb{R}$ that transform irrationals into irrationals and rationals into rationals?

This is an exercise in "Elements of set theory by Enderton". I can construct a function from the rational unit interval into rationals easily. So, If I can find a $1-1$ correspondence from real unit ...
0
votes
1answer
31 views

Cardinality of the set of all (real) discontinuous functions

This is a question from the book Introduction to Set Theory (Hrbacek and Jech), chapter 5, question 2.6. (Show that) The cardinality of the set of all discontinuous functions is ...
2
votes
1answer
30 views

Cardinality of sets: $|A|\le|B|\Rightarrow(|A\cup B|=|B|\land|A\times B|=|B|)$

My book of mathematical logic states the facts that, if we call $|X|$ the cardinality of set $X$, then, for any two sets $A,B$ such that $|A|\le|B|$, $$|A\cup B|=|B|\quad\text{ and }\quad|A\times ...
1
vote
0answers
13 views

Calculate cardinality of 8-digit strings composed of zeros and ones

How can i calculate cardinality of a set made of 8-digit strings composed of zeros and ones? In general, assuming that digits can repeats. My attempt Let $D$ be the domain composed only by one or ...
3
votes
1answer
56 views

Relationship between increasing integer sequences

Suppose that $\mathcal X\cap \mathcal Y=\emptyset$, that $\mathcal X\cup \mathcal Y=\Bbb N$ and that $X(n),\;Y(n)$ are increasing surjections $\Bbb N\to \mathcal X$ respectively $\Bbb N\to \mathcal ...
0
votes
3answers
40 views

Help me with proof concerning functions

Problem: Let $X$ and $Y$ be non-empty sets and let $f: X \rightarrow Y$ be a function. We define $F: P(Y) \rightarrow P(X)$ by $F(B) = f^{-1}(B)$ for all $B \in P(Y)$. Proof that $F$ is injective if ...
2
votes
1answer
34 views

Are $((0,1]\cap\mathbb Q)\times\mathbb Q$ and $\mathbb Q \times([0,1)\cap\mathbb Q)$ order isomorphic?

The ordering here isn't specified but I assume it's lexicographic. I think the answer is yes. My reasoning is the following: Neither sets have a least or a greatest element because the second ...
0
votes
2answers
21 views

Equivalence Relations and 1-1 Correspondences

I have an engineering instructor who has claimed that "equivalence relations and one-to-one correspondences are pretty much the same thing". However, I believe the answers to both of the following ...
1
vote
0answers
37 views

Universal set for linearly ordered sets of given cardinality

It is easy to see that every infinitely countable linearly ordered set embeds into Q (rational numbers) with its linear order.("Linear order"="total order". All embeddings are assumed to preserve ...
-1
votes
1answer
26 views

Is every point of rational number boundary point?

While studying first chapter of multivariable calculus, I am wondering if every point of the rational number is boundary point. It is obvious that $\Bbb{R}^n$ is the union of interior, exterior, ...
0
votes
2answers
39 views

The powerset of the set of natural numbers - Cantor's Theorem

It is a fact that if $A$ is any set then there is no bijection between $A$ and its powerset $P(A)$. If $A$ is finite, this is pretty clear just by looking at the sizes of $A$ and $P(A)$. But if I ...
1
vote
2answers
25 views

For every set $A$, there exists a well ordered set $V$ such that there exists no surjection $\pi: A \rightarrow V$.

I am proving that for every set$ A$, there exists a well ordered set $X$ such that there exists no surjection $\pi : A \longrightarrow V$. I think that's very simple, and so I think maybe I made some ...
-4
votes
3answers
67 views

Does there exist a function between arbitrary sets?

Given arbitrary sets $A$ and $B$, does there exist a function $f: A\rightarrow B$ that is injective?. Does this follow from the axioms of set theory? If yes, then which axiom?
0
votes
0answers
11 views

Can the direction of failing distributivity on ordinals be turned into an inequality?

Is it true that for all ordinals $\alpha_1, \alpha_2, \beta$: $$(\alpha_1 + \alpha_2)\cdot\beta \leq \alpha_1\cdot\beta+\alpha_2\cdot\beta\;?$$
0
votes
1answer
20 views

What is the universe of a sub algebra generated by $ \{(a \wedge b)\vee(c \wedge b') : a,c \in C\}$ ?

I need to prove the next thing, Let $B$ be a Boolean algebra and $C$ a proper subalgebra of $B$. Let $b ∈ B−C$. Prove that the set $ \{(a \wedge b)\vee(c \wedge b') : a,c \in C\}$ is the universe of ...