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
3answers
37 views

Set equality comparison of union

I was reading an introductory set theory book and came across the following question. Give an example where $A \cup B = A \cup C$, But $B \ne C$. I am lost. Any ideas?
-2
votes
1answer
55 views

Does $2$ belong to $\{1, \{2, \{3\}\}\}$?

$2$ belongs to $\{1,\{2,\{3\}\}\}$ State true or false. I don't know how to write all the subsets of this set and also to check if $2$ belongs to the given set. Please help.
1
vote
0answers
19 views

Measuring the difference in two sets of numbers

I have multiple sets of numbers considered prediction and then a final set called the result. I would like to have a measurement of the difference between each prediction and the result. Obviously, ...
1
vote
1answer
24 views

Terminology help for a set relation: for sets $X, Y$, not necessarily disjoint, such that neither is a subset of the other.

Is there an existing term for pairs of sets $X, Y$, not necessarily disjoint, such that neither $X \subseteq Y$ nor $Y \subseteq X$? Would it be incorrect (or misleading) to call them something like ...
6
votes
2answers
581 views

Olympiad question on Pigeonhole principle

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $26$, prove that $M$ contains at least one subset of four distinct elements, whose product is ...
1
vote
1answer
502 views

Is this enough for a set to be countable?

Given set $\mathcal{P}$ of subsets of a countable set $X$. For each $A, B \in \mathcal{P}$ it is given that $A \subset B$ or $B \subset A$. Does it follow that $\mathcal{P}$ is countable itself?
1
vote
1answer
27 views

When will $A_1^c \Delta A_2^c = (A_1 \Delta A_2)^c$ holds?

I tried many cases but all failed. I thought because $$A_1 \Delta A_2 = A_1^c \Delta A_2^c,$$ so that the question is really asking $$A_1 \Delta A_2 = (A_1 \Delta A_2)^c.$$ Can I say it will never ...
0
votes
1answer
36 views

Using the well ordering principle to prove a certain property of an integer

The Well ordering principle states that A least element exists in every non empty set of positive integers Use the well Ordering principle to prove the following statement ' Any nonempty subset of ...
1
vote
1answer
44 views

How to prove generalized DeMorgan's Law? [duplicate]

How to prove generalized DeMorgan's Law that $$\neg(A_1 \land A_2 \land \cdots \land A_n) = \neg A_1 \lor \neg A_2 \lor \cdots \lor \neg A_n.$$ Or in the set theory language, $$\Bigg(\bigcap_{i\in ...
0
votes
0answers
27 views

Bijectivity of the Inverse of a Bijection

If $f:A\to B$ is a bijective mapping, is $f^{-1} : B\to A$ also bijective? Can you also give a detailed proof?
1
vote
1answer
31 views

Calculate the cardinal of $\{f:\Bbb{N}\to \mathcal{P}(\Bbb{N}):n \notin f(n)\}$

Calculate the cardinal of $A=\{f:\Bbb{N}\to \mathcal{P}(\Bbb{N}):n \notin f(n)\}$. Ok, so I'm having some trouble with this problem. I know that since $A\subset \{f:\Bbb{N}\to \mathcal{P}(\Bbb{N})\}$ ...
0
votes
0answers
38 views

How to compute and compute the follow questioners about () and []

Compute the intersection of all sets of the form $(0, b)$, for $b$ a positive real number Compute the union of all sets of the form $[a, 1]$, for $a$ a positive real number Really don't know how to ...
0
votes
1answer
35 views

A bijection $f:\mathcal{A} \to \mathcal{B}$, where $\mathcal{A} \subset \mathbb{R}^n, \mathcal{B} \subset \mathbb{R}^k$, and $k <n$?

The motivation for this post is the question of whether or not there exists a class of functions which are bijections between vector spaces of differing dimensions. Although it is simple enough to ...
1
vote
1answer
26 views

Simple Set Operation with Random Variable

Consider $X(\omega) \ge -1$ be a discrete random variable and define an event $$ \{\omega: 1+a X(\omega) \le \varepsilon\} $$ where $a \in [0,1]$ and $\varepsilon \in [0,1]$. I was wondering ...
0
votes
2answers
35 views

Proof that for subsets $A$ and $B$ of a metric space $(X,d)$ that $(A \cap B)^{\circ} = A^{\circ} \cap B^{\circ}$

Where the circle is the interior of the set. It seems quite trivial but I cannot find a direct proof for this: $(A \cap B)^{\circ} = A^{\circ} \cap B^{\circ}$. Would this also imply that $A^{\circ} ...
2
votes
4answers
123 views

$|\mathbb N^{\mathbb N}| = |2^\mathbb N|$

I was trying to find a direct proof that $|\mathbb N^{\mathbb N}| = |2^\mathbb N|$, by finding a bijection between the two sets. The idea that came to mind was to start with the sequence of natural ...
2
votes
3answers
71 views

How to prove $A=(A\setminus B)\cup (A\cap B)$ [duplicate]

