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
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 ...
1
vote
0answers
35 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
24 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
36 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 ...
-2
votes
1answer
61 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 ...
0
votes
0answers
32 views

How do we express higher arity predicates and functions in terms of membership?

It's been noted by others that higher order logic is similar to set theory. We can express the second order statement $\forall$R$\forall$x(R(x)) as a first order statement $\forall$R$\forall$x (x ...
1
vote
3answers
56 views

How would the intersection of two uncountable sets be finite?

This is a problem from Discrete Mathematics and its Applications Here is my book's definition on countable and definition of having the same cardinality The only example that my book gave of ...
2
votes
1answer
45 views

Is this relation transitive? $R=\{(1,2),(1,1),(2,1),(2,2)\}$ over $A=\{1,2,3\}$

Is this relation $R$ over $A$ transitive?$$A=\{1,2,3\}$$ $$R=\{(1,2),(1,1),(2,1),(2,2)\}$$ Since from the definition a relation is transitive if $\forall x,y,z\in A (xRy,yRz\to xRz)$, so since $3$ ...
3
votes
1answer
56 views

What is the relationship between the cofinality and well orders?

Suppose $A$ is an infinite linear order with cardinality $\kappa$, and take the family $\langle A_{\alpha}: \alpha < \kappa \rangle$, define like this: $$A=\bigcup_{\alpha < \kappa} ...
1
vote
1answer
37 views

The cardinality of the set of open subsets and related proofs.

I have been going around in circles trying to prove this things for the last week, I would really appreciate any ideas on any of the next proofs. Let C be the linear continuum with no endpoints and ...
1
vote
0answers
30 views

The union of finite sets is a finite set

The union of two finite sets is a finite set. Let $X,Y$ be finite sets. That means that there are $n, m\in \omega$ such that $X \sim n$ and $Y \sim m$, i.e. there are functions $f: X ...
0
votes
2answers
23 views

Proof of well ordering principle for the set of positive integers with directly using the principle of induction and not strong induction

