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
1answer
30 views

Complements in topology

Let $T$ be a finite-closed topology on $X$. $X$ has 3 clopen elements. Prove that $X$ is finite. Empty set must be one of these clopen sets as well as $X$. Therefore, we are left with some element ...
-3
votes
0answers
38 views

I need help simplifying this set theory question [on hold]

This is my question: $$( A \cup B \cup C ) \cap \big( (A' \cap B) \cup (B' \cap C) \cup (A \cap C')\big)'$$
2
votes
2answers
25 views

A Chain of Subsets of $\mathbb{R}$ Without any Good Countable Subchain

Consider which $\bigl{(} A_i \bigr{)}_{i\in I}$ is a chain of subsets of $\mathbb{R}$. We say that a countable chain like $\bigl{(} B_n \bigr{)}_{n\in \mathbb{N}}$ is good if : for every $n\in ...
1
vote
2answers
24 views

Show every chain has an upperbound?

Sometimes I feel like proofs like this are pointless. I mean, if we have a partially ordered subset, it seems automatically true that you have a max element. 1) Either you have an infinite sequence ...
1
vote
5answers
32 views

Why is the definition of an image of a subset use existential quantifier rather than universal?

According to my textbook (Discrete Mathematics and Its Applications by Rosen), the definition of the image under function $f $ $(f:A\rightarrow B)$ of the subset $S$ $(S\subseteq A)$ is $$f(S) = \{t | ...
0
votes
1answer
35 views

Find the lowest value of $x$ so that $x \in (A \setminus B)$

Let $A$ and $B$ be two sets for which the following applies: $A = \{x: \text{GCD(}x,12) = 1\}$ $B = \{x: x\ \text{is a prime}\}$ Find the lowest value of $x$ so that $x \in (A \setminus B)$. $x \in ...
0
votes
1answer
22 views

Are these partial order or total orders?

I just want to know if the following are considered partially ordered sets or total set. Here is the definition: $\mathbb{R}^2$ : (a,b) R (c,d) iff $a\leqslant c$ and $b\leqslant d$ $\mathbb{R}^2$ ...
0
votes
3answers
63 views

For a function Y : X→X , if Y is injective, then Y∘Y∘Y is injective.

For a function Y : X→X , if Y is injective, then Y∘Y∘Y is injective. My attempt: Using contrapositive, if Y is not injective. then Y ∘ Y is not injective, the there exist x, x' ∈ X with x ≠ x' but ...
2
votes
2answers
195 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$. ...
2
votes
1answer
56 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
45 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
31 views

Sets and ordering sets [on hold]

Let $n=10^{10^{1000000000000}}$. It then holds $n<{2n \choose n}$<$2^{2n}$
-2
votes
1answer
21 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
12 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
29 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
61 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
148 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 ...
-2
votes
1answer
61 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
68 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
141 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
54 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
232 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
48 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
99 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
54 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
23 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
46 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? [closed]

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 ...