How to prove $A=(A\setminus B)\cup (A\cap B)$. I have seen this problem and the solution is clear to me. Initially I was satisfied by my prove but now I think it is wrong. How I have proved ...
4
votes
3answers
738 views

Does same cardinality imply a bijection?

This came up today when people showed that there is no linear transformation $\mathbb{R}^4\to \mathbb{R}^3$. However, we know that these sets have the same cardinality. I was under the impression ...
2
votes
1answer
73 views

order of infinite countable ordinal numbers

I'm trying to understand ordinal arithmetic. If one had an ordered list of the some subset of countable ordinal numbers, what order would the following 6 countably infinite ordinals be in? If the ...
0
votes
1answer
12 views

Question on M-generic filter

Let B a complete boolean algebra and $b, c\in B$ and M a model of ZFC. Why do we have that if $c\in G\,\, \forall G$ M-generic ultrafilter such that $b\in G$ then $b\le c$ ?
1
vote
1answer
16 views

Simple question on predense set in a boolean algebra

Let B a complete boolean algebra and D a subsets of B. Then D is predense below $ b\in B $, i.e. the downward closure of D is dense below b, iff $b\le \bigvee D$.Proving this equivalence seemed like ...
1
vote
1answer
79 views

The value of limsup and liminf of a sequence of a sets obtained by combining three sequences

What is the limit superior of the following sequence of sets? $\{X_n\}=\{\{1/2\},\{1/3\},\{1/4\},\{2/3\},\{1/3\},\{1/5\},\{3/4\},\{1/3\},\{1/6\}......\}(n\to∞)$ I.e., $X_1=\{1/2\}, X_2=\{1/3\}, ...
1
vote
1answer
81 views

Let U be a universe. Use an element argument to prove the following statement. For all sets A and B in P(U), (A ∩ B)⊆(A U B).

I am currently stuck attempting this question. The only way I know how to solving this question is simply via (A ∩ B)⊆A and A⊆(A U B). Therefore (A ∩ B)⊆(A U B). However, as mentioned in the question ...
1
vote
2answers
30 views

When is the inverse of a reciprocated function equal to the function?

If $f(x)=f(-\frac{1}{x})$, are there finite or infinite solutions for this? Can we tell? Thank you very much.
2
votes
1answer
58 views

On the equality of two sets (a doubt from Probability with Martingales).

Let $(S, \Sigma, \mu) $ be $([0,1], \mathcal{B}[0,1], Leb)$. Let $\epsilon(k)$ be a sequence of strictly positive numbers s.t. $\epsilon(k) \downarrow 0$. Let $V = Q \cap [0,1],$ the set of rationals ...
3
votes
0answers
61 views

How can functions be written as ordered triples?

In a function $ \langle f,A,B \rangle $, I know that the domain $ A $ and the co-domain $ B $ are not restricted to being sets. They can be proper classes. In that case, how can we write functions as ...
-1
votes
3answers
72 views

Show that there exists a bijection from a sets that is countable and infinite into natural numbers.

Show that there exists a bijection from a sets that is countable and infinite into natural numbers. I know that this question is a bit dumb but I can't prove it explicitly. I mean I can't ...
2
votes
1answer
24 views

Question about boundary of set defined by a polynomial

Suppose $p(z):\mathbb{C}\rightarrow\mathbb{C}$ is is a polynomial of degree $n$. Define $M=\{z\, |\, \text{Re}\,p(z)<0\}$. Why is $\partial M=\{z\, |\, \text{Re}\,p(z)=0\}$? I have only read some ...
1
vote
1answer
27 views

negation of a null sequence

I have that a sequence $\{a_n\}$ is null $\Leftrightarrow \forall \epsilon >0, \exists X$ such that $$|a_n| < \epsilon \ \forall n > X.$$ I want to give a definition when a sequence is not ...
2
votes
1answer
23 views

The Union of $n$ Independent Events Equals the Complement of the Complement of Their Product

The Statement of the Problem: If the events $A_1,...,A_n$ are independent, show that $$ P\left(\bigcup_{i=1}^n A_i \right) = 1-\prod_{i=1}^n P(A_i^c) .$$ Where I Am: So, I've seen this equality ...
0
votes
3answers
95 views

Prove that rational numbers (not just positive) are countable without using axiom of choice.

Prove that rational numbers (not just positive) are countable without using axiom of choice(since it is controversial). I have seen proofs that use the fact that union of countable sets is countable, ...
0
votes
4answers
58 views

Proving that $A\setminus B\subseteq C$ implies $A\setminus C\subseteq B$ .

Theorem. Suppose $A, B$, and $C$ are sets, and $A\setminus B\subseteq C$. Then $A\setminus C\subseteq B$ . What I tried Proof: My try: From the statement $A\setminus C\subseteq B$ We ...
0
votes
2answers
23 views

Proving a set releation

