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

Finding a unique relation $T$

This is one question I have been solving from Velleman's How to prove book: Suppose $R$ and $S$ are relations on a set $A$, and $S$ is an equivalence relation. We will say that $R$ is compatible ...
1
vote
1answer
45 views

How to calculate the cardinality of the complement of two countable sets of reals?

Let $A,B\subseteq\Bbb R$ be countable sets. Denote by $A'$ and $B'$ the complements (in $\Bbb R$) of $A$ and $B$ respectively. What is the cardinality of $C=A'\cap B'$? I cant figure this ...
3
votes
1answer
57 views

Anatomy of $\mathcal P(\mathbb{N})$

How many proper subsets of $\mathcal P(\mathbb{N})$ there is that have cardinality of $2^{|\mathbb{N}|}$ ?
1
vote
2answers
43 views

An injection between finite sets of equal size must be a bijection

To me, it seems logical that if I have two finite sets of equal size, and there is an injection between them, then that injection must be a bijection. However, of course, we cannot just claim these ...
1
vote
1answer
53 views

A Proof in Elementary Set Theory

I apologize in advance for any lack of clarity in my mathematical symbols; I'm beginning to learn how to use this site. I'm working through "Introduction to Analysis" by Rosenlicht and he presents an ...
1
vote
1answer
32 views

Has anyone ever suggested a name or notation for this operation on multisets?

A basic multiset identity says: $$A+B = (A \cap B) + (A \cup B)$$ Allowing ourselves to use negative multiplicities and rearranging: $$A-(A \cap B) = (A \cup B)-B$$ But since $A \supseteq (A \cap ...
0
votes
1answer
26 views

Cardinality of a Quotient Set

Let $X = \{1, 2, 3, 4, 5, 6, 7, 8, 9,10\}$ and $P=\{2,3,5,7\}$. In $P(X)$ define the equivalence $A\mathcal{R}B$ if $A\setminus P = B \setminus P$ . Then what is the cardinal of the quotient set? I ...
1
vote
2answers
22 views

Equality of 2 Sets

I'm reading a book that states "If $X$ and $Y$ are sets, then $X=Y$ if and only if, for all $x, x\in X$ if and only if $x\in Y$." Perhaps it's because I learned the equality of two sets being defined ...
11
votes
4answers
745 views

When do two functions become equal?

When do two functions become equal? I have stumbled over this definition of equality of functions in elementary real analysis. Let $X$ and $Y$ be two sets. Let $f:X\rightarrow Y$ and ...
0
votes
1answer
11 views

intersection closure of comparison relations

I am given a set of $n$ integers $X$ and a set of operations $L=\{\geq,\leq,\neq\}$ over $X$. Consider all binary relations $\bf{R}\ $ resulted from any combination of $L$. For example ...
2
votes
3answers
79 views

One-one and onto map from $\mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N} $.

Can you tell any one-one & onto map from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$? I can prove that these have same cardinality but am unable to think of a mapping.
0
votes
0answers
18 views

union of a class of sets which is empty [duplicate]

i came across a concept on set theory in a book on topology and i can't seem to understand it. if $U$ is the underlying universal set and if $\left\{A_{i}\right\}$ is a class of subsets of $U$ for an ...
-1
votes
1answer
27 views

$B$ is a subset of some $s(n)$

Assume that $s$ is a function with domain $\omega$ such that $s(n) \subseteq s(n^+)$ for each $n \in \omega$. Assume that $B \subseteq \bigcup_{n\in\omega}s(n)$ such that for every infinite subset ...
2
votes
2answers
61 views

Questions about definability of truth

Suppose i work in ZFC. Using the recursion theorem, i can define the the truth value of formuals in the language $\mathcal{L}$ of set theory (one predicate symbol $\in$), $Val_\mathcal{M}(\varphi)$, ...
1
vote
2answers
37 views

Question about definition by induction.

I am reading some notes about naive set theory. I know the "definition by induction", but I can't apply it to the following cases directly. Suppose $A$ is a set, let $A^+$ be the set $A\cup \{A\}$. ...
1
vote
1answer
29 views

Decreasing sequence of sets: Power of natural numbers

Let $P(N)$ be the set of all the possible subsets of natural numbers (power set of $N$). Suppose that we have a decreasing sequence of sets $S_n$, ie $S_{n+1} \subseteq S_n\;,\in P(N)$ such that they ...
3
votes
1answer
63 views

Exercise in set theory

Let $\mathbb{N}^{[2]}$ be the set of all sets with two elements in $\mathbb{N}$, and let $\mathbb{N}^{[2]}=A\cup B$. Prove that there is an infinite set $M\subseteq \mathbb{N}$ such that either ...
0
votes
3answers
37 views

For any two sets A and B, if $f: A \rightarrow B$ is injective, then if A is countable, B must be countable.

So i was given two questions you either prove or disprove them. A) For any two sets A and B, if $f: A \rightarrow B$ is injective, then if A is countable, B must be countable. B) For any two sets A ...
1
vote
1answer
23 views

