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

3
votes
1answer
62 views

Can a relation be transitive when it is not reflexive?

Lets say I have the following set: $$ \{1, 2\}$$ and on it the following relation is given: $$\{(1, 2), (2, 1)\}.$$ Now is the above relation transitive? My confusion: we can see, that it is ...
1
vote
3answers
244 views

Russell's Paradox in *Naive Set Theory* by Paul Halmos

In Naive Set Theory, Paul Halmos introduces an arbitrary set $A$ and another set $B = \lbrace{x \in A: x \notin x \rbrace}$. He then asserts that $B \notin A$ because $B \in A$ implies $B \in B$ or $B ...
1
vote
0answers
69 views

Prove that the set with $c^a$ is countable

$A = \{$prime integers$\}$ $B = \{$odd, positive multiples of $5$$\}$ $C = \{(b^a)/(a^b)|a \in A, b \in B\}$ Prove that $C\cup \{c^a|a \in A, c \in C\}$ is countable. I have no idea ...
1
vote
1answer
173 views

What's the successor of $\emptyset$? Do we need to assume that $\emptyset \in \emptyset$ for the successor to exist?

I'm reading Guerino Mazzolla's Comprehensive Mathematics for Computer Scientists 1: Axiom 3 (Axiom of Union) If $a$ is a set, then there is a set $$\{x| \text{ there exists an element } b \in ...
1
vote
3answers
720 views

if A and B are subsets of a Universal set U , how to prove that U \ (A \ B) = (U \ A) union B

i started by saying let x belongs to U \ (A \ B) then x belongs to U and x doesn't belongs to A\B but then how do i proceed from here , any help appreciated
-1
votes
3answers
82 views

Class Transitivity Proof

Prove that a class $T$ is transitive iff $\bigcup_{t \in T},\, t \subseteq T$ iff $a \in t$ whenever $a \in b$ and $b \in T$. I know that I need to begin by proving the first statement implies ...
1
vote
3answers
56 views

What Does Surjective Functions imply?

If a function $f: A \rightarrow B$ is surjective (don't know anything about injection), does that imply whenever x is in A, then $f(x)$ is in B, that is, $ \forall x \in A, \; f(x) \in B$?
2
votes
2answers
186 views

Conditions equivalent to the surjectivity of a function

Show that the following are equivalent for a map $f:X \to Y$. $\,f$ is a surjection. $\,f[f^{-1}[B]]=B$ for each $B \subseteq Y$. $\,f^{-1}[B] \subsetneq f^{-1}[C]$ for each $B ...
1
vote
2answers
49 views

Can't make sense out of this definition of the $xor$ function

Can someone clear up the following definition for me? Let $U \subseteq \mathbb{N}$. We say that a function $x: \{0,1\}^U\to \{0,1\}$ is a $xor$ on the set $U$ if the following condition is met: ...
2
votes
2answers
59 views

Let $A \subseteq X$ and $f: X \mapsto X$. Prove $f^{-1}(A) = A \iff f(A) \subseteq A \land f^{-1}(A) \subseteq A$

Let $A \subseteq X$ and $f: X \mapsto X$. Prove $f^{-1}(A) = A \iff f(A) \subseteq A \land f^{-1}(A) \subseteq A$ I have already proved $f(f^{-1}(A)) \subseteq A$: $e \in f(f^{-1}(A)) = \{f(x) \mid ...
0
votes
1answer
66 views

Why isn't $ P( \cup_n A_n) = \text{lim}_n P(A_n)$ obvious?

Let ( $ \Omega, \cal A$, P ) be a probability space. Let $(A_n)_n $ be an increasing sequence of events. I am reading a proof using $\sigma$-additivity to prove that $$ P( \cup_n A_n) = \text{lim}_n ...
4
votes
2answers
176 views

Set “in between” integers and reals

All infinite sets that I know of are either countably infinite, or uncountably infinite. This leads me to ask the following question: Is there any infinite set S s.t. there is no bijection between S ...
1
vote
1answer
74 views

A set that is an element of itself

Suppose that $A_1 = \left\{ 5 \right\}$ and that for each $n \in \mathbb{N}$, $$ A_{n+1} = \left\{ A_{n} \right\}.$$ Now consider the set $$A = \bigcup_{n=1}^\infty \mathcal P (A_n).$$ Is it true ...
4
votes
3answers
414 views

Empty functions are not injective?

Many sources say that empty functions such as $f:\emptyset \rightarrow S$ are injective because it is a vacuous truth. But currently I am reading a book on axiomatic set by Patrick Suppes, and he ...
4
votes
1answer
78 views

Can a function have overlapping range?

Consider the function $f : \mathbb{R}\rightarrow\mathbb{R}$ defined by $$f(x)=\left\{\begin{align}x^2 - 2 & \text{if}\,x > 0,\\ x - 1 & \text{if}\, x \le 0.\end{align}\right.$$ Find a right ...
6
votes
3answers
197 views

Search for a good analogy in the real world for the mathematical concept of set

I looked for a good explanation of a set for a course. Therefore I want to find a good analogy of this concept in real life. First I thought of explaining the set as something like a container such as ...
1
vote
1answer
88 views

Doubts on the axiom of union?

I'm reading Guerino Mazzolla's Comprehensive Mathematics for Computer Scientists 1: Axiom 3 (Axiom of Union) If $a$ is a set, then there is a set $$\{x| \text{ there exists an element } b \in ...
1
vote
2answers
147 views

Set Theory and Equality

Let $A$ and $X$ be sets. Show that $X\setminus(X\setminus A)\subseteq A$, and that equality holds if and only if $A\subseteq X$. I understand why this holds but am not sure how to 'show' this. Any ...
3
votes
1answer
3k views

into function vs injective function

In many mathematical books that I have read and from lectures from professors, the words 'into' and 'injective' were used interchangeably, but in Patrick Suppes book Axiomatic Set Theory he gives a ...
2
votes
1answer
228 views

Bijection from a set of functions to a Cartesian product of sets [duplicate]

Let S be an arbitrary set. Let $F=\{f:\{0,1\}\to S\}$ be the set of functions from $\{0,1\}$ to S. Construct a bijection $F→S \times S$. I think I would define the function $a(f)=(f(0),f(1))$ ...
3
votes
4answers
134 views

How do I show a set $A = (A\setminus B)\cup (A\cap B)$ for discrete math?

How would I go about showing that for any set A and B, $$A = (A\setminus B)\cup (A\cap B)?$$ I don't really understand how to show this. Here's my interpretation: $$A = (A\setminus B)\text{ or } ...
1
vote
1answer
67 views

I have doubts about my proof of this…

Well umm... I have a doubt if this proof is correct or I made some mistakes, especially in the second part of the proof and the extra assumptions I made. If anybody can correct me or say just that ...
2
votes
3answers
59 views

does the domain can be considered as subset of it image under 1 to 1 function?

Let $f\colon X \to X$ be a one-to-one function and let $A \subseteq X$. Does $A \subseteq f(A)$? I ask because I found a step which not clear to me in this paper ...
1
vote
2answers
115 views

Prove $A \subseteq (B \cap C) \iff (A \subseteq B)$ and $(A \subseteq C)$

I need some help with the following proof: $A \subseteq (B \cap C) \iff (A \subseteq B) \text{ and }(A \subseteq C)$. Any help would be appreciated.
1
vote
1answer
104 views

Why is the Jacobi symbol the product of the Legendre symbols of its prime factorization?

Does someone know the proof of why the Jacobi symbol is the product of the Legendre symbols of its prime factorization? i.e. why does: $$\left(\frac{z}{pq}\right) = ...
1
vote
2answers
80 views

Basic Cartesian prodcuts

I am having some issues grasping basic ideas of Cartesian products. I am reading a PDF my professor gave us explain sets/Cartesian products. If $\mathbb{R}\times \mathbb{R}$ can be written as ...
0
votes
1answer
366 views

Understanding basic sets/subsets in discrete math by determining if statements are true or false

Hi I'm working on some basic set/subset comparison statements in the form of True/False. There are 4 statements that I have to determine whether they're true or false. I think I understand the first ...
1
vote
1answer
57 views

Differences between $\omega$ versus $\aleph_0$

In what sense is $\omega$ different from $\aleph_0$? Is the following set of statements true? (1) $|\omega| = |\aleph_0|$ (2) $\omega$ is imbued with an ordering, while $\aleph_0$ isn't (although ...
1
vote
2answers
77 views

Basic set notation - has this textbook made a mistake?

An answer to one question claims that if it is true that $B=\{a,b\}, G=\{\{a,b\}, \{c,2\}\}$, then it is also true that $\{B\}\subseteq G $ But wouldn't $\{B\}=\{\{a,b\}\}$ and there is no ...
1
vote
1answer
218 views

Proof that there is no Universal Set

Give a proof that there is no universal set, using the Subset Axiom and a Russell’s-Paradox-type argument. so that is the question that I am working on. My approach at the moment is to have if ...
2
votes
1answer
6k views

Multiplication of Set Discrete math

I ran into some problems. Do you guys have any ideas about multiplication of set? For example: $A =$ $\{1,2,3\}$, $B = \{x,y\}, C=\{0,1\}$ What will you do if I want to see: $A\cdot(B\cdot C)$ Can ...
1
vote
1answer
52 views

Find the cardinal of the set of all infinite sequences of $0,1,-1$ such that each sequence contains each digit at least once - Check my answer

As the title says, we are asked to find the cardinal of the set of all infinite sequences made from the digits $0,1,-1$ such that each sequence contains each digit at least once. My answer I solved ...
0
votes
3answers
66 views

A Couple of Subset Questions

Give examples of sets A and B for which $\bigcup A = \bigcup B$ but $A \ne B$. This one makes little sense to me. I would think that if the union of two families were the same then so would the over ...
2
votes
1answer
147 views

$(X \supset A)\wedge (X \supset B)|(Y\supset A) \wedge (Y \supset B)\to Y\supset X$|Prove that $X=A \cup B$.

I've just got this question from Elon Lages' Curso de Análise Vol 1. Given the sets $A$ and $B$, let $X$ be a set with the following properties: $1.$ $(X \supset A)\wedge (X \supset B)$. ...
0
votes
4answers
130 views

Symmetric difference equality

Something I was thinking about earlier: If $A\triangle B=A \triangle C$, does $B=C$? Where $\triangle$ is symmetric difference. My intuition is telling me no, but I can't seem to think of an example ...
1
vote
2answers
1k views

Union of two countable sets

I need to prove that the union of two countable sets is countable. I have seen some solutions on this website and others, but they are all too complicated for my background. Could someone suggest a ...
1
vote
3answers
469 views

Inverse of bijection proving it is surjective.

I understand that the inverse of a bijection is a bijection. To proof this you need to formally proof it is injective and surjective. I can prove it is injective and i understand what it is in the ...
0
votes
1answer
112 views

Properly contained

I am asked to find a P(X) (powerset) where X has, say, 8 elements. Then I know that P(X) has $2^8$ elements, but how many of these are properly contained (proper subset) in X? How do I find this out? ...
0
votes
2answers
33 views

If $n$ is a finite ordinal, either $n=\emptyset$, or there exists a finite ordinal $m$ such that $n=m \cup\{m\}$

I have a difficulty with this statement : If $n$ is a finite ordinal, either $n=\emptyset$, or there exists a finite ordinal $m$ such that $n=m \cup\{m\}$. My professor's proof is totally unclear. I ...
-1
votes
1answer
57 views

Proof that two sets have the same cardinality.

Let J be the set of all even finite subsets of a set M, and U the set of the odd. Show that J and U have the same cardinality. To tell the truth, I haven't gotten far. I would appreciate any help!
-1
votes
2answers
81 views

What's an elegant way to express this set relation

I need to express a relationship between sets $A$ and $B$ such that $A\neq B$ and $A\cap B\neq\varnothing$. Is there a name for such a relation? Can assume if needed that both are non empty.
1
vote
1answer
37 views

Easy one on transitive relations

So I've got this one on my home work: Which of the following are equivalence relations on the set of $Z$ (integers)? And it presents this relation among others: $xEy$ if and only if $x^2=y^2.$ So ...
1
vote
1answer
78 views

Is there an answer? [duplicate]

A question that I've pondered for a while. How can it be such that between every two irrational numbers lie a rational and vice versa, when it has been proved there are more irrational numbers than ...
1
vote
3answers
56 views

Intersection of an infinite amount of sets

Consider a set $S = \{S_1, S_2, S_3, \dots\}$, where $S_i = \{i, i + 1, i + 2, \dots\}$. What is the intersection of all of the sets in $S$? Is the intersection even defined? If it is, I'm pretty ...
1
vote
1answer
48 views

Combinations of a Set Including Empty Set

What is the best way of finding the combinations of a set of numbers where order does not matter and the numbers in the set cannot be repeated and you can include $0$ to $n$ numbers? The only idea I ...
2
votes
3answers
103 views

Bijection for two sets.

Give a bijection between the set of odd numbers and the set of even numbers and provide proof that it is a bijection. Would this be a feasible bijection: If $a$ is odd, then $a-1$ is even. How ...
0
votes
2answers
50 views

Cartesian product help

Let $A_1 = B_1 = [0,1], A_2 = B_2 = [1,2]$ How do I get the result for $(A_1 \cup A_2) \times (B_1 \cup B_2)$ It's been like 3 years since i've had to do this.
1
vote
2answers
57 views

What makes a condition unary vs. n-ary (n>1)?

For any two disjoint sets $A$ and $B$, a set $W$ is a connection of $A$ with $B$ if $Z\in W\implies (\exists x\in A)(\exists y\in B)[Z=\{x,y\}]$ $(\forall x\in A)(\exists !y\in B)[\{x,y\}\in W]$ ...
-1
votes
2answers
61 views

Suppose B = $B_1 \cup B_2. $ Show that $A \times B = (A \times B_1) \cup (A \times B_2)$. [duplicate]

Is it always true that $(A_1 \cap A_2) \times (B_1 \cap B_2) = (A_1\times B_1) \cap (A_2 \times B_2)$ and $(A_1 \cup A_2) \times (B_1 \cup B_2) = (A_1 \times B_1) \cup (A_2 \times B_2)$? **I've ...
1
vote
2answers
58 views

Showing a class is a set.

The problem is to determine that a given class is or is not a set only using the basic axioms of modern set theory and some examples of classes that are or are not sets. The class in question is ...