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
1answer
18 views

Is every point of rational number boundary point?

While studying first chapter of multivariable calculus, I am wondering if every point of the rational number is boundary point. It is obvious that $\Bbb{R}^n$ is the union of interior, exterior, ...
0
votes
2answers
36 views

The powerset of the set of natural numbers - Cantor's Theorem

It is a fact that if $A$ is any set then there is no bijection between $A$ and its powerset $P(A)$. If $A$ is finite, this is pretty clear just by looking at the sizes of $A$ and $P(A)$. But if I ...
1
vote
2answers
21 views

For every set $A$, there exists a well ordered set $V$ such that there exists no surjection $\pi: A \rightarrow V$.

I am proving that for every set$ A$, there exists a well ordered set $X$ such that there exists no surjection $\pi : A \longrightarrow V$. I think that's very simple, and so I think maybe I made some ...
-3
votes
3answers
59 views

Does there exist a function between arbitrary sets?

Given arbitrary sets $A$ and $B$, does there exist a function $f: A\rightarrow B$ that is injective?. Does this follow from the axioms of set theory? If yes, then which axiom?
0
votes
0answers
9 views

Can the direction of failing distributivity on ordinals be turned into an inequality?

Is it true that for all ordinals $\alpha_1, \alpha_2, \beta$: $$(\alpha_1 + \alpha_2)\cdot\beta \leq \alpha_1\cdot\beta+\alpha_2\cdot\beta\;?$$
0
votes
0answers
11 views

