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
17 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
18 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
13 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
22 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
16 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
19 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 ...
0
votes
2answers
32 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
39 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
38 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 ...
-2
votes
1answer
129 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
26 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
9 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
29 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
64 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
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
39 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
40 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
43 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
41 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
36 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
12 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
38 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
18 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
35 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
67 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 ...