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

2
votes
1answer
60 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
29 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
24 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
11 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
41 views

Relationship between increasing integer sequences

Suppose that $X\cap Y=\emptyset$, that $X\cup Y=\Bbb N$ and that $X(n),\;Y(n)$ are increasing surjections $\Bbb N\to X$ respectively $\Bbb N\to Y$. Further, suppose that there are straight line ...
0
votes
3answers
36 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
20 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
23 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
38 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
24 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
62 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
14 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
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
24 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
44 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
21 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
20 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 ...
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
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
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
16 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
39 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
24 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 ...
5
votes
1answer
52 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
14 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
39 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
16 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
9 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
27 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 ...