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

2
votes
1answer
16 views

Show that $(\overline A ∪ B) ∩ (\overline C - A) = (\overline C - A)$.

Let $A, B,$ and $C$ be sets. Show that: $$ (\overline A ∪ B) ∩ (\overline C - A) = (\overline C - A) $$ I’ve simplified to the following: $$ (\overline A ∪ B) ∩ (\overline{C \cup A}) = ...
1
vote
1answer
17 views

inclusion of sets and inverse function

Is it true that for any function $f$, and sets $S_1,S_2$ such that $f:S1\rightarrow S2$, if g is the inverse of f $g = f^{-1}$, then $f(g[S1])\subseteq S1\subseteq g(f[S1])$?. If yes, is there a ...
0
votes
3answers
77 views

Why there is a unique empty set?

I Have a question. Given only the definition of equality of two sets, how can we prove that there is one and only one empty set. I mean by equality of two sets the following: $$A=B \iff \forall x (x ...
2
votes
2answers
28 views

Prove that $(\mathbb{N},\le)$ and $(\mathbb{Z}, \le)$ are not order isomorphic

I want to prove that $(\mathbb{N},\le)$ and $(\mathbb{Z}, \le)$ are not order isomorphic. So what I want to show is that the following is not true: $$x \le_\mathbb{N} y \iff f(x) \le_\mathbb{Z} ...
0
votes
2answers
20 views

For all $X \subseteq \mathbb{N}$ there exist $n \in \mathbb{N}$ with $|X| < n$.

True or false? For all $X \subseteq \mathbb{N}$ there exist $n \in \mathbb{N}$ with $|X| < n$. I think this is false because if you pick $X = \mathbb{N}$, then the inequality $|X| < n$ does ...
1
vote
1answer
21 views

intersection of antisymetric relations is antisymetric

Suppose $A$ is some set, and $R$ and $S$ are relations on $A$ s.t. $R$ and $S$ are anti-symmetric. I want to prove that $R\cap S$ is anti-symmetric. Let $a,b \in A \ $ s.t. $a\ne b$ and $(a,b)\in ...
-4
votes
2answers
23 views

Simple set theory proof [on hold]

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
23 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
1answer
28 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.
2
votes
0answers
30 views

'The power' to inject $8$ in $5$ cannot be used to simulate the 'power' to inject $9$ in $5$

I found a cool exercise on les mathématiques (french forum); it seems to be a challenging problem with no answer for now. Let me traduce the problem. Problem. We have three sets $A,B,C: ...
3
votes
3answers
55 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 ...
3
votes
1answer
17 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
24 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
43 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
43 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
16 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
31 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
37 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
26 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
35 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
15 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
25 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
55 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
41 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
37 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 ...