Can we prove well ordering principle for the set of natural numbers (positive integers ) with directly using the principle of induction i.e. $( S \subseteq \mathbb N ,1 \in S \space \&\ n \in S ...
1
vote
0answers
26 views

Partial order of a finite set is an intersection of a finite number of linear orders of this set

I am trying to prove that every partial order of a finite set is an intersection of a finite number of linear orders of this set. Can this be proved using these observations: a partial order has a ...
1
vote
0answers
34 views

$X$ is at most countable iff there is a $f: \omega \overset{\text{surjective}}{\rightarrow} X$.

I am looking at the proof of the following proposition: Let $X \neq \varnothing$. $X$ is at most countable iff there is a $f: \omega \overset{\text{surjective}}{\rightarrow} X$. Proof: ...
3
votes
2answers
75 views

Proof by Iteration

It seems that I suffer the "too-much-logic-too-pedantic-too-confused"-disease. (You know? This very disease which lets you doubt everything and lets you yell for formalized proof. It's annoying, ...
1
vote
1answer
33 views

Cardinality of vertex set and edge set of an infinite connected graph

Let $G=(V,E)$ be connected such that $|V|$ is infinite. Does it follow that $|E| = |V|$? (It's easy to see that $|E|\leq |V|$.)
1
vote
1answer
33 views

A quickie about set theory notation

I'm reading the first chapters of my discrete mathematics textbook and I couldn't help but wonder (perhaps I haven't seen enough examples) -- is it more appropriate to write that $a$ is an integer and ...
1
vote
1answer
27 views

What is the operator priority in set theory?

Say I have three arbitrary sets $A,B,C$. Which statement is true ? $A \times B \cup C = (A \times B) \cup C $ $\quad $ or $\quad$ $A \times B \cup C = A \times (B \cup C) $ And the same ...
1
vote
1answer
16 views

Applying set operations on subsets of $\{0, 1, 2, \ldots, 8, 9\}$

Set Operation- Let A={2,4,5,6,8} B={1,4,5,9} and c={x| E Z{positive Integer} and 2 <= x <5 } of S={0,1,2,3,4,5,6,7,8,9} compute each of the following sets: (c ∩ B)∪ ¬A my answer: C={0,1,2} ...
1
vote
1answer
56 views

True-False Problem: elementary set theory (please verify)

I'm trying to self-learn math and I'm starting with naïve set theory. The only problem is that the book I'm using lacks a solution textbook and I don't know if the solution I gave to this problem is ...
0
votes
1answer
38 views

Does $\wp(A \cap B) = \wp(A) \cap \wp(B)$ hold? How to prove it?

I'm currently working on some discrete mathematics work and I've encountered a question I'm not sure how to answer exactly. Precisely, I'm trying to prove that two power, intersected sets statements ...
0
votes
1answer
9 views

Denumerable partition of a denumerable set where each set in the partition is denumerable. [duplicate]

Suppose that a set $A$ is denumerable. Prove that there is a partition $P$ of $A$ where $P$ is denumerable and every $X \in P$ is also denumerable. I can see that this can be done but I cannot figure ...
0
votes
0answers
57 views

How to prove $f(c) = f(d) = 0$ [duplicate]

I ONLY NEED HELP WITH PROVING: $f(c) = f(d) = 0$ Robert Green's answer here : Is the first part of the answer, but I cannot problem that $f(c) = 0$ and $f(d) = 0$? How should I do this? Here was ...
1
vote
1answer
28 views

Need help with notation — finite set of random primes

I need help with notation for a finite set of random primes. Edit I've inserted my take on the format from the answer. Does it work? My attempt:$$\{X\in\binom{\mathbf P_{3,100}}{20}\},$$ ...
0
votes
1answer
23 views

How many sets of 2 without duplicates out of these options?

So there are twelve signs of the zodiac: Aries, Taurus, Gemini, Cancer, Leo, Virgo, Libra, Scorpio, Sagittarius, Capricorn, Aquarius and Pisces I want to know how many possible sets of 2 I can make ...
2
votes
1answer
39 views

Proof Verification of $B \cup A = B$ implies $Pr(A) \leq Pr(B)$

Basic Information If you're confused $Pr(A)$ stand for probability of A. My Work 1) $A\cup B = B \iff A \subseteq B$ (By Theorem 3.4 in our textbook) 2) $A \subseteq B \implies |A| \leq |B|$ ...
4
votes
2answers
37 views

$A\subset f^{-1}(f(A))$ with equality if and only $f$ is injective.

I've got a little mistakes with that: $A\subset f^{-1}(f(A))$ with equality if and only $f$ is injective. For example, if we take $f(x)=x^2$ and $A=[-1,1]$, we have $$f(A)=f([-1,1])=\{f(x)\mid ...
-1
votes
1answer
23 views

List the elements of the set

Im working on my math homework and I don't even know how to do this or what it is asking. Any help would be great! Let A = {1, 2, 3} × {1, 2, 3, 4}. List the elements of the set B = {(s, t) ∈ A | s ≥ ...
2
votes
3answers
40 views

If $f\circ g = g \circ f$ does that mean that both functions are to and from the same set and both are bijections? Does it tell us anything else?

If $f\circ g = g \circ f$ does that mean that both functions are to and from the same set and both are bijections? Does it tell us anything else?
0
votes
2answers
39 views

To prove a given set is a $\sigma$ algebra

I need to prove the following If $R$ is a $\sigma$ ring then $\{ E \subset X : E \subset R $ or $ E^c \subset R \}$ is a $\sigma$ algebra. Here now my claim is that $E_j \in R\ \forall i = ...
0
votes
1answer
55 views

Attempt to proof the Cantor-Bernstein theorem

I've found a proof of the Cantor-Bernstein theorem in Kleene's 'Introduction to Metamathematics' (1952) in §4 Thm A. I must admit I don't understand its essence but I was wondering if the proof could ...
-1
votes
1answer
44 views

$\bigcup_{i \in I} \mathcal{P} (A_i)$

This is Velleman 3.7, Problem 4 Below is the problem, verbatim. Suppose $ \{ A_i \mid i \in I\}$ is a family of sets. Prove that if $\mathcal{P}(\bigcup_{i \in I} A_i) \subseteq \bigcup_{i \in I} ...
1
vote
0answers
6 views

How the union of a bound series of integers converges to all integers for cases of all orders.

For the series $S_n = \{-n, \cdots, n \}^d$ I would like to show the union of all such sets converge to $\mathbb{Z}^d$ as $n \rightarrow \infty$. That is to said, how can I prove: $$\bigcup_{n \geq ...
2
votes
2answers
16 views

Showing $R$ is transitive and reflexive $\to$ $R=R^2$, $R$ is transitive and reflexive $\to$ $R=R^2$

Let $R$ be a relation over $A$. Define $R^{-1}, R^2$ like so: $aR^{-1}b \iff bRa\\ aR^2b\iff\exists _{c\in A}(aRc\wedge cRb)$ Prove: $R$ is transitive $\iff$ $R^2\subseteq R$ ...
1
vote
1answer
17 views

Show $\alpha$ is a limit ordinal $\leftrightarrow \alpha \neq 0$ and $\cup \alpha = \alpha$

$\alpha$ is a limit ordinal $\leftrightarrow \alpha \neq 0$ and $\cup \alpha = \alpha$ Sorry if this question has been asked already but I couldn't find it on this site. I assume by definition ...
1
vote
1answer
15 views

Question about proving intersection of two transitive relation is transitive

Suppose $R,S$ are transitive relations over $A$, prove that $R\cap S$ is transitive. Let $x,y,z\in A$, since $R,S$ are transitive then $$(x,y),(y,z),(x,z)\in R \wedge S\Rightarrow ...
0
votes
0answers
16 views

Finding maximal chains in an ordered set.

Let $R$={$((x_1,y_1),(x_2,y_2))$:$x_1\le x_2, y_1\le y_2$} find the maximal chaings. Could it be that every maximal chains is of the form {$(a,b)+t(1,1)|t\in\Bbb{R}$} such that every other chain of ...
-1
votes
1answer
15 views

Ordered sets. Chain upper bounds.

Suppose I have an ordered set $A$ and a chain $B\subseteq A$ then does $B$ necessarily have a supremum? Let alone an upper bound? And if it is empty? This question is a bit confusing because I am not ...
-1
votes
1answer
30 views

Clarification on intuition behind one to one correspondence?

My book - Discrete Mathematics and its Applications This is my book's definition on if an infinite set is countable And the example it gave The "infinite set is countable if and only if it is ...
1
vote
1answer
29 views

Are maps and operators between two sets the same?

I have been reading on up on the definition of maps and operators, specifically reacting to sets (rather then the more restricted vector spaces) and their definitions seem to be identical. So are all ...
2
votes
3answers
28 views

Not a precise question on equivalence class.

Consider $f:X\longrightarrow Y$. Define a relation $\sim$ on $X$ by $a\sim b$ iff $f(a)=f(b)$. I proved that $\sim$ is an equivalence relation and that if $f$ is onto and $X/\sim$ is the set of ...
0
votes
0answers
16 views

Zorn's lemma usage\problem. [duplicate]

Let $(A,\le)$ be an ordered set. Show that if any chain has an upper bound then for any $a\in A$ there exist a maximal element such that $a\le x$. I am stuck with this... Would appreciate any ...
1
vote
1answer
16 views

Equivalence class of $(x_1,y_1)\sim(x_2,y_2)$ iff $ x_1=x_2$

I proved that $x\sim y$ iff $x-y\in \mathbb Z$ is an equivalence relation on $\mathbb R$. I'd like to know if $[x]=\{x+n:n\in\mathbb Z\}$ is an equivalence class for every $x\in \mathbb R$ (if it is ...
0
votes
2answers
25 views

Total order function property

This may have been asked before but it's difficult to search for. Suppose that $|A|=n$ and that $R$ is a total order on $A$ (not a strict order). Define $g:A \to I_n$ by $$ g(a) = |\{x \in A ~|~ ...
0
votes
1answer
18 views

Unique expression as disjoint union of indecomposable subsets

Let $f:A \to A$ be a function, we say that $B \subseteq A$ is $f$-invariant iff $f(B) \subseteq B $. We say that an invariant subset is indecomposable iff it cannot be expressed as a union of ...