The universe of a sub algebra generated by $ \{(a \wedge b)\vee(c \wedge b') : a,c \in C\}$

I need to prove the next thing, Let $B$ be a Boolean algebra and $C$ a proper subalgebra of $B$. Let $b ∈ B−C$. Prove that the set $ \{(a \wedge b)\vee(c \wedge b') : a,c \in C\}$ is the universe of ...
0
votes
1answer
15 views

If a set X has the finite meet property, then there is an ultrafilter such that X is a subset of it.

I need to prove that if $X \subseteq B$ is a set with the finite meet property, then there exists an unltrafilter $U$ of $B$ such that $X \subseteq U$. I know that the finite meet property means that ...
0
votes
2answers
21 views

Let $F$ be a class of sets. Prove that $B - \mathop{\bigcup}_{A\in F} A = \mathop{\bigcap}_{A\in F} (B-A)$

Let $F$ be a class of sets. Prove that $B - \mathop{\bigcup}_{A\in F} A = \mathop{\bigcap}_{A\in F} (B-A)$ I've started like this: $X= B - \mathop{\bigcup}_{A\in F} A$ $Y= \mathop{\bigcap}_{A\in ...
0
votes
2answers
18 views

How many relations can be defined the this power set

Let $A=\{1,2,3\}$ What is the number of reflexive relations the can be defined on $P(A)$? I first thought the number is 3, but it seems I'm wrong. How can someone solve this problem? Thanks
0
votes
1answer
8 views

Proof concerning indexed family of sets

Let $f: A \rightarrow B$ be a function. Let $I$ be a non-empty set, and let $\left\{U_i\right\}_{i \in I}$ be a family of sets indexed by $I$ such that $U_i \subset A$ for all $ i \in I$. Proof the ...
2
votes
1answer
22 views

Sum and product of Cardinal numbers

Define the sum and the product of two cardinal numbers and show that these are well-defined operations. That's what I have tried: Let $A,B$ sets with $A \cap B=\varnothing, card(A)=m, card(B)=n$. ...
2
votes
3answers
43 views

Is is true $\forall_{A,B \subset X}: f(A - B)=f(A) - f(B)$?

In C. Adam's Topology, it is written that $f(A) - f(B) \subset f(A - B)$ for any function, but $f(A) - f(B) = f(A - B)$ iff f is bijective. I can come the half way, i.e., $f(A) - f(B) \subset f(A - ...
1
vote
1answer
20 views

Indexed family by two indexes

Show an example of indexed family $A (i, j)$ by two indexes $i,j$, such that each set will be different: every combination of (union over $i$/intersection over $i$), (union over $j$/intersection over ...
2
votes
2answers
41 views

Can we always define distributive multiplication

If I have a set endowed with an addition operation (say a general group) and I know it contains 1, can I always define a multiplication operation so that it distributes over the addition? By this I ...
1
vote
0answers
19 views

Partial and total orders

From Exercise 4.4.9 of How To Prove It: Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$. Define a relation $L$ on $A \times B$ as follows: $L = \{((a, b), (a', b')) \in (A ...
2
votes
1answer
36 views

Power Set Explanation

The following is from the Wikipedia page on the Power set: By identifying a function in $2^S$ with the corresponding preimage of $1$, we see that there is a bijection between $2^S$ and $\mathcal ...
1
vote
0answers
30 views

If $E$ is a closed set there exist a set $S$ such as $E=S'$

In "Elementary Real Analysis" by Thomson-Bruckner p.190 I did the following exercise: (we're working on $\mathbb{R}$ and elementary topology on that set) One of Cantor's early results in set ...
0
votes
0answers
19 views

Inclusion or element?

Hello people I want to make sure my work is correct ! {1} --- {1,{1,{1}}} its a subset only since here the element {1} isn't inside that set however it is a subset. {{1}} is not an element or subset ...
0
votes
2answers
55 views

Let $A, B$ be sets. Show that $\mathcal P(A ∩ B) = \mathcal P(A) ∩ \mathcal P(B)$.

Let $A, B$ be sets. Show that $\mathcal P(A \cap B) = \mathcal P(A) \cap \mathcal P(B)$. I understand what this question is asking. The power set of an intersection equals the intersection of two ...
1
vote
1answer
36 views

Induction on the size of the set?

Show that every non-empty finite set of real numbers has a maximum. (Hint: induction on the size of set). I'm not exactly sure how to approach this. I'm familiar with induction, but I don't know ...
0
votes
1answer
11 views

SDR (system of distinct representatives) from Venn Diagram

I want to learn what is SDR (system of distinct representatives) today. SDR (system of distinct representatives): SDR = System of distinct representatives. Given a finite family of sets ...
1
vote
2answers
28 views

Set Theory: Cardinality of functions on a set have higher cardinality than the set

I'm independently working my way through Elements of the theory of functions and functional analysis by Kolmogorov and Fomin. At the moment, I'm stuck on the following exercise (on page 11), the ...
0
votes
0answers
25 views

Logic problems and Venn Diagrams [on hold]

In a class of 32 pupils: 5 pupils live in New Town, travel to school by bus and eat school dinners. 3 pupils live in New Town, travel to school by bus but do not eat school dinners. 9 pupils do not ...
5
votes
10answers
2k views

Is there a maximum value between open (0,1) set?

This question came up in my interview for a job application(you won't believe it but it was a C# programmer job application). Let's say we have a open set (0,1). Can we say that there is a maximum ...
-1
votes
0answers
29 views

Prove that S=$\cup_{\varepsilon \ge0} \cap_{n=1}^{\infty}\cup_{m=n}^{\infty}E_m(\varepsilon)$ [on hold]

Let {$f_n$}$_n$ and $f$ be real valued function defined on $\mathbb R $ for $\varepsilon$>0 and $m\in \mathbb N$, define $E_m(\varepsilon)=${$x\in \mathbb R : |f_m(x)-f(x)|\ge \varepsilon$}. And let ...
1
vote
1answer
31 views

There exist a surjection from X to Y and a surjection from Y to X iff there exists a bijection betwen X and Y. [duplicate]

Theorem: Let X and Y bet non empty sets, then there exist a surjection from X to Y and a surjection from Y to X if and only if there exist a bijection betwen X and Y. Do anyone have an idea how to ...
0
votes
1answer
15 views

Basic set theory and probability

I need to prove the following but they all seem too obvious to need a proof. For the third one, for exmple, should I argue something along the line of $A\cup A^c=U$? Thanks in advance. $A=(A\cap ...
0
votes
2answers
37 views

Prove that cardinality of A,B,C,D are same.

Consider the following sets: A= set of sequence of real nos. B=set of sequence of positive real nos C=$\mathbb R$ D= C[0,1] then prove that cardinality of ...
0
votes
2answers
43 views

Is my proof that empty set is open and R is open correct?

Claim: The empty set is open. Proof. Assume that the empty set is closed. Then, there must be one point such that any point in its ball is not inside of the empty set. However, the empty set has no ...
0
votes
1answer
19 views

Why are we looking for such a function?

Show that for any sets $A_1, A_2, B_1, B_2, A_1 \sim A_2 \wedge B_1 \sim B_2 \rightarrow A_1^{A_1} \sim A_2^{B_2}$. Let $A$ set with $card(A)=m$. Let $B$ set with $card(B)=n$. We define ...
4
votes
1answer
50 views

Proving things about the function $f:\varnothing\to S$

If $S$ is any set, then the empty set is contained in it in a unique way. You could view the inclusion $\varnothing \subseteq S$ as the unique function from $f:\varnothing \to S$. The following ...
-2
votes
2answers
40 views

How to prove $(B \cap A^c) \cup A$ is an empty set [on hold]

I was wondering how I could prove $(B \cap A^c) \cup A$ is an empty set using the laws of set theory. Thanks!
1
vote
1answer
34 views

$\mathbb R$ is totally ordered, but $x\in\mathbb R$ has no immediate successor.

A similar question is this one. I proved that if $X$ is a totally ordered set, then an element of $X$ has at most one immediate successor and at most one immediate predecessor. Initially when I read ...
0
votes
1answer
13 views

Subsets Of A Set Product

I was asked the following question: Let $A={1,2,3}$ and $B={4,5}$. How many subsets does the set $A\times B$ contain of size at most $4$? My understanding of the outer product $A\times B$ is ...
1
vote
1answer
37 views

Question about maps in partially ordered sets

I am struggling with a proof related to the mapping of posets. Let $P_1$and $P_2$ are posets, and $f$ an order preserving map from $P_1$ to $P_2$. $$g(Z):= f^{-1}[Z]$$ $g$ goes from the set of all ...
1
vote
1answer
32 views

Is there a bijective mapping $f:\mathbb{N}^2→\mathbb{N}$ that preserves lexicographic order?

Is there a bijective mapping $f:\mathbb{N}^2→\mathbb{N}$ that preserves lexicographic order? I know that it is impossyble for the case $f:\mathbb{R}^2→\mathbb{R}$ ( here Bijection from $\mathbb{R}^n$ ...
0
votes
0answers
15 views

If $x,y$ are ordinals and $x \cong y$ then $x = y$

If $x,y$ are ordinals and $x \cong y$ then $x = y$ The proof goes as follows; Suppose $f$ is an isomorphism between $x$ and $y$ then show $f$ is the identity map. Assume that $f$ is not the ...
0
votes
0answers
8 views

How can we deduce that $\{0,1\}^{\omega} \sim \mathcal{P}(\omega)$? [duplicate]

Proposition: The set $\{ 0,1 \}^{\omega}$ of the infinite sequences with values at $\{0,1\}$ is not countable. Proof: $$\{0,1\}^{\omega}=\{ (x_n)_{n \in \omega}: \forall n \in \omega \ \ x_n \in ...
1
vote
0answers
25 views

Definition of infimum and supremum in being greater than elements

Suppose you have a set, $\mathbb{N}$, the set of natural numbers.The proof by contradiction is simply that you assume. $a = \sup \mathbb{N}$ The definition of $\sup = a$ would then be that. $a = ...
0
votes
1answer
27 views

Cantor - No set is equinumerous with its power set.

Theorem: No set is equinumerous with its power set. Proof: Let $A$ be a set. We want to show that if $f: A \to \mathcal{P}A$ (a random function) then $f$ is not surjective. We define the set $D=\{ ...
0
votes
0answers
26 views

Which other function could we pick to prove that the union is at the most countable?

Proposition: The union of two sets, both of which is at most countable, is an at most coutable set. Proof: Without loss of generality, let $A \neq \varnothing, B \neq \varnothing$ be at most ...
0
votes
3answers
57 views

if A × B ⊆ C × D then how to prove that A ⊆ C or B ⊆ D.

Suppose $A,B,C,D$ are sets such that $A \times B \subseteq C \times D$. How do I prove that $A \subseteq C$ or $B \subseteq D$? I am only arriving at $(x,y)$ belongs to $A \times B\to (x,y)$ belongs ...
1
vote
0answers
34 views

Counting problems that still remains unsolved?

I just proved that the cartesian product of $\mathbb{Q}$ and $\mathbb{N}$ is countable and I started to wonder if there exists any sets that is still not yet proven to be countable/uncountable? Also, ...
0
votes
1answer
21 views

Check $S\cap T$ where $S =\left\{ x \in \mathbb{R} : x^6 -x^5 \le 100\right\}$ and $T =\left\{x^2-2x : x \in (0,\infty)\right\}$

Let $S=\left\{x\in\mathbb{R} : x^6 -x^5 \le 100\right\}$ and $T=\left\{x^2-2x : x \in (0,\infty)\right\}$. Then check whether or not $S\cap T$ is Closed and bounded in $\mathbb{R}$ Closed but not ...
1
vote
0answers
29 views

What function to use to show that the set of positive rational numbers is countable? [duplicate]

This is from Discrete Mathematics and its Applications Here is the definition of countable that the book uses and how to determine if two sets have the same cardinality Here is the example that ...
0
votes
1answer
34 views

Symmetric difference and convergence of sequence of sets

I have two question regards to symmetric different and a convergent sequence of a set:- if we have a sequence of sets $\{X_i\}$.then how to show that:- $\{X_i\}$ is convergent if and only if if for ...
1
vote
1answer
45 views

Given $B \cup A = B$ and probability and set theory axioms, prove $\mathbb{P}(A) \leq \mathbb{P}(B)$.

I need to prove that $\mathbb{P}(A)$ is less than or equal to $\mathbb{P}(B)$ using only this three things: $B \cup A = B$ The three axioms of probability: a) $\mathbb{P}(A)$ is greater or equal to ...
1
vote
1answer
13 views

How to interpret algebraic relationship/ next step to take to prove function is onto?

This is a problem from Discrete Mathematics and its Applications Book's definition on bijection Book's definition on onto Book's definition on one to one I am trying to do problem 23D. Here ...
1
vote
1answer
29 views

Definition of an ordered pair in Analysis text

In my analysis text the author defines an ordered pair $$ (a,b) := \{ \{a\}, \{a,b\} \} $$ I am confused as to how this is an adequate definition. I see that it establishes order but other than that ...
0
votes
1answer
41 views

Checking if a relation is a function

The question: Define a relation $P$ from $\mathbb{R}^+$ to $\mathbb{R}$ as follows: For all real numbers $x$ and $y$ with $x>0$, \begin{align} \left(x,y\right)\in P\:\:\text{means ...