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

11
votes
4answers
728 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
78 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
35 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
22 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
54 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
50 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
32 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
54 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
60 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
41 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
90 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
50 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
81 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
233 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
59 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
34 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
83 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
62 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
31 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 ...
1
vote
1answer
34 views

Given $f: A \times B \rightarrow C$, what is the notation for the induced function when the right factor is replaced by $B'$?

Given a function $f: B \rightarrow C$ and a bijection $g: B' \rightarrow B$, there is a naturally induced function $f': B' \rightarrow C$, namely the composition $f' = f \circ g$. Now, given a ...
0
votes
1answer
34 views

Find the number of sets satisfying the conditions

Let $ N$ be the number of ordered pairs of nonempty sets $ \mathcal{A}$ and $ \mathcal{B}$ that have the following properties: • $ \mathcal{A} \cup \mathcal{B} = ...
0
votes
5answers
53 views

Formal proof of a simple fact, namely that $S$ has even cardinality if certain pairs could idenitifed

Let $S$ be a finite set such that to each $s \in S$ there corresponds exactly one $t \ne s$ such that $t$ uniquely corresponds to $s$. Then $S$ has even order. This is quite obvious, an argument ...
14
votes
5answers
944 views

Is axiom of choice necessary for proving that every infinite set has a countably infinite subset?

Is it possible to prove the following fact without axiom of choice ? " Every infinite set has a countably infinite subset". Can it be proved that axiom of choice is necessary here ?
0
votes
1answer
26 views

Is there a relationship between the unbounded infinities and uncountable infinities? [duplicate]

When a function f increases without bound we say $f(x)=\infty$. How does this idea relate to, if at all with the infinite sets we study in set theory? To give a better understanding of why I'm ...
1
vote
1answer
26 views

Set theory venn diagram help. Homework

I am new to set theory and one of our exercises is the following question: decide on the truth or falsity of the claim that, for all sets A, B, C, D [A ∩ B ⊆ C ∩ D] ⇒ [(A∆B) ⊇ (C∆D)]. I have drawn ...
-1
votes
0answers
92 views

Is there a universal way to define cartesian product with arbitrary many terms?

Suppose we are working with some set theory where primitives are sets and membership. Starting from that, we can give a prescription to define what it means to be an ordered pairs $(a,b)$. This allows ...
2
votes
1answer
35 views

Logic question requiring axiom of choice

Predicting Real Numbers Regarding the above question, the solutions require creating classes of sequences with representative sequences. How are those sequences constructed? How is it possible to ...