This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

-1
votes
1answer
19 views

Question on Proofs of Sets.

The set $A$ is a subset of the set $B$ iff $A \cup B = B$ If $A$ is a subset of the et $B$, then $A \cup C$ is a subset of $B \cup C$.
3
votes
3answers
26 views

Elementary Set Theory Proof. (Bi-Conditional Proof) [on hold]

Set $A$ is a subset of Set $B$ iff $A\cap B = A.$ Don't know how to do this bi-conditional proof.
1
vote
2answers
16 views

Proving Distributive Law of Sets

Let $A$, $B$, and $C$ be sets. Prove that $A \bigcap (B-C) = (A\bigcap B) - (A\bigcap C)$. Hint: Using 'iff' works on this proof. This is a question we got in a quiz. The problem is I don't get the ...
1
vote
1answer
19 views

Shorter expression of a special conditions

Let $A$ be a set and $B$ a condition (can be either true or false). Is there any shorter description of the expression $$ x = \begin{cases} A & B \\ \emptyset & \text{otherwise} \end{cases} ...
3
votes
3answers
27 views

Notation for non-empty subset [duplicate]

To denote non-empty subsets, I repeatedly find myself writing $A\subset S, A\neq \emptyset$. Is there any established shorthand for this, you know, like $A\subset S$ can be seen as a shorthand for ...
-2
votes
0answers
10 views

Inscribed and circumscribed polygons [on hold]

Given a circle, prove (with basic geometric methods: no trigonometry) that the area of any inscribed irregular polygon is strictly smaller than the area of any circumscribed polygon. Extra ...
0
votes
3answers
169 views

Demonstrating the equality of two power sets [on hold]

Let $A$ and $B$ be sets. How to prove that $A = B$ if and only if $P(A) = P(B)$?
0
votes
0answers
52 views

equivalence relations and classes

For each relation $p$ described below, determine if $p$ is reflexive, symmetric, transitive, anti-symmetric. In each case, if $p$ is an equivalence relation, describe the equivalence classes. a) $A = ...
0
votes
1answer
20 views

Prove that for a sequence of people sets $S_1,…,S_d$, $\Delta_i \not = 0$ for all people

