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
0answers
25 views

Prove that the set of all points on the plane has the same cardinality as the set of all lines.

Prove that the set of all points on the plane has the same cardinality as the set of all lines. (Hint : The line $y=ax+b$ corresponds to the pair $(a,b)$; do not forget about vertical lines.)
1
vote
1answer
41 views

Prove that the set of all finite sequences of real numbers has the same cardinality as the set $\mathbb{R}$ of reals. [duplicate]

Prove that the set of all finite sequences of real numbers has the same cardinality as the set $\mathbb{R}$ of reals. I can not understand the purpose of the question.
1
vote
1answer
20 views

Complement of a set and inverse image.

I'm currently taking a real analysis class and we are working on measurable functions (the notes can be found here under "Measurable Functions"; the exercise is the first one on the last page). ...
1
vote
2answers
28 views

Constructing a one-to-one correspondence between closed interval and half open interval

Construct a one-to-one correspondence between the closed interval $ [0,1] $ and the half-open interval $ [0,1)$. Hint: Take $B=\{1\}$
0
votes
0answers
15 views

Proving union of two $\sigma$ algebras in $X$ is an algebra, then it is a $\sigma$-algebra.

I tried two countable union of $M_1, M_2 \in 2^X$ such that $A\in M_1, B\in M_2$ where $ A=\bigcup_{k=1}^{\infty}A_k, B=\bigcup_{k=1}^{\infty}B_k $. But Im stuck on that I should prove ...
0
votes
0answers
12 views

What is the set of the accumulation points of this set?

Let $A := \{ \frac{1}{n} \mid n \in \mathbb{N} \}.$ I wish to find the boundary of $A$. Since $\overline{A} = A \cup \{ 0 \},$ there remains to find $\overline {\mathbb{R}\setminus A}.$ Since ...
0
votes
1answer
24 views

Given the relation $\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$ determine whether it is reflexive, transitive, symmetric, or anti-symmetric.

Given the relation $\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}\,$ determine whether it is reflexive, transitive, symmetric, or anti-symmetric. I found this set to be reflexive and symmetric. But not ...
0
votes
5answers
41 views

In set theory; How to show $|B_3 \cup (B_1\cap B_2)| = |B_1| + |B_2| +|B_3| - |B_1 \cup B_2|$?

I am unable to solve this problem. Can anyone show me how to prove this above formula?
0
votes
3answers
60 views

Is the universe calculable and if so, can this be proven with mathematics. [on hold]

The world according to determinism is a place where event x ultimately leads to event y and thus the direction of the universe at any given moment should be, in theory, calculable. Can this be ...
2
votes
1answer
18 views

Is ordering of (possibly infinite) sets by cardinality a total ordering?

