0
votes
2answers
52 views

Explanation of the formula $f^{-1}(Y)=\{x \in A |f(x) \in Y\}$ for the preimage of a set

So I found a Definition in the book that goes like this to find the pre-image of a set: $$f^{-1}(Y)=\{x \in A |f(x) \in Y\}$$ Example of the theorem being used: Let $A = \{1,2,3,4,5,6\}$ and ...
3
votes
4answers
72 views

Book/Article recommendation

I am a first year Math major in the university, this summer I want to self study and go over some specific subjects. Firstly, can someone can give a suggestion for a detailed book/article about the ...
1
vote
2answers
26 views

If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
2
votes
1answer
42 views

Prove a statement with elements for Set Theory

I am stuck on this proofing question and I would like some clarification. Q: $A\subseteq B \iff A\cap B^{\prime} = \emptyset$ I already proved that LHS goes to RHS, but I am confused for the other ...
4
votes
1answer
39 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
0
votes
2answers
31 views

Subsets and Cardinality

I'm confused on if I should count a subset as one element or if I should count all the elements of that subset when computing cardinality. Example: Given the set $A = \{1,2,3,\{4,5,6\}\}$ does $A$ ...
1
vote
1answer
28 views

Find how many People Like dancing Only,People Like Movies

A survey was conducted among 402 persons regarding their interest in movies,dancing and games it was found that (i) 100 People Like games. (ii) 142 People Like movies or dancing but not games. (iii) ...
1
vote
3answers
27 views

Using set theory to count the possible paths on an XY plane

I'm taking an introductory discrete math course, and we're studying set theory. It's going okay, but I read an example problem which gave me some difficulty. I've included a screenshot of the problem. ...
0
votes
2answers
28 views

Discrete Math and Sets and subsets question

Let Universe be {1,2,3,4,5,6} If A = {1,2,3,4} then |A| = 4, and from this we can see that A is an element of U(universe), but can someone explain to me why {A} is NOT an element of U? I'snt the ...
1
vote
0answers
20 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
0
votes
0answers
40 views

How do we prove that, if $\mathcal{P}(A) \sim \mathcal{P}(B)$, then $A \sim B$? [duplicate]

The converse--if $\ A \sim B$ then $ \mathcal{P}(A) \sim \mathcal{P}(B)$--is very easy to prove. I can't see an immediate, simple proof for the converse case. It seems like a potentially good strategy ...
2
votes
1answer
36 views

Cardinality of all inverse functions (bijections) defined on: $\mathbb{R}\rightarrow \mathbb{R}$