Determining Injectivity, surjectivity, bijectivity, and inverses

I was given a question that begins like this. Suppose that $A$ is the set $\{a,b,c\}$ (these are just names for some three elements - you don't know anything about $a,b,$ or $c$). Consider the ...
0
votes
0answers
49 views

Does Zorn's lemma not hold for $\mathbb{N}$?

Quote Wikipedia: Suppose a partially ordered set $P$ has the property that every chain (i.e. totally ordered subset) has an upper bound in $P$. Then the set $P$ contains at least one maximal ...
0
votes
1answer
25 views

Truth set with an implies statement and an intersection of family of sets equals everything?

Suppose $A_0 = \{1,2\}, B = \{2,3\}, F = \{A_0, B\}$. $\cap F = \{x | \forall A (A \in F \implies x \in A)\}$ I am confused over the truth set in the intersection of $F$ because if $A \notin F$ then ...
1
vote
2answers
57 views

Let $f : \mathbb{N} → \mathcal{P}(\mathbb{N})$ be given by $f(n) = \{n+1 , n+2 , n+3 , . . . \}$

So i was given a question like this Let $ f : \Bbb N\to \mathcal P(\Bbb N) $ be given by $f(n) = \{n+1 , n+2 , n+3 , . . . \}$ (a) Is f an injection? Explain (b) Is f a surjection? Explain. I ...
0
votes
2answers
38 views

Proof: $ A - (B - C) \subseteq (A - B) - C$

Question: Prove or disprove the following statements: For all sets $A, B, C$: a) $A - (B - C) \subseteq (A - B) - C$ b) $(A - B) - C \subseteq A - (B - C)$ c) If $A - (B - C) \subseteq ...
2
votes
3answers
52 views

Prove explicitly that if a function has a left inverse it is injective and if it has a right inverse it is surjective

A function g : S → T is said to be a left inverse for the function f : T → S if g◦f equals the identity function on $T$. In this case, f is also a right inverse for g . Prove explicitly that ...
0
votes
0answers
34 views

How to count the number of unique combination of numbers in a set N, whose products equal to K?

Let K be the number 32, and N be the set of its factors. K = 32 N = {2, 4, 8, 16} How many unique combination of numbers are there in N, whose product is equal to K ? The answer is 6, ...
-1
votes
2answers
57 views

Fill in the blanks with either $∈$ or $⊆$

So was given a question that begins like this Let $A=\{ \emptyset , 1 , \{2\} , \{1 , 2\} \}$ . Fill in the blanks with either $\in$ or $\subseteq$ . $\{ 1 , \{2\} \}$______ $P(A)$ ...
-7
votes
1answer
62 views

Trivial and non trivial subsets [closed]

What is a trivial and non trivial subsets?, and please give 2 examples for each. I've tried to search for the examples but none of them shown. thanks
0
votes
1answer
42 views

Prove that for any two sets $|X|$ and $|Y|$, either $|X|\leq|Y|$ or $|Y|\leq|X|$. [duplicate]

Prove that for any two sets $|X|$ and $|Y|$, either $|X|\leq|Y|$ or $|Y|\leq|X|$. I know that there is a proof using Zorn's Lemma but I can't figure out how to do it.
2
votes
2answers
92 views

Is $A\cup B=A\cup \{B\cap A^c\}$?

I am reading the book "Statistical Inference" by Casella and Berger. I was wondering if an identity in Theorem 1.2.9 b is correct. They proves the following: If $P$ is a probability function and $A$ ...
2
votes
5answers
53 views

Prove that $(A-B) \cap (A-C) = A \cap (B \cup C)^c$ for any three sets A, B, C.

I was given a question that says Prove that $(A-B) \cap (A-C) = A \cap (B \cup C)^c$ for any three sets A, B, C. I'm completely lost with this question. In a previous question that says $A \cap C ...
-1
votes
2answers
83 views

About the cardinality of natural numbers [Solved]

I had learned that the set is countable if and only if it is finite or countably infinite. We know well that the set $\mathbb{N}=\{1,2,3,4,\dots\}$ is an infinite set. In order to find out if the ...
0
votes
1answer
18 views

Linear Diophantine equation in two variables

So I was given a question to find if there is any integer solutions. $6x + 15y = 79, x,y \in \Bbb Z$ Proof $3(2x + 5y) = 79$ implies 3|79 which is absurd because no such x,y exist Then I was given ...
0
votes
2answers
27 views

Determining bijectivity of a function

I was given a function from $f: \Bbb R \rightarrow \Bbb R \\f(x) = x^5 - 3\\$ I know this function is bijective because it is one to one, and onto. Then the question changes to $f: \Bbb Z \rightarrow ...
1
vote
1answer
31 views

Function defined on power set