We have $k$ people $p_1,...,p_k$, and $d$ people sets $S_1,...,S_d$, where the sizes of $S_1,...,S_d$ can vary between $1$ and $k$ (so each $S_1,...,S_d$ is a set of some people from ...
0
votes
2answers
54 views

Relations $\rho $ and $\rho^2$ [on hold]

If $\rho$ is a relation on a set $A$, define $\rho^2$ by $a\rho^2 b$ if and only if there exists $c$ with $a\rho c$ and $c\rho b$. If $\rho$ is reflexive/symmetric/transitive does $\rho^2$ have the ...
-4
votes
0answers
32 views

Well order given disjoint well orders. [on hold]

Let $F = \{X_α \mid \alpha \in A\}$ be an indexed family of pairwise disjoint sets. (Recall that this means that if $\alpha\ne\beta$ then $X_\alpha \cap X_\beta = \varnothing$.) Suppose that each ...
1
vote
1answer
52 views

What is meant by $ab$ on words $a$ and $b$ in $\{ab\ |\ a,b \in Σ^*\}$?

Given language $L$ := $\{ab\ |\ a,b \in Σ^*\}$, $Σ := \{blue, green\}$. Is the notation "$ab$" above taken to be word concatenation, such that $\{bluegreen\} \subset L$? What occurs when $L$ := ...
3
votes
3answers
51 views

What is $\bigcup_{n=1}^{\infty}[0,1-\frac{1}{n}]$?

I often read that: $\bigcup_{n=1}^{\infty}[0,1-\frac{1}{n}]=[0,1)$. But why? My intuition would say that the result would be $[0,1]$ because $\lim_{n\rightarrow \infty}[0,1-\frac{1}{n}]=[0,1]$
0
votes
1answer
23 views

How to prove that $B$ is uncontable if $A$ is uncontable, $A\subseteq B?$ [duplicate]

Let $A$ be uncountable, $A\subseteq B.$ Prove that $B$ is uncountable.
1
vote
0answers
16 views

Cardinality for Kleene star and infinite Cartesian products.

Let $X$ be a finite set with at least 2 elements. Then the set of all finite-length "strings", $$X^* = \bigcup_{L \in \mathbb{Z}^+} \prod_{i=1}^L X_i = \{ (x_1, \ldots, x_L) : L \in \mathbb{Z}^+ ...
1
vote
1answer
25 views

Venn- Diagrams, Probability

I want to know how to draw a Venn Diagram with the given information below.. There are 30 students: 16 are girls; There are 7 girls and 6 boys who have blue eyes. A student is randomly ...
0
votes
3answers
33 views

Discrete Mathematics Symmetric Diffirence Proof [duplicate]

I've been trying to find a proof for the following problem but have been unable to come up with anything myself: Say we have A, B, C part of a universe U show that if $$A \Delta C = B \Delta C ...
0
votes
1answer
27 views

Any denumerable set is infinite

Currently, I'm learning 'An Introduction to Classical Real Analysis' (Stromberg, 1981) by myself and find that the proof of Theorem (1.55) in pages 29-30 is far beyond my comprehension. Can anybody ...
0
votes
1answer
43 views

Is it possible to find $n-1$ consecutive composite integers

Given an integer $n\geq 2$ ,can we always find an integer $m$ such that each of the $n-1$ consecutive integers $m+2,m+3,.....,m+n$ are composite?
0
votes
1answer
13 views

Proving that the $k$th element of $A \cup B$ is median of (the first $k$ elements of A) $\cup$ (the first $k$ elements of $b$)

By union here, I am referring to a union where duplicates are allowed. Given two sorted arrays, A and B, how do you prove that the $k$th element in the union of A and B is the median of the following ...
3
votes
1answer
26 views

Binary Relations that are Partial Orders

I am trying to figure out how many binary relations there are over the set {a,b,c} that are also partial orders. While I have some intuition as to how to do this, I am having trouble with coming up ...
0
votes
3answers
43 views

How to find the number of subsets in a set without writing all of them out?

How can you find the number of subsets in any set like $\{2, 4, 6, 8\}$ without writing out the subsets first including the empty set and the set itself? I seriously need the shortcut to finding ...
-1
votes
1answer
35 views

Proving $\rm{card}(\Bbb Z)=\rm{card}(\Bbb N)$ [duplicate]

So I'm trying to prove that the set of integers has the same cardinality as the set of naturals just using the definition, that is, I'm trying to find a bijective function between the two sets. I ...
-1
votes
0answers
21 views

Injective map implies $|A| \leq |G|$?

I'm looking at a proof and it says that if there is an injective map from A to G, then $|A| \leq |G|$. I'm not sure why this is true. Is it because if $|A| > |G|$, then you would have elements ...
0
votes
0answers
27 views

comparing cardinality of infinte sets [duplicate]

Let's say I have two infinite sets: 1) the set of all functions from $\mathbb{R}$ to {0,1}; 2) the set of all polynomials whose coefficients are in $\mathbb{R}$. Which is greater? I figure the ...
0
votes
0answers
26 views

Proofs Regarding Open and Closed Sets

I need to prove the following regarding open and closed sets: 1. A set L is closed iff for any converging sequence $(x_n)$ with $x_n\in L$, the limit $x=\lim_{n\to\infty}{x_n}$ is also an element of L ...
1
vote
1answer
41 views

What is the dimension of the vector space of functions $f:\mathbb R\to\mathbb R$?

What is the dimension of the vector space of functions $f:\mathbb R\to\mathbb R$? I want to say that it is at least $2^{\aleph_0}$, but I have no idea how to sharply pin it down otherwise.
1
vote
0answers
15 views

A property of $\delta$-rings

Let $\mathfrak{R}$ be a (non-unitary) $\delta$-ring of sets and let $\{A_n\}_n$ be a collection of sets belonging to it. If $\bigcup_{n=1}^{\infty} A_n\notin\mathfrak{R}$, could ...
4
votes
1answer
60 views

Is the book “Naive Set Theory” from P. R. Halmos still up-to-date?

My question is, if Halmos' book "Naive Set Theory" is still up-to-date concerning contemporary mathematics, that is, is it outdated or not? I really love the books so far, and while it's clear the ...
0
votes
1answer
20 views

How to prove these facts about integers using this definition?

A subset $A$ of $\mathbb{R}$, the set of real numbers, is said to be inductive if $1 \in A$ and if the statement $x \in A$ implies the statement $x+1 \in A$. The $Z_+$ of positive integers is ...
2
votes
2answers
22 views

Does there exist a bijective mapping of an open interval with the corresponding closed interval having only finitely many points of discontinuity?

Given $a<b$, is there a bijection $f \colon [a,b] \rightarrow (a,b)$ such that $f$ be continuous except at finitely many points only? I know that there does exist a bijection of $[a,b]$ with ...
4
votes
2answers
38 views

Does $A^i \cap A^j = \emptyset, $ if $ i \neq j$?

I'm doing a bit of set theory and, of course, I'm confused. How true is it that if we have a series of cartesian products of a set, say $A^n, n< \omega$, then it necessarily holds that $A^i \cap ...
0
votes
2answers
51 views

Question about intersection/union of a set and its complement

I was answering this multiple choice question: If $A$ is any set, then $A \cup A' = U$ None of these $A \cap A' = U$ $A \cup A' = \emptyset$ I answered (1), but apparently the ...
1
vote
1answer
18 views

Question about function on a lattice.

Let $X$ be a complete lattice, and $g$ a function from $X$ to $X$ s.t. $x_1\le x_2$ $\implies g(x_1)\le g(x_2)$. Show that there must be some element in $X$ that maps to itself. Here is what I am ...
0
votes
2answers
53 views

Cardinality of the union of two infinite set

Suppose that $A$ and $B$ are two infinite sets and $|A|<|B|$. The question is that how to prove that $|A∪B|=|B|$. The proof is related to the Axiom of Choice.
1
vote
4answers
69 views

which one of these proofs more acceptable for $A⊆B$ iff $A\cap B=A$?

I've got two answers to prove that $A⊆B$ iff $A\cap B=A$ first, (*) Assume that $A\cap B=A$. If $x\in A$ and $x\in B$ $\rightarrow $ $x\in (A\cap B)$. And if $y\in B$ but $y\notin A$ $\rightarrow ...
-1
votes
0answers
15 views

How do I construct a finite sequence satisfying binary relation?

Let $R$ be a binary relation on $\{1,\cdots,n\}$ such that $\forall 1\leq i< n, \exists 1\leq i<j\leq n$ such that $iRj$. How do I prove that there exists a finite sequence $\{n_1,\cdots,n_k\}$ ...
2
votes
1answer
36 views

How do I make sense of $\{ n \} \cap n$?

I've been learning set theory, and I've come across an exercise in which I'm trying to prove that $\forall x \forall y x \in y \rightarrow y \neq x$. I want to use the axiom of foundation to prove ...
1
vote
3answers
26 views

Countable Union to Countable Disjoint Union

In many texts, the construction of a countable disjoint union of sets from a sequence of sets, $E_1, E_2,E_3,\ldots$ follows from: Let $F_1 = E_1, F_2 = E_2\setminus E_1,F_3 = E_3\setminus (E_1\cup ...
4
votes
5answers
155 views

why is $\{x\} \in \{x\}$ false?

I apologise for this simple question. So if {x} is a subset of {x, {x}}, then why isn't {x} belong to {x}?
7
votes
2answers
95 views

$A_1 \cap A_2 \cap \cdots \cap A_n \ne \emptyset$ holds for all $n$. Must it be that $\bigcap_{n = 1}^{\infty} A_n \ne \emptyset$?

Let $A_1, A_2, A_3, \,\ldots$ be sets such that $A_1 \cap A_2 \cap \cdots \cap A_n \ne \emptyset$ holds for all $n$. Must it be that $\bigcap_{n = 1}^{\infty}A_n \ne \emptyset$? I answered ...
2
votes
3answers
34 views

Can $\mathbb{R}$ be partitioned into $n$ dense sets with same cardinality?

Are there sets $S_i\subseteq\mathbb{R}$ with $i\leq n$ such that $S_i$ are disjoint, $S_i$ have same cardinality, $S_i$ are dense in $\mathbb{R}$?
0
votes
1answer
53 views

Spotting mistake: unnecessary given condition

I have solved the following problem without using a given premise. Could someone please spot whether I have done something wrong? Suppose we have a relation $\geq$ that is transitive, but not ...
0
votes
1answer
28 views

If $A$ is a subset of $C$ and $B$ is a subset of $C$, then the union of $A$ and $B$ is a subset of $C$

If $A$ is a subset of $C$ and $B$ is a subset of $C$, then $A\cup B$ is a subset of $C$. I was considering letting $x$ be an element of $A$ and $B$ and going from there, but I'm not sure that that is ...
2
votes
4answers
36 views

Two sets are disjoint if and only if one is contained in the complement of the other

Prove that $A\cap B = \emptyset$ iff $A\subset B^C$. I figured I could start by letting $x$ be an element of the universe and that $x$ is an element of $A$ and not an element of $B$.
0
votes
0answers
18 views

Cartesian Product of set complements

Let $C$ be a subset of $M$ and $D$ be a subset of $N$. Is there any way to simplify the Cartesian product $(M\backslash C)\times(N\backslash D)$ ?
1
vote
0answers
18 views

Subsets of $ \mathbb Q $ of order type $ \omega^{\alpha}$ for each countable ordinal $\alpha $.

My introductory text in Set Theory (Stillwell) includes an exercise (6.3.1) asking for an explicit example of a subset of $ \mathbb Q $ or order type $ \omega^2 $. This seems straight forward enough. ...
-2
votes
1answer
23 views

Prove this theorem with complement sets [closed]

Prove that the relative complement of A∩B with respect to a set E is the relative complement of A with respect to a set E ∪(union) the relative complement of B with respect to a set E.
2
votes
2answers
32 views

Prove that $A=B$ according to the conditions involving relative complements

Prove that if the relative complement of $A$ with respect to a set $E$ is equal to the relative complement of $B$ with respect to a set $E$, then $A=B$.
0
votes
0answers
17 views

Special relations on a finite set

Given a set $S = \{s_1, \dots, s_n\}$, $S \times S$ is the product space of $S$ with itself. Let $S_0 = \{(s_i, s_i), i=1,\dots,n\}$. Are there a name and/or notation for the operation mapping $S$ to ...