What is the cardinality of all inverse functions defined on: $\mathbb{R}\rightarrow \mathbb{R}$? easy to calculate the upper bound which is $2^\aleph$. ($\aleph$ is the cardinality of the ...
0
votes
0answers
29 views

Notations for elementary set theory

I wish to understand the following notations which defined for every cardinals, $a,b$: $P(a,b) = \left| In(A,B) \right|$ $C(a,b) = \left| P_b(A) \right|$ $E(ab) = \left| Eq(A,B) \right|$ ...
0
votes
0answers
40 views

Simple Math Problem on Interval

It's not clear for me. I see this wikipedia page for a difference of half interval on $\mathbb{R}$ and interval on $\mathbb{R}$? For example $$ \{ (-\infty \le x \le a) \, \left|\, a \in \mathbb{R} ...
1
vote
0answers
21 views

element subset for adjacency matrix

I am trying to create an element of a matrix that is a subset of a larger matrix. However, I am told that my subscripts do not match. I wanted other people's opinion as to what I am doing wrong and ...
1
vote
2answers
83 views

Proofs involving sets - True and False?

Can someone please help me with these True and False questions? I've tried them myself, but I'm not very good at discrete math... Thank you in advance! Any set $A$ and $B$ with $B\subseteq A$ and ...
0
votes
1answer
20 views

Proving the following bijection

Let $F = \lbrace S_1, S_2, \dots, S_n \rbrace$, where $S_i \subset \lbrace 1, 2, \dots, 3m\rbrace$ and define a function $f: F \to \mathbb{N}$ by $$ f(S_i) = \sum_{j \in S_i} (n+1)^{3m-j} $$ then ...
0
votes
1answer
37 views

Help on understanding how to express sets and their relations graphically

Let $A=\{0,1\}, B=\{a,b,c\}, R=id_A, S=\{(a,b),(a,c) \}\cup id_B$ Express graphically the following: $(A,R)+(B,S)\\ (B,S)+(A,R)\\ (A,R)\times(B,S)\\ (B,S)\times(A,R)$ I'm not sure how ...
0
votes
1answer
23 views

Need help understanding transitive relations

My discrete math professor gave an example stating that the following relation is transitive, reflexive, symmetric, and antisymmetric. A = {a,b,c,d} R = {(a,a), (b,b), (c,c), (d,d)} I do not ...
1
vote
2answers
50 views

Question about proving subsets.

I need some help understanding the steps to take to prove subsets. Question: For each of the following universal statements regarding any three finite sets $X, Y$, and $Z$, determine whether it is ...
1
vote
2answers
45 views

How to prove or disprove $P(\overline A) = P(U) - P(A)$

Edit: P(U) and P(A) refer to Power Sets. I don't know how to prove, or disprove, $P(\overline A) = P(U) - P(A)$. My initial thoughts is that the statement is true: If I have a set A in universe U, ...
1
vote
1answer
92 views

Prove or find a counterexample: if $A \subseteq B, B \subseteq C, C \subseteq A$, then $A = B = C$

Proof or find a counterexample:For all sets A;B;C if $A \subseteq B$, $B\subseteq C$, and $C\subseteq A$, then $A = B = C$. I tried doing this but not sure whether going in the right way Let $x\in ...
0
votes
1answer
41 views

Prove equality of set equations

I have to prove that $$A\setminus(A\setminus B)=(B\setminus A)\triangle B$$ I am asked to do that by method, where: we assume that some element $u\in A\setminus (A\setminus B) \Rightarrow u\in A\wedge ...
1
vote
1answer
30 views

Discrete math set theory

If a and b are finite sets then, n(A∩B) = n(A)+n(B)-n(A∪B) will this statement be false? and why please explain
1
vote
3answers
72 views

Prove that $A\subseteq B\Longleftrightarrow A\cap B = A$

In set theory logic mathematics. How would i do the proof for: $A\subseteq B\Longleftrightarrow A\cap B = A$
1
vote
1answer
32 views

Number of relations from A to B with specific domain

I have two sets $A = \{1,2,3,4\}$, $B = \{5,6,7,8,9\}$ I need to find the number of relations from $A$ to $B$ which includes $\{1,2,3\}$ in the domain. It says to use the Inclusion–exclusion ...
-1
votes
1answer
43 views

For all sets A, B, and C, if A ⊆ B, then A∩C ⊆ B∩C

Prove each of these statements. Use equation editor for mathematical symbols, formulas, predicates, equations, and so forth. You may use all the proof techniques we've used so far: direct proof, ...
0
votes
3answers
45 views

How many subsets of a set $S$ of size $37$ contain $x$, but not $y$, where $x,y$ are distinct?

Let $S$ be a set of Size $37$, let $x$ and $y$ be distinct elements of $S$. How many subsets of $S$ are there that contain $x$, but do not contain $y$. Can you explain why the answer is $2^{35}$?
1
vote
2answers
43 views

one to one positive integers and positive rationals

How would you go about proving that there is a 1 : 1 correspondence between the set of positive integers and the set of positive rationals. I know there are a lot of ways to do this but I am looking ...
0
votes
1answer
37 views

Maximum size of a poset chain

Let m,n ≥ 2. Consider the poset ({1,...,m}×{1,...,n}, ρ) where ρ is defined by (i,j)ρ(k,l) if and only if i ≤ k and j ≤ l. What is the maximum size of a chain in this poset? What is the maximum size ...
1
vote
3answers
23 views

Intersection of two sets that contain other sets as elements

How would the intersection of $A=\{a, b, e, \{a, b, c, d\}, \{d, e\}\}$ and $B=\{a, b, c, f, \{a, d\}, \{d, e\}\}$ be defined? I've searched quite a few books but no luck so far.
0
votes
2answers
34 views

Proving that $S_k = \{A \subset \mathbb{N} : |A| = k\}$ for $k\in\mathbb{N}$ is denumerable. [duplicate]

I am having trouble with this problem for quite some time. I posted this question before but I still can not figure out this problem. So far,from the suggestion of user134824, I have tried to define ...
0
votes
1answer
60 views

Proving that these two sets are denumerable.

(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$ (b) $S = \bigcup_{k=1}^\infty S_k$ Work: For (a), I am not too sure about what approach I should use. I think finding a bijective ...
0
votes
1answer
42 views

Prove a statement for the infinite matrix

We are given infinite two dimensional matrix $\{a_{i,j}\}_{i,j=1}^\infty$. And we know that matrix contain only natural values and each number appears in the matrix exactly 8 times. Task is to prove ...
2
votes
1answer
50 views

Question about $\aleph = 2^{\aleph_0}$ proof.

I'm reading this proof from my course's book for the identity: $\aleph = 2^{\aleph_0}$ The proof starts with the claim: $2^{\aleph_0} \le \aleph \le 10^{\aleph_0}$. Then, since $2^{\aleph_0} = ...
2
votes
1answer
35 views

Show that $\mathfrak c +{\aleph_0}=\mathfrak c$ using “presenters”

I need to prove that $\mathfrak c +{\aleph_0}=\mathfrak c$ using "presenters". For example, in order to prove that $\mathfrak c +\mathfrak c=\mathfrak c$ We can show that: $$\mathfrak c =\left| ...
0
votes
1answer
35 views

When proving a partial order relation is a total order do we have assume both elements are distinct?

Consider the "divides" relation on the set $A=\lbrace 1,2,2^2,.\;.\;.,2^n\rbrace$, where $n$ is a non-negative integer. Prove that this relation is a total order on $A$. First we prove $A$ is a ...
0
votes
1answer
30 views

Equivalence Relations and distinct equivalence classes

$A=\lbrace(1,3),(2,4),(-4,-8),(3,9),(1,5),(3,6)\rbrace$. $R$ is defined on $A$ as follows: For all $(a, b)\;(c, d) \in A$, $(a, b) R (c, d) \iff ad=bc$ I know what they are asking but I cannot see ...
1
vote
1answer
24 views

Solving a poset for less than equal?

I don't completely understand posets yet, so I'm confused on how to do this particular problem. Here is the question: Let S be the set of all real numbers. Prove that the less than or equal to ...
1
vote
3answers
69 views

Showing a subset is uncountable [closed]

How do I show if $A \subseteq B$, and $A$ is uncountable then $B$ is uncountable?
1
vote
1answer
55 views

Proving a Bound for Oddtown-Eventown or Clubtown

Suppose we have a town with a set of residents $V$, where $|V| = n$. The residents like forming clubs, and we have clubs $C_1,C_2,\ldots,C_m \subseteq V$. We are interested in the maximum number of ...
0
votes
2answers
59 views

Writing in set builder notation

I need to write following set in to set builder notation. $\{ 0,3,6,9,12 \}$ Solution which I found on internet is: $\{3x\;|\;\text{where }x\text{ is an integer and }0\leq x \leq 4\}$ What I ...
1
vote
3answers
61 views

Understanding Set Theory and Proving $A \cap(B\cup A) = A$

I am trying to wrap my head around discrete mathematics in order to help my understanding of self taught programming. I am now trying to understand Set Theory, more specifically proving certain ...
0
votes
0answers
32 views

Proving a set is equal to another set

For all sets $A$ and $B,(B-A)=B\cap A^C$. I would like to know if this proof is correct or if I am on the right track. Here it is: Let $b \in B$ such that $b \notin A$ than $b \in B$ and $b \in ...
1
vote
2answers
38 views

How to Prove this Set Question? [closed]

For both sets C and D, provide a proof that C ∪ (D − /C) = C "/C" is a set's complement of C
-1
votes
2answers
142 views

Give a Bijection that is in-between 2 intervals and use a formal proof to show that it is a bijection. [duplicate]

∀w,x,y,z ∈ R, w < x and y < z. Given that information, supply a bijection between the two intervals. (w,x) and (y,z) Then after you find the bijection, provide a formal proof that what you found ...
3
votes
1answer
54 views

Please check these proofs for sets

I would appreciate the insight again for a couple of proofs since I'm learning. These are homework problems in so much as they are problems from the textbook. They are not required by my professor. ...
0
votes
1answer
83 views

Can you conclude that A = B if A, B, and C are sets such that…

a. A ∪ C = B ∪ C b. A ∩ C = B ∩ C c. A ∩ C = B ∩ C and A ∪ C = B ∪ C My method of solving this was to convert everything to propositional logic, then to solve it to show that none of the above are ...
1
vote
1answer
47 views

$M_{R^n}$; how to derive $n$ for transitive closure?

When finding the transitive closure of a relation $R$, I convert $R$ into a boolean matrix $M_R$, and find the union between $M_R$ and its powers up to $n$. $$M_{R^*} = M_{R^1} \lor M_{R^2} \lor ...
0
votes
1answer
41 views

set theory, infinite set proof, is it alright?

$\Bbb{N}$ is the natural numbers set (included $0$). let be $n\in\Bbb{N}$, $A_n = \{x\in \Bbb{N}|0\leq x \leq n\}$ prove of disprove: $$\forall n,k \in \Bbb{N},\exists m \in\Bbb{N}(|A_m - A_n|=k)$$ ...