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

2
votes
2answers
188 views

Can Zorn's Lemma be 'inverted' like this:?

Let $R$ be a (commutative) ring not equal to $0$. I want to show that the set of prime ideals of $R$ has a minimal element w.r.t. inclusion. This may be a wholeheartedly wrong attempt, but I thought ...
2
votes
1answer
35 views

How to pick decimal expansion in the proof that $(0,1)$ uncountable

Prove $(0,1)$ is uncountable. Suppose $(0,1)$ were countable. List $(0,1)$ as: $x_1=0.a_{11}a_{12}\dots$ $x_2=0.a_{21}a_{22}\dots$ and so on, where $a_{ij}$ are integers from $0$ to $9$. ...
1
vote
1answer
33 views

Relationship between $S$ and $S^{-1}$

This is one of the problem I have been solving in Velleman's How to Prove book: Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$. Prove that if $R$ is symmetric, ...
3
votes
2answers
21 views

Empty conditional

I have the following set $$M_{\delta} = \{x\in\mathbb{R}^n\mid x_i\ge1,i=1,\ldots,n,x_j\le 1+\delta , j\in\varnothing\}$$ and I'm not sure how to evaluate it. There is no such $j$ such that the empty ...
2
votes
5answers
39 views

$A\backslash (B\cap C) = (A\backslash B)\cup (A\backslash C)$; only one inclusion seems to work

I encountered the following problem: $$A\backslash (B \cap C) = (A\backslash B)\cup(A\backslash C).$$ So I need to prove two things: $A\backslash (B\cap C) \subseteq (A\backslash B) \cup ...
-4
votes
0answers
24 views

Sets and ordering sets [on hold]

Let $n=10^{10^{1000000000000}}$. It then holds $n<{2n \choose n}$<$2^{2n}$
-2
votes
1answer
20 views

A,B,X,Y are sets.. when is $X^Y \leq A^B$?

Let A,B,X,Y be sets with $X \leq A$ and $Y \leq B$. Prove that, apart from some exceptional cases, $X^Y \leq A^B$. What are the exceptional cases?
1
vote
2answers
22 views

Intersection of elements of a union

I am working on a proof where I would like the following identity to hold. $$\bigcap_{w \in \bigcup_{i \in \mathbb{N}} W_i}w = \bigcup_{i \in \mathbb{N}} \bigcap_{w \in W_i} w,$$ where $w$ are sets ...
1
vote
1answer
11 views

Characteristic function of a disjoint union

I just could not convince myself about what $\chi_{\cup_{A_n}}$ is worth, if $(A_n)$ is a sequence of pairwise disjoint sets? Is it equal to the series $\sum_{n=1}^{\infty}\chi_{A_n}$? We need to ...
-1
votes
1answer
28 views

Doubt with Intervals and Inequalities

This doubt has been bothering me for ages. I would be truly grateful for any help. Problem 1: $\dfrac{2}{|x-4|}>1$ Express the solutions using intervals Solution: $x\in(2,4)\cup(4,6)$ ...
1
vote
1answer
20 views

Inverse of a set of ordered pairs.