Given sets $A$ and $B$. Can you show that either there exists an injective map of $A$ into $B$ (that is, a map such that each element of $A$ maps to an element of $B$ and no two elements of $A$ map to ...
0
votes
0answers
17 views

Recommended Level of Depth on Set Theory for Applied Math (LA,Prob)

I hope this is appropriate to post on these specific tags. If one's objective is to become highly proficient in the application of Linear Algebra, Probability, Statistics and Optimization, how much ...
1
vote
1answer
14 views

Number of pairwise disjoint subsets of a set R, where the total cardinality of the pairwise subsets is less than or equal to some k < |R|

I'm not a mathematician and so I am not sure if my question is worded right. I am a software engineer who just started doing a PhD and so there is a lot of theoretical computer-science stuff that ...
3
votes
3answers
98 views

Are there two meanings to induction?

I've seen mathematical induction in two forms. First form: It seems that if $P(0)$ holds and $\displaystyle ...
0
votes
1answer
24 views

Good books of naive set theory

Is there a good book naive set theory which prove important theorems and propositions like: The rational numbers are countable The real numbers are not countable $card \ (0,1)=card\ ...
1
vote
1answer
33 views

Term for relationship of set overlap without containment?

What is the term for the relationship between two sets that share at least one common element, but neither set is a proper or improper subset of the other? $$ A?B=_{def}\exists x \exists y \exists z ...
0
votes
4answers
66 views

Show that all the intervals in $\mathbb{R}$ are uncountable

Question: Show that all the intervals in $\mathbb{R}$ are uncountable. I have already proven that $\mathbb{R}$ is uncountable by using the following: Suppose $\mathbb{R}$ is countable. Then ...
1
vote
1answer
24 views

$A$ and $B$ are infinite sets with $B \subseteq A$. Which of the following statements are true?

$A$ and $B$ are infinite sets with $B \subseteq A$. Which of the following statements are true? $A \sim B$ $A \sim A \setminus B$ If $B$ is countable then $A \sim B$ If $A$ is ...
3
votes
1answer
33 views

Is it possible to extend well ordering principle/induction to all well ordered sets?

Today I was thinking about well ordering of naturals,and how by induction we can prove some properties of natural numbers.Now I started wondering if this is property of natural numbers,which are well ...
0
votes
1answer
19 views

A Criterion For a Set To Have all the Atoms of a Boolean Algebra

Let $\Omega$ be any set and let $\mathcal A$ be an algebra of sets in $\Omega$. An element $E\in \mathcal A$ is said to be an atom if there is no non-empty element $A\in \mathcal A$ such that ...
-1
votes
1answer
28 views

How to solve unitary work problem by Set theory?

How to solve by set theory - if $A,B$ and $C$ can complete a work individually in $4, 5$ and $6$ days, how many days they will take together to finish the work?
1
vote
2answers
19 views

If $A_n \downarrow A.$ then $A_1 - An \uparrow A_1 - A$? Set theory.

Let $A_1, A_2 , \dots$ be subsets of a set $\Omega$. If $ A_1 \subset A_2 \subset \dots$ and $\bigcup_{n = 1}^{\infty} A_n = A $ then we write $A_n \uparrow A.$ $ A_1 \supset A_2 \supset \dots$ and ...
1
vote
1answer
21 views

Show that the built set $\{ (x, y) \in \mathbb{R}^{2} \mid x^{2} + xy + y^{2} = 1 \}$ is compact in $\mathbb{R}^{2}$

I see that the set $\{ x^{2} + xy + y^{2} = 1 \}$ is bounded, because given any $y$ there are exactly two $x$ such that $x^{2} + xy + y^{2} = 1$ and so is the case where $x$ is given. But I do not ...
-1
votes
1answer
34 views

How to show that the set of natural numbers, $\mathbb N$, is equinumerous with $\mathbb N \cup \{N\}$? [on hold]

I have the set $\Bbb N$ of natural numbers $\{0, 1, 2, 3, \ldots \}$ and another set, $\Bbb N \cup \{N\} = \{0, 1, 2, 3, \ldots\}\cup\{N\}$. What kind of function is there which establishes a ...
0
votes
0answers
44 views

Proof of $(P \to R) \lor (Q \to R)\, is\,equivalent\, to\,(P \land Q) \to R$

I am working through Velleman’s ‘How to Prove It’. This is one of the problems where I am a bit stuck. $(P \to R) \lor (Q \to R)\, is\,equivalent\, to\,(P \land Q) \to R$ I use the Conditional ...
0
votes
1answer
40 views

Proof by contradiction or contrapositive sets help

so I'm having difficulties proving the following Theorem, through either proof by contradiction or contrapositive. Can someone please help me? The problem is as follows: Prove that for any two sets, ...
0
votes
0answers
18 views

Equality of sets

Suppose we have a stopping time defined as $T_\lambda = \inf \{ s\geq 0 : M_s \geq \lambda \}$ where $M$ is a non-negative martingale which is right-continuous. For my question this does not matter ...
1
vote
2answers
24 views

Is the empty family of sets pairwise disjoint?

„A family of sets is pairwise disjoint or mutually disjoint if every two different sets in the family are disjoint.“ – from Wikipedia article "Disjoint sets" What about the empty family of sets? Is ...
0
votes
1answer
20 views

Finding smallest set of real numbers according to a property

This is one of the example problem that has been solved in Velleman's How to prove book: Find the smallest set of real numbers X such that $5 \in X$ and for all real numbers $x$ and $y$, if $x ...
2
votes
4answers
58 views

What does P in blackboard bold type of letter stand for? ℙ?

In the first post of the thread "Cardinal number subtraction", Cardinal number subtraction there is a symbol for some kind of set which looks like this: ℙ I am familiar with symbols for natural ...
1
vote
1answer
44 views

Existence of functions $g$ such that 1. $f\circ g(1) =2$; 2. $g \circ f(1) = 2$, for all $f$ [on hold]

Let $S = \{1,2,3,4\}$. Let $F$ be the sets of all functions from $S$ to $S$. a) Prove or disprove the statement: "For all $f \in F$, there exists $g \in F$ so that $(f \circ g)(1) = 2$" b) Prove or ...
0
votes
1answer
36 views

