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

-4
votes
2answers
21 views

Simple set theory proof

Prove that the intersection $$ \bigcap_{n \in \mathbb{N}}\left(-\frac{1}{n},1\right) = [0,1)$$ without using limits. I know that I need to prove subset in both directions.
0
votes
1answer
22 views

“if f is an injection, then $f^{-1}(f(x))=x$ for all x in D(f) and $f(f^{-1}(y))=y$ for all y in R(f)”

How can I prove that "if f is an injection, then $f^{-1}(f(x))=x$ for all x in D(f) and $f(f^{-1}(y))=y$ for all y in R(f)" Does anyone could help keep? Thanks!
1
vote
0answers
18 views

Restriction of an equivalence relation on a subset.

If we have an equivalence relation defined on a set E and S its subset. Is the relation defined on S is also an equivalence one? Thank you for your answers.
3
votes
4answers
51 views

Existence of a countable $\sigma$-algebra on an uncountable set

Let $\Omega$ be a set. If $\Omega$ is finite, then any $\sigma$-algebra on $\Omega$ is finite. If $\Omega$ is infinite and countable, a $\sigma$-algebra on $\Omega$ cannot be infinite and ...
2
votes
1answer
14 views

Can I represent $S = \{x: \sin(x) > 0\}$ as $\bigcup_{k\in\Bbb Z} \left[\frac {\pi}{6}+2\pi k,\frac {5}{6} \pi+2\pi k\right]$?

Is it correct to represent $S = \{x: \sin(x) > 0\}$ as $\bigcup_{k\in\Bbb Z} \left[\dfrac {\pi}{6}+2\pi k,\dfrac {5}{6} \pi+2\pi k\right]$?
0
votes
0answers
23 views

Cardinality of the set $\mathbb{Z}_{26}^5$

I am trying to compute the unicity for a Vigenère cipher with $m=5$ to compute this I need the sizes(cardinality) of the plaintext space and key space they are the sets $\mathbb{Z}_{26}^5$. Integers ...
4
votes
1answer
37 views

Would you accept this proof for $(A^c)^c = A$?

In my exercises I had the following question: Prove that $(A^c)^c = A$. My solution: Let $A$ be a set where $A\subset X$. $A = \{x \in X, x \in A\}$ by definition. $A^c = \{x \in X, x \notin A\}$ ...
1
vote
1answer
38 views

How to write $H = \{x: \cos(x) > 0\}$ as the union of the intervals?

I have $\dfrac {1}{2}\left( 4\pi k\pm k \right) ,k\in \mathbb{Z}$. But I don't understand how to represent it as the union of the intervals.
-3
votes
2answers
42 views

Prove that $ |A∪B|=|A|+|B|-|A∩B|$ [on hold]

If $A, B$ and $C$ are finite sets, prove that $$|A\cup B|=|A|+|B|-|A\cap B|$$ $$|A\setminus B|=|A|-|A\cap B| $$ $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|$$
0
votes
0answers
15 views

Inductive Property of Sets?

Why doesn't the set: $ {2,4,6,8,10,.....}$ have the inductive property. For example $ n = 2k$. So for every value of k you get a value of $n$. Plus $k+1$ is also present. So shouldn't this set have ...
1
vote
1answer
29 views

My question is a very basic one about relations

I am learning about relations right now and I have a question about some terms. I am told a relation on $A$ is a subset of $A\times A$. Then I am told a relation $R$ on $A$ is reflexive if for all ...
0
votes
1answer
47 views

Countability for Subset of Irrational Number [on hold]

I know that the set $I$ of irrational numbers is uncountable. But how to know that $$C=\{{x\in I, 0\leq x^2 \leq25}\}$$ is uncountable or not?
2
votes
3answers
22 views

Please help me with this set operation (Corrected question)

"$A$ and $C$ are disjoint sets, schematize $(A^c \cup B^c)\cap C$." Please help me. My answer was "$C$". Thank you. (I can't comment, so I put the upgraded question...)
-1
votes
1answer
23 views

Could you help me with this set operations? [on hold]

"$A$ and $B$ are disjoint sets, schematize $(A^c \cup B^c)\cap C$." Please help me. My answer was "$C$". Thank you.
1
vote
1answer
27 views

Is this proof correct (Cartesian Products and Subsets)?

I am trying to prove that if $A \times B$ is a subset of $A \times C$ then $B$ is a subset of $C$ given that $A$ is not empty. I've looked at this question on here and I'm aware it's been asked. My ...
1
vote
1answer
36 views

How to complete the proof that $A^c\cup(A\setminus B)=(A\cap B)^c$?

I had to prove that: For all sets A and B, $A^c \cup (A \setminus B) = (A \cap B)^c$. Below is what I did, but I'm kind of stuck at the time. So I begin with proving $A^c \cup (A \setminus B) ...
1
vote
1answer
43 views

(If exists) a set of all ordinals that set is an ordinal?

In set theory (ZF) an ordinal is a transitive set of transitive sets. Thus (if exists) a set of all ordinals gives a contradiction therefore there is no set of all ordinals. But what is wrong with ...
0
votes
1answer
34 views

Question on Proofs of Sets. [on hold]

The set $A$ is a subset of the set $B$ iff $A \cup B = B$ If $A$ is a subset of the set $B$, then $A \cup C$ is a subset of $B \cup C$.
2
votes
2answers
33 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
19 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
24 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
34 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 ...
-1
votes
0answers
14 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
174 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
1answer
24 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 ...
1
vote
2answers
71 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 ...
1
vote
1answer
54 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
52 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
39 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
1answer
22 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
26 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
33 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
44 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
14 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
27 views

Binary Relations that are Partial Orders

I am trying to figure out the relationship between binary relations in a set and partial orders. Any thoughts?
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
42 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
21 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
23 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
19 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.