An exam ask me the following question. Let $r=\{(x,y) \ | \ x \in [-1,1] \ \text{and} \ y=x^2\}$, is the following statement true? $$r^{-1}=\{(x,y) \ | \ x \in [0,1] \ \text{and} \ y=\pm\sqrt{|x|} ...
-1
votes
0answers
17 views

The elements in set $\Bbb Z$ under ordinary addition has infinite order [on hold]

For elements, $g$, in a set with ordinary addition operation defined on the set, the order of any element in the set, denoted $|g|$, is the smallest positive integer, $n$, such that $n\times g=0$. For ...
0
votes
1answer
78 views

Why does $\bigcap_{m = 1}^\infty ( \bigcup_{n = m}^\infty A_n)$ mean limsup of sequence of set?

Why does $\bigcap_{m = 1}^\infty ( \bigcup_{n = m}^\infty A_n)$ mean the limit superior of sequence of set? I'm not getting it. ${A_n}$ is a sequence of set in $S$. I do know what limsup means ...
1
vote
5answers
59 views

Is the Cartesian product of two uncountable sets uncountable? [duplicate]

Is Cartesian product of two uncountable sets uncountable? Suppose we have a set of real numbers $R$, Can't it be shown that $R$ is uncountable by Cantor's diagonalization method, so it follows that ...
0
votes
3answers
43 views

Is a relation from a set $A$ to a set $B$ always a proper subset of $A\times B$?

Is a relation from a set $A$ to a set $B$ always a proper subset of $A\times B$? Or, is it possible that the relation covers the entire set $A\times B$?
0
votes
2answers
26 views

Equivalence: Injective function from natural numbers to a set $X$, and injective but not surjective function from $X$ to $X$

How do I go about proving the equivalence of these statements? (1) There is an injective function $f: \mathbb{N} \rightarrow X$ (2) There is an injective but not surjective function $g:X \rightarrow ...
6
votes
1answer
145 views

Confusion between an element and its preimage

Let $X$ be a set and $\sim$ is an equivalence relation on $X$, so that the quotient set $X/_\sim=\bigcup_{x\in X}{[x]}$ with $[x]=[y]$ if and only if $x\sim y$. Consider the quotient map $f:X\to ...
-3
votes
1answer
57 views

Applications of set theory

We know that science and specially mathematics are based on the set theory. But, I would like to know some direct applications of set theory for computer science and engineering. For example, is there ...
4
votes
2answers
67 views

Let $X\subset \mathbb{R}$ Lebesgue measurable, $|X|<|\mathbb{R}|$, is it true that $X$ is null?

Let $X\subset \mathbb{R}$ Lebesgue measurable, $|X|<2^{\aleph_0}$, is it true that $X$ is null? Of course I am not assuming the Continuum Hypothesis. EDIT: It might be helpful to know that all ...
-2
votes
2answers
60 views

Proving that $A\cup\emptyset=A$ and $A\cap\emptyset=\emptyset$ [on hold]

I need to prove that $A\cup\emptyset=A$, and $A\cap\emptyset=\emptyset$. It's seem like it's obvious, yet how can I prove it mathematically?
1
vote
2answers
140 views

Is the set of all pairs of real numbers uncountable?

My hypothesis is that $\mathbb{R \times R}$, the set of all pairs $(r_1, r_2)$, of real numbers is uncountable. I understand that the set of all pairs of natural numbers is countable. But could ...
0
votes
1answer
26 views

Uncountable “relatively independent” subset of finite dimensional vector spaces over an uncountable field

Let $V$ be a $n$ dimensional vector space over an uncountable field ; then does there always exist an uncountable subset $S$ of $V$ such that any $n$ vectors of $S$ are linearly independent ? ( I can ...
0
votes
1answer
40 views

Can an element of a power set $2^A$ be a subset of $2^A$?

This question is continued from a previous thread I started, but it had more than one question so I had to move the other question here. For this example consider an injective map $f: A \to 2^A$ then ...
0
votes
1answer
52 views

If $A$ is a non-empty set and $2^A$ is the power set of $A$. Is $2^A \subseteq A$?

I'm aware that if there exists an injective map $f: A \to 2^A$ then for each element $a\in A$ $\exists$ $f(a)\subseteq A$. But does this also mean $f(a)\subseteq 2^A$? I ask this because when ...
6
votes
6answers
229 views

Is the set of all pairs of natural numbers countable? [duplicate]

Say that $\Bbb N \times \Bbb N$ is the set of all pairs $(n_1, n_2)$ of natural numbers. Is it countable? My hypothesis is yes it is countable because sets are countable. But I am unable to come up ...
0
votes
2answers
45 views

Closure of $\Bbb R$ [on hold]

Is the closure of $\Bbb R$ equal to $\Bbb R$ itself or the extended real numbers $\bar{\Bbb R}$? Thanks for any comment.
5
votes
1answer
98 views

Is this enough to explain why set theory work in real analysis?

Sorry for starting a lot of topics in set theory; I think this will be my last. I just want to know what are the basics I need to know about set theory to mathematical analysis. Is what I have ...
0
votes
5answers
82 views

A better proof for the set of irrational number not closed under ordinary multiplication.

A positive irrational number $$q$$ is by definition a real number than cannot be expressed as a ratio of $2$ integers. To show that the set of irrational number is not closed under ordinary ...
0
votes
1answer
29 views

Show that the set $\mathbb{Q}^+$ is a group under ordinary multiplication

To be a group, a set with a binary operation has to satisfy all four of the group axioms. My problem is with closure as each time I am unsure if my proof suffices. The set of positive rational numbers ...
1
vote
2answers
55 views

Is the fact that these sets can not exist a consequence of Russels paradox?

Some time ago I asked why a given collection of objects could not be a set(something to do with abstract algebra). I got three answers, one was close to the Russel paradox, two other explanations ...
2
votes
0answers
39 views

On the properties of an interesting set on the real line…

Let $K$ be the set of all real numbers of the decimal form $$ 0.\;e_1\;\underbrace{0}_{1!\text{ times}}\;e_2\;\underbrace{00}_{2!\text{ times}}\;e_3\;\underbrace{000000}_{3!\text{ ...
1
vote
1answer
14 views

Is it overkill to define the closure of a set $A,A\subseteq B$ by the union of the range of the recursive function $h(0)=A, h(n^+) = h(n)\cup f[h(n)]$

$f:B\to B,A\subseteq B$. Is it overkill to define the closure of a set $A,A\subseteq B$ over $f$ by the union of the range of the recursive function $h(0)=A, h(n^+) = h(n)\cup f[h(n)]$? I ...
3
votes
3answers
91 views

If $A$ and $B$ are sets, then either $A \in B$ or $A\notin B$

Given that $A$ and $B$ are two sets, is the following proposition a tautology: $A\in B \vee A\notin B$. I do not know any set theory beyond the naive one.
1
vote
2answers
53 views

What kind of set-theory is sufficient to understand mathematical analysis?(book recommendation))

I am looking for books with set theory and logic that is sufficient to understand mathematical analysis. I guess another question might be if there even exists such a book. There are basically two ...
0
votes
2answers
40 views

$A \subset B \implies f^{-1}(A) \subset f^{-1}(B)$

Prove: $A \subset B \implies f^{-1}(A) \subset f^{-1}(B)$ I am busy setting up a proof for Real Analysis, and have come to a point where I need to use the above statement. Intuitively, I ...
0
votes
0answers
30 views

Which of the following sets have the cardinality the same as $R$ [duplicate]

Which of the following sets has the same cardinality as that of $\mathbb{R}$? $W$=The set of constant functions on $\mathbb{R}$ $X$=The set of polynomial functions on $\mathbb{R}$ $Y$=The set of ...
0
votes
1answer
60 views

Proving set identities

I am attempting to work on some proofs for my math assignment, but I'll be honest in that I am really struggling to understand them. I read through the power point given by my teacher; however, even ...
0
votes
1answer
26 views

simplifying set theory expression

I'm trying to simplify a set theory expression, it relates to a programming problem... I have a set of staff members who are grouped into various teams (Team A, Team B, Team C etc ...up to Team H). ...
1
vote
2answers
22 views

Set Theory - Simplify expression

Can the following be simplified? It's been a long time since I did set theory and I don't remember my simplification rules. This is probably totally easy... can I simplify this any further? $(A \cap ...
1
vote
1answer
43 views

Proving $k^{m+l} = k^m k^l$ by constructing a bijective function F : $ ^MK \times ^LK \to ^{L\bigcup M}K $

For cardinals k which is cardinal of K and l which is cardinal of L and m which is cardinal of M. W.T.S [ $ k^{m+l} $ = $ k^m k^l $] by constructing a bijective function F : $ ^MK \times ^LK \to ...
-4
votes
0answers
21 views

If the function f and function g is one to one, show that the composition g of f is one to one? [on hold]

If the function $f$ and function $g$ is one to one, show that the composition $g$ of $f$ is one to one? How do I show that the composition of two function both of which are one to one produces a ...
1
vote
2answers
46 views

Show that $f: \mathbb N \to \mathbb N$, $f(x)=x^2$ is not onto

To begin, the definition of an onto (surjective) function is as follows. A function $\phi$ from $A$ to $B$ is surjective if for each for each $b$ in $B$, there exists at least one $a$ in $A$ such ...
0
votes
1answer
23 views

Are maximal intervals of open nonempty sets always equal?

Let $O\subset\mathbb{R}$ be an open nonempty interval. Define for every $x\in O$: $$a_x = \inf\{a\in\mathbb{R}\mid(a,x]\subset O\}$$ $$b_x = \sup\{b\in\mathbb{R}\mid[x,b)\subset O\}$$ $$I_x = (a_x, ...
4
votes
1answer
51 views

Product of two sets with density zero has density zero?

Let $A$ and $B$ be two subsets of $\mathbb N$ which have asymptotic density zero. Define $A\times B$ as the set of integers of the form $ab$ with $a\in A$ and $b\in B$. Must $A \times B$ also have ...
1
vote
2answers
58 views

Given nonempty sets S and T, does there exist a set R that is disjoint from S with |R|=|T|?

Let $S$ and $T$ be nonempty sets. I would like to show that there exists a set $R$ such that $S\cap R=\emptyset$ and $\left\vert T\right\vert = \left\vert R\right\vert$. Here is my work so far. Let ...
0
votes
0answers
13 views

Set-sum in $\mathbb Z_p^d$

Notation: $G$ abelian group, $X,Y \subset G$, $X^c = G \backslash X$, $|X| =$ number of elements of $X$, $X+Y = \{ x+y \in G; x \in X, y \in Y \}$. Let $B \subset G$ fixed and $\lambda(x) = ...
1
vote
1answer
22 views

Set builder notation for matching element pairs

I have a set of pairs, $S = \{ \langle a,b \rangle_1, \langle a,b \rangle_2, ..., \langle a,b \rangle_n \} $ where $a$ is not unique amongst the pairs. If I want to express the extraction of all the ...
1
vote
3answers
61 views

Which of the following statements are false?

All of the following sets are subsets of positive integers. $A = \{x\mid x\ \text{is divisible by 2}\} \\ B = \{x\mid x\ \text{is divisible by 4}\} \\ C = \{x\mid x\ \text{is divisible by 6}\}$ ...
0
votes
1answer
25 views

A question about the well-ordering theorem

In Munkres' book "Topology", he states that Well-Ordering Theorem: If $A$ is a set, there exists an order relation on $A$ that is a well-ordering. Then, in his discussion of the Maximum ...
0
votes
2answers
23 views

How to proof equivalence relation?

I need help with this problem: Let $S=\left\{\left[\begin{matrix} a & b \\ c & d \end{matrix}\right] : a,b,c,d \in \mathbb{C}\right \}$ and $M=\left\{\left[\begin{matrix} a & b \\ ...