Let $A, B$ and $X$ be sets. Prove that if $A ∪ B ⊆ X$ then $A ⊆ X$.

I have just started learning set theory and I've been trying to learn how to do proofs, however I really can't figure out I've been trying to answer a simple one: Let $A, B$ and $X$ be sets. Prove ...
4
votes
2answers
44 views

How can I prove that the cadinality of a set minus a finite number of elements of it is still the same as the original set?

A is a finite subset of S, which is an infinite set. How can I prove that $|S| = |S \setminus A|$? I just finished proving that $|T \cup S|$ where $T$ is infinite and $S$ is countable is $|T|$. They ...
1
vote
1answer
15 views

Find $\bigcap_{k\in\mathbb{Z^+}} B_k$ where $B_k=\left[3/k,\left(5k+2\right)/k\right)\cup\left\{10+k\right\}$

The question was originally, instead of $\bigcap_{k\in\mathbb{Z^+}}B_k$, to find $\bigcap_{k\in\mathbb{N}}B_k$, but this did not make any sense. For instance, consider the interval I am finding the ...
0
votes
1answer
31 views

How could I prove that the cardinality of the union of two sets is equal to R? $|T U S| = |T| = |\mathbb{R}|$

I have to prove that $|T \cup S|$ where $T$ is infinite and $S$ is countable, equal to $|T|$, and this is also $|\mathbb{R}|$. How can I approach this? $|T \cup S| = |T| = |\mathbb{R}|$ I tried to ...
1
vote
3answers
69 views

What is the cardinality of the set of all functions from $\mathbb{Z} \to \mathbb{Z}$?

How can I approach this? I have to find the cardinality of the set of the functions from $\mathbb{Z} \to \mathbb{Z}$ and I have no idea on how to solve it. Can someone hint me here? The approach ...
1
vote
3answers
79 views

How to resolve $x \in A \wedge x \notin A $?

Let A and B be two sets. Then $A \setminus B = \{x: x\in A \wedge x\notin B\}$ $A \setminus B = \{x: x\in A \wedge x\notin A \cap B\}$ How can one prove that two logical statements are equal? ...
0
votes
3answers
26 views

Computation theory, finding the number of total injections from a set B to A x B with A = {a,b,c,d,e} B = {0,1,2}

The cardinality of $A \times B$ is $15$ and that's as far as I've gotten.I'm using Sudkamps book and computation theory and this seems to be a question on my next exam however it is not included in ...
2
votes
0answers
13 views

Proof $X\backslash\bigcap \limits_{i\in\Lambda} A_i = \bigcup\limits_{i\in\Lambda} (X\backslash A_i)$ [duplicate]

Let $X$ be a universe. Let $\{A_i\}_{i\in\Lambda}$ be a family of sets in $X$, where $\Lambda$ is a set of index. I want to prove: $$X\backslash\bigcap \limits_{i\in\Lambda} A_i = ...
1
vote
1answer
24 views