Let $E$ be a set and let $f:\mathcal P(E) \to \mathcal P(E)$ such that if $A \subset B \implies f(A) \subset f(B)$. We define $R=\{Z \subset E :f(Z)\subset Z\}$ and $S=\{Z \subset E : Z \subset ...
1
vote
2answers
28 views

Listing all elements of a set [duplicate]

I was given a question like the following: Let $A = \Bbb Z$, $B = [-1,\pi]$ , $C=(2,7)$. List all Elements of $A \cap (B^c \cap C)$. I do not really understand how to got about this problem. I ...
3
votes
1answer
235 views

Set Theory ZF Axioms Doubt

I have a pretty basic question about the symbolic representation of the axiom of extensionality for set theory, which states that $$ \forall A \forall B [ \forall x (x\in A \iff x\in B)] \iff A = B ...
1
vote
0answers
38 views

Prove that $|\mathbb R^n | = |\mathbb R|$. [duplicate]

Prove that $|\mathbb{R}^n| = |\mathbb{R}|$. It will be enough to prove $|\mathbb{R}^{2}|=|\mathbb{R}|$. We can further simplify by proving $|(0,1)\times(0,1)| = |(0,1)|$ (because ...
0
votes
1answer
27 views

Filter and Ultrafilter questions

I'm trying to prove an ultrafilter on a finite set must be principle. I'm not really too sure how to go about this: Let I be a finite set and let U be an ultrafilter on I. That's the extent of my ...
0
votes
1answer
9 views

Is the image mapping of the inverse relation the same as the original relation's preimage mapping?

Suppose R is a relation from X to Y, and S is the inverse relation to R. Is the image mapping of S, the same as the preimage mapping of R?
0
votes
2answers
61 views

Confusion about reflexivity proof and properties of inequality with regards to a partial order proof

The confusions stem from this question: Let $R$ be a relation over a set $A$. For all $a∈A$ and $b∈A$, given that $a < b$ iff $a\leq b$ but $a\neq b$, and $a\leq b$ iff either $a < b$ or ...
1
vote
1answer
26 views

Operation table for A+B where + denotes the operation of symmetric difference

If someone could please verify if my operation table in the picture below is correct it'd be much appreciated. The task was given: $P_D=\{A: A \subset D\}$ and $D$ is a $3$-element set $D=\{a, ...
0
votes
1answer
36 views

Help with Set Problem

I asked an odd question about the concept of limits of sets in another post (Taking Limits of Sets but it got rather convoluted and I thought I could split it up into sub parts of the problem and put ...
3
votes
4answers
76 views

Does the set $\left\{\left(f,\int_a^b f\right):f\in X\right\}$ represent a function?

I'm working through Undergraduate Topology by Kasriel, and the author asks the following: Let $X$ be the set of all continuous, real-valued functions defined on $\left[a,b\right]$. Does ...
2
votes
2answers
87 views

True or false. If A ∪ B = ∅ , then A = ∅ and B = ∅ .

True or false. If A ∪ B = ∅ , then A = ∅ and B = ∅ . True or false. If A ∩ B = ∅ , then A = ∅ or B = ∅ or both A and B are empty sets. True or false. (A ∪ A^c)^c = ∅ . True or false. If A ∈ B, then ...
0
votes
2answers
60 views

Power set empty set confusion

So the question is Let $T = \{a,b\}$ and $S = \{Ø,\{Ø\}\}$. So what $i$ would assume would be the power set of $T$ is $\{\varnothing,a\}$, $\{\varnothing,b\}$, $\{a\}$, $\{b\}$, $\{a,b\}$. ...
0
votes
2answers
34 views

Is there a name for the operation which is the union of two sets, but keeps duplicates?

Is there a name for the operation $*$ such that, for example, if $A = \{a, b\}$ and $B = \{a, b, c\}$, $$A * B = \{a, a, b, b, c \}\text{?}$$ I.e., it is the union of $A$ and $B$ including duplicates? ...
0
votes
3answers
63 views

True or false. A set is any collection of objects.

True or false. A set is any collection of objects. True or false. A proper subset of a set is itself a subset of the set, but not vice versa. True or false. The empty set is a subset of every set. ...
0
votes
1answer
16 views

Subset of a set

How many subsets does the set containing a single element which is an empty set have? I know that an empty set is a subset of any set including itself but what would be the number of subsets in a set ...
1
vote
2answers
33 views

Is this proof about the countability of $\Bbb Q \times \Bbb Q \times \cdots \times \Bbb Q$ sound?

If $\Bbb{Q}$ is countable, prove that the set $\Bbb{Q}^n$ for $n = 2,3,...$ is countable. Base case: $n = 2 \rightarrow \Bbb{Q}^2 = \Bbb{Q}\times\Bbb{Q}$ which, by Proposition 4.5 (see bottom of ...
0
votes
1answer
50 views

Cardinal number for a subset of $\mathbb{N}$

Following simple statement came to my mind when I was thinking about infinite sets. Statement: There is no set $X\subset\mathbb{N}$ that has cardinality strictly between any finite set ...