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

1
vote
1answer
26 views

Intuition of least upper & greatest lower bound of sequence of subsets.

I have come across these while studying the limsup & liminf of sequence of subset of a set. In order to understand that, I have to understand what least upper bound & greatest lower bound of a ...
2
votes
4answers
58 views

Set theory: cardinality of a subset of a finite set.

Suppose $A$ is a finite set of cardinality $n$. And Let $B$ be a subset of $A$ and the cardinality of $B$ equals $n$. Then $B=A$. Many texts use this fact very frequently but it seems that they ...
0
votes
0answers
29 views

Is this proof for the existence of countable subsets for infinite sets correct?

Does this proof require any extra axiom for it to work? Taken from Virtual Lab in Probability and Statistics Theorem: If $S$ is an infinite set then $S$ has a countable infinite subset. ...
1
vote
0answers
25 views

De Morgan's laws imply involution?

Suppose you have a complemented lattice $\mathfrak{L} = \left<L, \vee, \wedge, \neg, 1, 0\right>$ that satisfied De Morgan's laws. I want to prove that this is an ortholattice. The first ...
4
votes
1answer
29 views

Power set of $X$ is not in $X$

Prove or find a counterexample to: $P(X) \notin X$. I think it's true but I'm having trouble coming up with a proof, clearly if $P(X) \in X$ then $X \in P(X) \in X$ but I'm not sure where the ...
1
vote
1answer
29 views

How do you create the equation for the Cantor Pairing Function?

According to wikipedia, here is the equation: $f(x,y) = \frac{(x+y)(x+y+1)}{2}+y$ How do you go about creating this function? I understand that the X value is found by the corresponding triangle ...
1
vote
1answer
20 views

The Intersection of Equivalence Relations which cover a relation

Exercise A.3 From John Lee( Topological Manifolds) Let $R \subset X \times X$ be any relation on $X$, and define ~ to be the intersecction of all equivalence relations in $X \times X$ that contain ...
3
votes
0answers
28 views

Proving Equivalence Relation $xPy$ iff $ y = x + n\pi$ on The Reals

I am trying to prove that the relation P on $\mathbb{R}$ by the rule $\forall x, y \in \mathbb{R}, xPy \text{ if and only if } \exists n \in \mathbb{Z} \text{ such that }y = x+ n\pi$ From what I can ...
0
votes
4answers
73 views

How to prove that $[0, 1) \text{ and } (0, 2]$ have the same cardinality using Bijection?

I am just starting out with bijection, so my knowledge of it is very sparse. I am trying to prove that $[0, 1) \text{ and } (0, 2]$ have the same cardinality using a bijection. But I have no idea of ...
-2
votes
0answers
34 views

Bijection between two sets $\mathbb R$ and $\mathbb R^2$ (and $\mathbb R^n$) [duplicate]

Does there exist a bijection between $\mathbb{R}$ and $\mathbb{R}^2$? How about $\mathbb{R}$ and $\mathbb{R}^n$?. ...
3
votes
1answer
21 views

Strings in a dictionary. A partial order, strict order, and total order?

Question: The domain is the set of all words in the English language (as defined by, say, Webster's dictionary). Word $x$ is related to word $y$ if $x$ appears as a substring of y. For example, "ion" ...
2
votes
1answer
23 views

X - Y in a finite set

Question: The domain is the power set of a finite set. $X$ is related to $Y$ if $X - Y$ is not empty. Is it a partial or strict order? If it is a partial order or strict order, is it also a total ...
2
votes
3answers
322 views

Is the powerset of the reals any “more uncountable” (in some sense) than the reals are?

I know that $\mathbb{N}$ is countable and has cardinality $\aleph_0$, and that $\mathbb{R}$ has cardinality $2^{\aleph_0} = \text{C}$ and is uncountable. Are sets with cardinalities greater than ...
0
votes
1answer
20 views

The terminology for particular subsets of the power set of R

The set $X = \{\{x\in\Bbb R\mid x<a\}\mid a\in\Bbb R\}$ , which is a subset of the power set of R. Is there a terminology for the set $X$? My intent is to search the related literature about the ...
0
votes
1answer
24 views

Partial order or strict order

Question: The domain is the set of all positive integers. $a$ is related to $b$ if $b = a⋅ 3n$, for some positive integer $n$. Because of the equal sign, isn't this relation symmetric, transitive, ...
-1
votes
1answer
33 views

Is the cartesian product associative [duplicate]

Does the cartesian product have an associative property such that $M_1\times(M_2\times M_3) = (M_1\times M_2)\times M_3$, or does the different order result in different ordered pairs?
2
votes
5answers
70 views

What is $X\cap\mathcal P(X)$?

Does the powerset of $X$ contain $X$ as a subset, and thus $X\cap \mathcal{P}(X)=X$, or is $X\cap \mathcal{P}(X)=\emptyset$ since $X$ is a member of the $\mathcal{P}(X)$, and not a subset?
2
votes
1answer
38 views

Intuition of partial-ordered set.

Recently I've come in front of partial ordered set. I've read the wiki article but couldn't comprehend it especially the concept of set together with a binary relation. Can anyone please explain me ...
1
vote
2answers
72 views

Empty set does not belong to any cartesian product?

I am reading from Halmos naive set theory, for Cartesian product, defined as: $$ A\times B=\left\{x: x \in P(P(A\cup B))\,\wedge\,\exists a \in A,\exists b \in B,\, x=(a,b)\right\} $$ Empty set ...
0
votes
1answer
43 views

If there is a finite-closed topology on $X$ with 3 clopen elements, then $X$ is finite

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
41 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
33 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
27 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
39 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
37 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
24 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
71 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
202 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$. ...
3
votes
1answer
64 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
50 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
41 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 [closed]

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
80 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
63 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
44 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
27 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
150 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
67 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$ [closed]

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