Theorem:Suppose $A$, $B$, and $C$ are sets, $A\setminus B ⊆C$, and $x $ is anything at all. If $x ∈ A\setminus C$ then $x ∈ B$. Proof: Suppose $x ∈ A\setminus C$.This means that $x ∈ A$ and $x\notin ...
1
vote
1answer
69 views

constructions of terms using variable

It is usually said given set of variables, terms of language are defined recursively. But for recursive definition on a set, we need a function p which assigns to each function from a section of ...
5
votes
2answers
345 views

Impossible numbers drawn from tricky function

The function is this: $f(\frac{a}{b},\frac{c}{d})=\frac{a+c}{b+d}$ where $0\lt \frac{a}{b} \lt 1$ $0\lt \frac{c}{d}\lt 1$ $a,b,c,d$ are all integers $a/b$ and $c/d$ are in lowest terms Are there ...
2
votes
3answers
83 views

Proof of recursion theorem

I was going through a real analysis textbook The Real Numbers and Real Analysis this morning, and I encountered a theorem stating that: Let $H$ be a set, let $e\in H$ and $k:H\rightarrow H$ be a ...
2
votes
2answers
139 views

substituting a variable in a formula (in logic)

What kind of mathematical object is this substitution(is it a function or what). We assuming set of variables exist.
1
vote
2answers
21 views

Partition of at most countable set is at most countable set

Let $X$ be any at most countable set. I have to prove that partition of at most countable set is at most countable set. It seems bvious, but I need formal proof. Let $\{S_i\}_{i\in I}$ be partition ...
0
votes
2answers
52 views

Set Theory (Example of Set)

A set is defined as the collection of well-defined and distinct objects. Now if we consider the collection of identical glasses, can we call that collection as a set? But I am confused that since all ...
1
vote
3answers
65 views

Exercise 1 on page 10 in Naive Set Theory, following Axiom of Pairing

In Section 3 "Axiom of Pairing" in Naive Set Theory on page 10 Halmos proposes the following argument. "Consider the sets $ \emptyset , \lbrace \emptyset \rbrace , \lbrace \lbrace \emptyset \rbrace ...
-1
votes
2answers
84 views

The range of the function $f(x,y)=(x+y,xy)$

I have the following homework question: $$\begin{split} f: \mathbb I \times \mathbb I &\to \mathbb R\times \mathbb R\\ f(x, y) &=(x+y, xy)\end{split}$$ Does there exist $(x, y) \in \mathbb ...
-1
votes
2answers
39 views

Set Theory Proof $A=B$ [closed]

Let $A$ be the set of all integers $x$ such that $x = 2k$ for some integer $k$ Let $B$ be the set of all integers $x$ such that $x = 2k+2$ for some integer $k$ Give a formal proof that $A = B$.
3
votes
1answer
35 views

Size of Totally Ordered Set with Countable Predecessors

Assume Choice. Let $S$ be a set, and $\trianglelefteq$ be a total order on $S$. If for all $s \in S$, the set $\{t:t\trianglelefteq s\}$ is countable, what are the possible cardinalities of $S$? ...
0
votes
2answers
56 views

How do I write this set notation correctly?

I have a 2D matrix $f(m,n)$, where $1<m<M$ and $1<n<N$. The element at location $(m,n)$ is denoted as $f_{m,n}\in \{+1,-1\}$. I want to write something like set notation but I am not ...
0
votes
0answers
24 views

Prove/Disprove existence of a set [duplicate]

I would like to know if my arguments are correct. Prove/Disprove existence of a set X $\subset$ P($\mathbb{N}$) , $ |X|=\aleph$ and for every $ A,B \in X $ ,$ A \subset B $ or $ B \subset A$ I ...
1
vote
1answer
28 views

Let $R$ be an equivalence relation: How many elements are in $R$?

Let $R\subset X\times X, |X|=30$. Supposing there are only 3 distinct equivalence classes and all of these have the same amount of elements, find $|R|$. I didn't get very far on this, I thought that ...
1
vote
4answers
219 views

$\{∅\} ∈ \{∅\}$ is this right or wrong?

I am very confused about whether $\{∅\} ∈ \{∅\}$ or not. I thought it's right because in curly brackets the phy is also a member. Can anyone help me understand this?
2
votes
1answer
34 views

Manipulating sets ($+$, etc).

I was seeing a proof of the Open Mapping Theorem, in Kreyszig's book, and I have no problems with it. But there's a point in which he does something like: $$\begin{align}B_Y(0,r) \subset ...
1
vote
2answers
35 views

Comparison of two collections of 4-tuples using combinatorics - more complicated version

My problem is to show that 2 collections of unordered 4-tuples - $\mathbf{A}$ and $\mathbf{B}$ - are the same. I define a collection of objects as a set, in which multiple entries of the same object ...
6
votes
2answers
226 views

Showing a function is invertible

I came across this problem and not sure how to prove it. Show that if $ f\circ f \circ g\circ g \circ f\circ f $ is invertible then $ g $ is invertible. I'm not sure if it's correct to say that ...