Function inverse

Question: Let $S$ and $T$ be sets and let $f:S\to T$. Show that $f$ is a surjection from $S$ to $T$ iff for each subset $B$ of $T$, $f[f^{-1}[B]]=B$. So it's a surjection if for each element $t$ ...
0
votes
2answers
28 views

Find $\bigcap_{k\in\mathbb{N}} B_k$ if $B_k=\left\{k-1,k,k+1\right\}$

This is not a homework problem. I want to find \begin{align} \bigcap_{k\in\mathbb{N}} B_k,\tag{1} \end{align} if $B_k=\left\{k-1,k,k+1\right\}$. I know these sets are not pair-wise disjoint, but the ...
2
votes
3answers
29 views

Prove that if A is a countable set, and is a subset of R, then there exists a real number x such that A intersect A + x is disjoint.

I am struggling with this question, and any help would be appreciated. I hope I'm clear with the terminology though.
0
votes
0answers
29 views

Does there exist an open subset U of $R^{n+1}$ and a bijective function $f: S^n→U$? [closed]

Let $S^n=\left \{ x_1,x_2,...,x_{n+1}| x^2_1+x^2_2+...+x_n^2=1 \right \}$ Does there exist an open subset U of $R^{n+1}$(natural topology) and a bijective function $f: S^n→U$ ?
-1
votes
1answer
28 views

Show that the set of integers endind in 0 or 5 has the same cardinality as the set of integers

The title is the question I am asked, word for word. How would I show this? They are both infinite, therefor have the same cardinality? I'm also a bit confused on the wording of "the same ...
1
vote
0answers
28 views

Functions, sets, intersections

Question: Let $S = \{1,2\} = T$ and define $f: S \to T$ by $f(1) = 1 = f(2)$. Let $B = \{1\}$ and let $C = \{ 2\}$. Find $f[B \cap C]$ and $f[B] \cap f[C]$ and observe they are not equal. Hint: ...
3
votes
3answers
32 views

Prove $B ⊆ (C ∪ A) ⇔ (B \setminus A) ⊆ C$

Prove the following: \begin{align} B ⊆ (C ∪ A) &⇒ (B\setminus A) ⊆ C \\ (B\setminus A) ⊆ C &⇒ B ⊆ (C ∪ A) \end{align} Using Eulerian circles I only understood that statements are true. Still ...
0
votes
0answers
40 views

Indexed Families of Sets

Let $B_n=(0,1/n]$ for all $n\in\Bbb N$. $\qquad$(a) For each $n\in\Bbb N$, find $\bigcap_{k=1}^nB_k$ and $\bigcup_{k=1}^nB_k$. $\qquad$(b) Find $\bigcap_{n=1}^\infty B_n$ and ...
1
vote
1answer
42 views

Circular list from the 2nd element of the result of repeatedly perfect shuffling a magnitude ordered list of natural numbers less than an even number.

Start with a magnitude ordered list of the natural numbers that are less than a chosen even number greater than 0. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} Repeatedly 'Perfect Shuffle' this list, ...
3
votes
1answer
252 views

Is there a set theory where Ø = {Ø}? [closed]

Is there a set theory where Ø = {Ø} ? Or is it 'universally' impossible ? (i.e. does Ø ≠ {Ø} have to hold in every possible (= coherent), imaginable set theory?).
0
votes
1answer
18 views

Finding a Topology from a Subbase

The book I am using for my Introduction of Topology course is Principles of Topology by Fred H. Croom. Let $X=\{1,2,3,4,5\}$. $\mathcal{T}_X$ has a subbase $\mathcal{S}=\{\{1\}, \{1,2,3\}, ...
1
vote
3answers
27 views

mapping $\{a,b\} \times \{a,b\} \to \{a,b\}$

My lecturer asked the class how many maps are possible given the following expression: $$\{a,b\} \times \{a,b\} \to \{a,b\}$$ His answer is 16, but I'm not sure how he arrived at that answer. My ...