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
22 views

Can number 2 be a particular instance of set membership relation? [on hold]

I have found some definitions of numbers in set theory, such as von Neumann's, Zermelo's, Frege-Russell's, and Cantor's (see e.g. this video https://www.youtube.com/watch?v=6UWhPnbZv-o&sns=fb). ...
0
votes
3answers
30 views

How to prove the equivalence relation $A\cup B=B \Leftrightarrow A\cap B = A$? [on hold]

How to prove the equivalence relation? $$A\cup B=B \Leftrightarrow A\cap B = A$$
0
votes
1answer
22 views

Proving the existence of a Bijection between Cartesian Products of Sets by Induction

Prove by induction that for any sets $A_1, \ldots , A_n$, there is a bijection from $(((A_1 \times A_2) \times A_3) \times \ldots \times A_n)$ to $A_1 \times (A_2 \times ( \ldots (A_{n-1} \times A_n) ...
1
vote
1answer
32 views

Showing that the class of all sets of a particular cardinality is not a set.

How to show that the class of all sets of a particular cardinality ,say $h$ is not a set. My argument: I assume that I've shown the following lemma. Lemma: If $X$ is an infinite set of cardinality ...
0
votes
1answer
51 views

A version of Zorn's lemma

The version of Zorn's lemma that I have found more often is Zorn's Lemma (1) If every chain belonging to the partially ordered set $S$ has an upper bound in $S$ then $S$ contains a maximal ...
-2
votes
1answer
34 views

Question about Aaronson Scott Quantum Computing Since Democritus

In the chapter on sets: Equality rules: $x=x, x=y$ implies $y=x, x=y$ and $y=z$ implies $x=z$, and $x=y$ implies $f(x)=f(y)$ are all valid. where $f$ is a function. But how do we know for ...
0
votes
1answer
8 views

Manipulating the definition of $\sigma$-algebra generated by a family of sets

I manipulated the standard definition of $\sigma$ algebra generated by a family of sets $\mathcal{A}$, $$ \sigma ( \mathcal{A}) := \bigcap \{ \Sigma \ | \ \Sigma \text{ is a $\sigma$-algebra on } X, ...
0
votes
1answer
10 views

Cantor Set and Base 3 Decimal Expansions

I'm trying to show that every point in the Cantor Set (obtained by "middle-thirds" removal, starting with $[0,1]$) has a base 3 decimal expansion consisting of only zeros and twos. I think the proof ...
-2
votes
1answer
34 views

Functions : Injective, surjective or bijection? [on hold]

I have been asked a question in one of my test. Question : Consider the relation R is a subset of X * Y where X = [a, b] and Y = [c, d] defined by R = {(x,y): x^2 + y^2 = 1}. For each of the ...
0
votes
2answers
21 views

Help with proof about functions and subsets

Problem: let $f: A \rightarrow B$. Prove that $f$ is injective if and only if for all $D \subset A$ we have that $f^{-1}(f(D)) = D$. Proof: => Suppose $f$ is injective. Let $x \in f^{-1}(f(D))$. ...
0
votes
0answers
17 views

Symbol Identification related to set-theory and graph theory

If $A$ is a set of vertices of a graph $G$ where $A=\{V_1, V_2, V_3,V_4... V_N\}$, then what is the meaning of symbol $|A|$ ? I encountered this problem when I was reading a paper related to directed ...
-4
votes
1answer
31 views

Use De Morgan's Laws to simplify the following sets

Simplify the following sets: $$ℝ\setminus \bigcap\limits_{n=1}^∞ (-1/n,1/n)\tag1$$ $$\bigcup\limits_{n=1}^∞ (ℝ\setminus[1/n,2+1/n])\tag2$$ For the first problem, I used De Morgan's law, and it ...
2
votes
1answer
64 views

How can we construct a $1-1$ correspondence between $(0,1$) and $\mathbb{R}$ that transform irrationals into irrationals and rationals into rationals?

This is an exercise in "Elements of set theory by Enderton". I can construct a function from the rational unit interval into rationals easily. So, If I can find a $1-1$ correspondence from real unit ...
0
votes
1answer
31 views

Cardinality of the set of all (real) discontinuous functions

This is a question from the book Introduction to Set Theory (Hrbacek and Jech), chapter 5, question 2.6. (Show that) The cardinality of the set of all discontinuous functions is ...
2
votes
1answer
28 views

Cardinality of sets: $|A|\le|B|\Rightarrow(|A\cup B|=|B|\land|A\times B|=|B|)$

My book of mathematical logic states the facts that, if we call $|X|$ the cardinality of set $X$, then, for any two sets $A,B$ such that $|A|\le|B|$, $$|A\cup B|=|B|\quad\text{ and }\quad|A\times ...
1
vote
0answers
12 views

Calculate cardinality of 8-digit strings composed of zeros and ones

How can i calculate cardinality of a set made of 8-digit strings composed of zeros and ones? In general, assuming that digits can repeats. My attempt Let $D$ be the domain composed only by one or ...
3
votes
1answer
54 views

Relationship between increasing integer sequences

Suppose that $\mathcal X\cap \mathcal Y=\emptyset$, that $\mathcal X\cup \mathcal Y=\Bbb N$ and that $X(n),\;Y(n)$ are increasing surjections $\Bbb N\to \mathcal X$ respectively $\Bbb N\to \mathcal ...
0
votes
3answers
39 views

Help me with proof concerning functions

Problem: Let $X$ and $Y$ be non-empty sets and let $f: X \rightarrow Y$ be a function. We define $F: P(Y) \rightarrow P(X)$ by $F(B) = f^{-1}(B)$ for all $B \in P(Y)$. Proof that $F$ is injective if ...
2
votes
1answer
34 views

Are $((0,1]\cap\mathbb Q)\times\mathbb Q$ and $\mathbb Q \times([0,1)\cap\mathbb Q)$ order isomorphic?

The ordering here isn't specified but I assume it's lexicographic. I think the answer is yes. My reasoning is the following: Neither sets have a least or a greatest element because the second ...
0
votes
2answers
21 views

Equivalence Relations and 1-1 Correspondences

I have an engineering instructor who has claimed that "equivalence relations and one-to-one correspondences are pretty much the same thing". However, I believe the answers to both of the following ...
1
vote
0answers
32 views

Universal set for linearly ordered sets of given cardinality

It is easy to see that every infinitely countable linearly ordered set embeds into Q (rational numbers) with its linear order.("Linear order"="total order". All embeddings are assumed to preserve ...
-1
votes
1answer
26 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
39 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
25 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 ...
-4
votes
3answers
64 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
10 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
15 views

What is 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
16 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
24 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
19 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
9 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
26 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
46 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
24 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
42 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
21 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
37 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 ...
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
56 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
38 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
13 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
26 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
32 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
18 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
40 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
45 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
25 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^{B_1} \sim A_2^{B_2}$. Let $A$ set with $card(A)=m$. Let $B$ set with $card(B)=n$. We define ...